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:
[img]
Preview
PDF (Not Set) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (349Kb)
URL: http://www.elsevier.com/wps/find/journaldescriptio...
DOI (Digital Object Identifier) Link: http://dx.doi.org/10.1016/j.jtbi.2006.06.026
Google Scholar: Look up in Google Scholar

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 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 http://arxiv.org/abs/q-bio/0601006
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
URI: http://oro.open.ac.uk/id/eprint/5822
Share this page:

Actions (login may be required)

View Item
Report issue / request change

Policies | Disclaimer

© The Open University   + 44 (0)870 333 4340   general-enquiries@open.ac.uk