Gene

Nearest neighbor search

Biology

Similarity (geometry)

Operating system

Economics

Biochemistry

Data mining

Computer science

Levenshtein distance

Genetics

Database

Sequence (biology)

Image (mathematics)

Operations management

Artificial intelligence

Information retrieval

Edit distance

Sequence alignment

Metric (unit)

Peptide sequence

Smith–Waterman algorithm

Heuristics

IEEE Transactions on Information Theory

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.

Levenshtein Distance, Sequence Comparison and Biological Database Search