Surprises in approximating Levenshtein distances

Simple item page
dc.creatorBaake, Michael
dc.creatorGrimm, Uwe
dc.creatorGiegerich, Robert
dc.date2006-01-06
dc.date2006-06-28
dc.date.accessioned2026-07-07T07:00:03Z
dc.date.available2026-07-07T07:00:03Z
dc.descriptionThe 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.
dc.description7 pages, 4 figures; revised version
dc.identifierhttps://arxiv.org/abs/q-bio/0601006
dc.identifierhttp://arxiv.org/abs/q-bio/0601006
dc.identifierJournal of Theoretical Biology 243 (2006) 279-282
dc.identifierdoi:10.1016/j.jtbi.2006.06.026
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/107953
dc.subjectQuantitative Methods
dc.titleSurprises in approximating Levenshtein distances
dc.typetext

Files

Collections

arXiv