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.

Keywords

Greedy algorithmDynamic programmingComputer scienceAlgorithmUniGeneBiologyGenomeGenetics

Affiliated Institutions

Related Publications

Fast and accurate short read alignment with Burrows–Wheeler transform

Heng Li , Richard Durbin

Abstract Motivation: The enormous amount of short reads generated by the new DNA sequencing technologies call for the development of fast and accurate read alignment programs. A...

2009 Bioinformatics 59569 citations

Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit

Joel A. Tropp , Anna C. Gilbert

This paper demonstrates theoretically and empirically that a greedy algorithm called Orthogonal Matching Pursuit (OMP) can reliably recover a signal with $m$ nonzero entries in ...

2007 IEEE Transactions on Information Theory 9473 citations

The order of sequence alignment can bias the selection of tree topology.

James A. Lake

Sequential pairwise alignment of multiple sequences is a widely used procedure (Kruskal 1983 ).It is useful and generally successful when sequences within a set differ by relati...

1991 Molecular Biology and Evolution 150 citations

VSEARCH: a versatile open source tool for metagenomics

Torbjørn Rognes , Tomáš Flouri , Ben Nichols +2 more

Background VSEARCH is an open source and free of charge multithreaded 64-bit tool for processing and preparing metagenomics, genomics and population genomics nucleotide sequence...

2016 PeerJ 10017 citations

A Rapid Bootstrap Algorithm for the RAxML Web Servers

Alexandros Stamatakis , Paul Hoover , Jacques Rougemont

Despite recent advances achieved by application of high-performance computing methods and novel algorithmic techniques to maximum likelihood (ML)-based inference programs, the m...

2008 Systematic Biology 6968 citations

Publication Info

Year: 2000
Type: article
Volume: 7
Issue: 1-2
Pages: 203-214
Citations: 5473
Access: Closed

External Links

View on DOI.org

Social Impact

Altmetric

A Greedy Algorithm for Aligning DNA Sequences

PlumX Metrics

Social media, news, blog, policy document mentions

Citation Metrics

5473

OpenAlex

Cite This

APA Style

                            
                                
                                    Zheng Zhang, 
                                
                                    Scott Schwartz, 
                                
                                    Lukas Wagner
                                
                                et al.
                            
                            (2000). 
                            A Greedy Algorithm for Aligning DNA Sequences. 
                            Journal of Computational Biology
                            , 7
                            (1-2)
                            , 203-214.
                            https://doi.org/10.1089/10665270050081478
                        

Identifiers

DOI: 10.1089/10665270050081478