IEEE Transactions on Information Theory · 2020 · 150 citations · 81 references
Life SciencesBioinformaticsBiologyComputational BiologyGenomicsSequence AnalysisDna SequencingDynamic Programming For AlignmentGenome SequencingProtein Database SearchSequence AlignmentSequence Similarity SearchBiological Sequence AlignmentBlast AlgorithmsLocal AlignmentMetric EntropyProtein Sequence SearchSequence ComparisonSequence SimilaritySimilarity Search
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.
81
Basic local alignment search tool
Stephen F. Altschul, Warren Gish, Webb Miller et al. · Journal of Molecular Biology · 1990 · 94.5K citations
A Mathematical Theory of Communication
Claude E. Shannon · Bell System Technical Journal · 1948 · 80.7K citations
Fast and accurate short read alignment with Burrows–Wheeler transform
Heng Li, Richard Durbin · Bioinformatics · 2009 · 62.8K citations · Full text
Fast gapped-read alignment with Bowtie 2
Ben Langmead, Steven L. Salzberg · Nature Methods · 2012 · 61.1K citations