Copy the page URI to the clipboard
Baake, Michael; Grimm, Uwe and Giegerich, Robert
(2006).
DOI: https://doi.org/10.1016/j.jtbi.2006.06.026
URL: http://www.elsevier.com/wps/find/journaldescriptio...
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.
Viewing alternatives
Download history
Metrics
Public Attention
Altmetrics from AltmetricNumber of Citations
Citations from DimensionsItem Actions
Export
About
- Item ORO ID
- 5822
- Item Type
- Journal Item
- 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 or School
-
Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
Faculty of Science, Technology, Engineering and Mathematics (STEM) - Depositing User
- Uwe Grimm