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 (349Kb)
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 Article
ISSN: 0022-5193
Extra Information: Preprint version q-bio/0601006 available at
Keywords: global alignment; distance concepts; statistical independence; computational complexity
Academic Unit/Department: Mathematics, Computing and Technology > Mathematics and Statistics
Item ID: 5822
Depositing User: Uwe Grimm
Date Deposited: 07 Nov 2006
Last Modified: 04 Dec 2010 15:28
Share this page:


Scopus Citations

Actions (login may be required)

View Item
Report issue / request change

Policies | Disclaimer

© The Open University   + 44 (0)870 333 4340