Reduced space sequence alignment.
BACKGROUND
Sequence alignment is the problem of finding the optimal character-by-character correspondence between two sequences. It can be readily solved in O(n2) time and O(n2) space on a serial machine, or in O(n) time with O(n) space per O(n) processing elements on a parallel machine. Hirschberg's divide-and-conquer approach for finding the single best path reduces space use by a factor of n while inducing only a small constant slowdown to the serial version.


RESULTS
This paper presents a family of methods for computing sequence alignments with reduced memory that are well suited to serial or parallel implementation. Unlike the divide-and-conquer approach, they can be used in the forward-backward (Baum-Welch) training of linear hidden Markov models, and they avoid data-dependent repartitioning, making them easier to parallelize. The algorithms feature, for an arbitrary integer L, a factor proportional to L slowdown in exchange for reducing space requirement from O(n2) to O(n1 square root of n). A single best path member of this algorithm family matches the quadratic time and linear space of the divide-and-conquer algorithm. Experimentally, the O(n1.5)-space member of the family is 15-40% faster than the O(n)-space divide-and-conquer algorithm.
Grice
J A
JA
University of California, Santa Cruz 95064, USA.
Hughey
R
R
Speck
D
D
D000465:Algorithms; D003199:Computer Systems; D003201:Computers; D005069:Evaluation Studies as Topic; D008390:Markov Chains; D016415:Sequence Alignment / Q000379:methods* / Q000706:statistics & numerical data; D012984:Software