Properties of levenshtein metrics on sequences |
| |
Authors: | William H. E. Day |
| |
Affiliation: | (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 等数据库收录! |
|