title: A greedy algorithm for aligning DNA sequences.
abstract: 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.
authors.affiliation: Department of Computer Science and Engineering, The Pennsylvania State University, University Park 16802, USA.
authors.forename: Z
authors.initials: Z
authors.lastname: Zhang
authors.forename: S
authors.initials: S
authors.lastname: Schwartz
authors.forename: L
authors.initials: L
authors.lastname: Wagner
authors.forename: W
authors.initials: W
authors.lastname: Miller
mesh_terms: 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
chemical_list: D004247:DNA