ISSN:
1522-9602
Source:
Springer Online Journal Archives 1860-2000
Topics:
Biology
,
Mathematics
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02460077
Permalink