Levenshtein Distance, Sequence Comparison and Biological Database Search
Top Cited Papers
Open Access
- 21 May 2020
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 67 (6) , 3287-3294
Abstract
Levenshtein edit distance has played a central role—both past and present—in sequence alignment in particular and biological database similarity search in general. We start our review with a history of dynamic programming algorithms for computing Levenshtein distance and sequence alignments. Following, we describe how those algorithms led to heuristics employed in the most widely used software in bioinformatics, BLAST, a program to search DNA and protein databases for evolutionarily relevant similarities. More recently, the advent of modern genomic sequencing and the volume of data it generates has resulted in a return to the problem of local alignment. We conclude with how the mathematical formulation of Levenshtein distance as a metric made possible additional optimizations to similarity search in biological contexts. These modern optimizations are built around the low metric entropy and fractional dimensionality of biological databases, enabling orders of magnitude acceleration of biological similarity search.Keywords
Funding Information
- National Institutes of Health (R01GM108348)
This publication has 92 references indexed in Scilit:
- Fast gapped-read alignment with Bowtie 2Nature Methods, 2012
- How to apply de Bruijn graphs to genome assemblyNature Biotechnology, 2011
- Aligning Short Sequencing Reads with BowtieCurrent Protocols in Bioinformatics, 2010
- How to map billions of short reads onto genomesNature Biotechnology, 2009
- Applications of next-generation sequencing technologies in functional genomicsGenomics, 2008
- The Personal Genome ProjectMolecular Systems Biology, 2005
- BLAT—The BLAST-Like Alignment ToolGenome Research, 2002
- Initial sequencing and analysis of the human genomeNature, 2001
- A New Algorithm for DNA Sequence AssemblyJournal of Computational Biology, 1995
- Basic Local Alignment Search ToolJournal of Molecular Biology, 1990