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://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
Mathematics, Computing and Technology
Item ID: 5822
Depositing User: Uwe Grimm
Date Deposited: 07 Nov 2006
Last Modified: 25 Feb 2016 07:56
URI: http://oro.open.ac.uk/id/eprint/5822
Share this page:

Altmetrics

Scopus Citations

► Automated document suggestions from open access sources

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   + 44 (0)870 333 4340   general-enquiries@open.ac.uk