A greedy algorithm for aligning DNA sequences. [J Comput Biol. 2000 Feb-Apr]

SearchDatabase nameforSearch term

Advanced Search (beta)

Your browser version may not work well with NCBI's Web applications. More information here...

Display Show

All: 1

Review: 0

Click to change filter selection through MyNCBI.

1: J Comput Biol. 2000 Feb-Apr;7(1-2):203-14. Links

A greedy algorithm for aligning DNA sequences.

Zhang Z, Schwartz S, Wagner L, Miller W.

Department of Computer Science and Engineering, The Pennsylvania State University, University Park 16802, USA.

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.

PMID: 10890397 [PubMed - indexed for MEDLINE]

Aligning a DNA sequence with a protein sequence. [J Comput Biol. 1997]
Fast, optimal alignment of three sequences using linear gap costs. [J Theor Biol. 2000]
Alignments of DNA and protein sequences containing frameshift errors. [Comput Appl Biosci. 1996]
Multiple sequence alignment using an exhaustive and greedy algorithm. [J Bioinform Comput Biol. 2005]
SALSA: improved protein database searching by a new algorithm for assembly of sequence fragments into gapped alignments. [Bioinformatics. 1998]
» See all Related Articles...

Display Show

A greedy algorithm for aligning DNA sequences.

Related Articles