dorsal/arxiv
View SchemaSurprises in approximating Levenshtein distances
| Authors | Michael Baake, Uwe Grimm, Robert Giegerich |
|---|---|
| Categories | |
| ArXiv ID | q-bio/0601006 |
| URL | https://arxiv.org/abs/q-bio/0601006 |
| DOI | 10.1016/j.jtbi.2006.06.026 |
| Journal | Journal of Theoretical Biology 243 (2006) 279-282 |
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.
{
"annotation_id": "b98e320f-fcec-41e2-8e3f-235d26c8a0a1",
"date_created": "2026-03-02T18:01:35.135000Z",
"date_modified": "2026-03-02T18:01:35.135000Z",
"file_hash": "7470a28ed0b213af53b43c41cc840a1f8783acf9a772fb2c821bfdba84ae4c4e",
"private": false,
"record": {
"abstract": "The Levenshtein distance is an important tool for the comparison of symbolic\nsequences, with many appearances in genome research, linguistics and other\nareas. For efficient applications, an approximation by a distance of smaller\ncomputational complexity is highly desirable. However, our comparison of the\nLevenshtein with a generic dictionary-based distance indicates their\nstatistical independence. This suggests that a simplification along this line\nmight not be possible without restricting the class of sequences. Several other\nprobabilistic properties are briefly discussed, emphasizing various questions\nthat deserve further investigation.",
"arxiv_id": "q-bio/0601006",
"authors": [
"Michael Baake",
"Uwe Grimm",
"Robert Giegerich"
],
"categories": [
"q-bio.QM"
],
"doi": "10.1016/j.jtbi.2006.06.026",
"journal_ref": "Journal of Theoretical Biology 243 (2006) 279-282",
"title": "Surprises in approximating Levenshtein distances",
"url": "https://arxiv.org/abs/q-bio/0601006"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "fe989ed6-d046-49b9-a220-d1475ae47b29",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}