A greedy algorithm for aligning DNA sequences.
For aligning DNA sequences that differ only by sequencing errors, or by equivalent errors from other sources, a greedy algorithm can be much faster than traditional dynamic programming approaches and yet produce an alignment that is guaranteed to be theoretically optimal. We introduce a new greedy alignment algorithm with particularly good performance and show that it computes the same alignment as does a certain dynamic programming algorithm, while executing over 10 times faster on appropriate data. An implementation of this algorithm is currently used in a program that assembles the UniGene database at the National Center for Biotechnology Information.
Zhang
Z
Z
Department of Computer Science and Engineering, The Pennsylvania State University, University Park 16802, USA.
Schwartz
S
S
Wagner
L
L
Miller
W
W
D000465:Algorithms; D001699:Biometry; D004247:DNA / Q000235:genetics*; D016208:Databases, Factual; D016415:Sequence Alignment / Q000706:statistics & numerical data*; D017422:Sequence Analysis, DNA / Q000706:statistics & numerical data; D012984:Software
D004247:DNA