Properties of levenshtein metrics on sequences |
| |
Authors: | William H E Day |
| |
Institution: | (1) Department of Computer Science, Memorial University of Newfoundland, A1C 5S7 St. John's, Newfoundland, Canada |
| |
Abstract: | Levenshtein dissimilarity measures are used to compare sequences in application areas including coding theory, computer science
and macromolecular biology. In general, they measure sequence dissimilarity by the length of a shortest weighted sequence
of insertions, deletions and substitutions required, to transform one sequence into another. Those Levenshtein dissimilarity
measures based on insertions and deletions are analyzed by a model involving valuations on a partially ordered set. The model
reveals structural relationships among poset, valuation and dissimilarity measure. As a consequence, certain Levenshtein dissimilarity
measures are shown to be metrics characterized by betweenness properties and computable in terms of well-known measures of
sequence similarity.
This work was supported in part by the Natural Sciences and Engineering Research Council of Canada under Grant A-4142. |
| |
Keywords: | |
本文献已被 ScienceDirect SpringerLink 等数据库收录! |
|