Author name cluster

Robert Niewiadomski

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

1 author row

AAAI Conference 2006 Conference Paper

Sequential and Parallel Algorithms for Frontier A* with Delayed Duplicate Detection

Robert Niewiadomski

We present sequential and parallel algorithms for Frontier A* (FA*) algorithm augmented with a form of Delayed Duplicate Detection (DDD). The sequential algorithm, FA*-DDD, overcomes the leak-back problem associated with the combination of FA* and DDD. The parallel algorithm, PFA*-DDD, is a parallel version of FA*-DDD that features a novel workload distribution strategy based on intervals. We outline an implementation of PFA*-DDD designed to run on a cluster of workstations. The implementation computes intervals at runtime that are tailored to fit the workload at hand. Because the implementation distributes the workload in a manner that is both automated and adaptive, it does not require the user to specify a workload mapping function, and, more importantly, it is applicable to arbitrary problems that may be irregular. We present the results of an experimental evaluation of the implementation where it is used to solve instances of the multiple sequence alignment problem on a cluster of workstations running on top of a commodity network. Results demonstrate that the implementation offers improved capability in addition to improved performance.

PDF Details

TCS Journal 2004 Journal Article

A space-efficient algorithm for sequence alignment with inversions and reversals

Zhi-Zhong Chen
Yong Gao
Guohui Lin
Robert Niewiadomski
Yang Wang
Junfeng Wu

A dynamic programming algorithm to find an optimal alignment for a pair of DNA sequences has been described by Schöniger and Waterman. The alignments use not only substitutions, insertions, and deletions of single nucleotides, but also inversions, which are the reversed complements, of substrings of the sequences. With the restriction that the inversions are pairwise non-intersecting, their proposed algorithm runs in O ( n 2 m 2 ) time and consumes O ( n 2 m 2 ) space, where n and m are the lengths of the input sequences, respectively. We develop a space-efficient algorithm to compute such an optimal alignment which consumes only O ( nm ) space within the same amount of time. Our algorithm enables the computation for a pair of DNA sequences of length up to 10, 000 to be carried out on an ordinary desktop computer. Simulation study is conducted to verify some biological facts about gene shuffling across species.

Details DOI