A Greedy Algorithm for Aligning DNA Sequences
Zheng Zhang, Scott Schwartz, Lukas Wagner et al. · Journal of Computational Biology · 2000
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.
Cited by 5,478 works. doi:10.1089/10665270050081478
Authors
References
- Basic Local Alignment Search Tool
- Gapped BLAST and PSI-BLAST: a new generation of protein database search programs
- Database resources of the National Center for Biotechnology Information: update
- Base-Calling of Automated Sequencer Traces Using Phred. I. Accuracy Assessment
- An improved algorithm for matching biological sequences
- Comparative biosequence metrics
- A map of human genome sequence variation containing 1.42 million single nucleotide polymorphisms
- Deciphering the biology of Mycobacterium tuberculosis from the complete genome sequence
- Alignment of whole genomes
- Generation and analysis of 280,000 human expressed sequence tags.