Surprises in approximating Levenshtein distances

Baake, Michael; Grimm, Uwe and Giegerich, Robert (2006). Surprises in approximating Levenshtein distances. Journal of Theoretical Biology, 243(2) pp. 279–282.

DOI: https://doi.org/10.1016/j.jtbi.2006.06.026

Abstract

The Levenshtein distance is an important tool for the comparison of symbolic sequences, with many appearances in genome research, linguistics and other areas. For efficient applications, an approximation by a distance of smaller computational complexity is highly desirable. However, our comparison of the Levenshtein with a generic dictionary-based distance discussed below indicates their statistical independence. This observation suggests that a simplification along this line might not be possible without restricting the class of sequences. Several other probabilistic properties are briefly discussed, emphasizing various questions that deserve further investigation.

Viewing alternatives

Metrics

Item Actions

Export

You can export this page using these formats Digital Object Identifier - DOI