The Open UniversitySkip to content

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.

Full text available as:
PDF (Not Set) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (357kB)
DOI (Digital Object Identifier) Link:
Google Scholar: Look up in Google Scholar


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 indicates their statistical independence. This 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.

Item Type: Journal Item
ISSN: 0022-5193
Extra Information: Preprint version q-bio/0601006 available at
Keywords: global alignment; distance concepts; statistical independence; computational complexity
Academic Unit/School: Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
Faculty of Science, Technology, Engineering and Mathematics (STEM)
Item ID: 5822
Depositing User: Uwe Grimm
Date Deposited: 07 Nov 2006
Last Modified: 07 Dec 2018 14:41
Share this page:


Altmetrics from Altmetric

Citations from Dimensions

Download history for this item

These details should be considered as only a guide to the number of downloads performed manually. Algorithmic methods have been applied in an attempt to remove automated downloads from the displayed statistics but no guarantee can be made as to the accuracy of the figures.

Actions (login may be required)

Policies | Disclaimer

© The Open University   contact the OU