摘要
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.
- A novel genetic approach for optimized biological sequence alignmentGautam, Garai; Biswanath, ChowdhuryJournal of Biophysical Chemistry, 2012, 03(02): 201-205.被引 2
- Basic local alignment search toolAltschul S F; Gish W; Miller W; Myers E W; Lipman D JJournal of Molecular Biology, 1990, 215(3): 403-410.
- Ultrafast and memory-efficient alignment of short DNA sequences to the human genomeLangmead Ben*; Trapnell Cole; Pop Mihai; Salzberg Steven LGenome Biology: biology for the post-genomic era , 2009, 10(3): R25.被引 7454
