Skip to main content
SpringerLink
Log in

Properties of levenshtein metrics on sequences

  • Published:
Bulletin of Mathematical Biology Aims and scope Submit manuscript

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 is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Literature

  • Boland, R. P., E. K. Brown and W. H. E. Day. 1983. “Approximating Minimum-length-sequence Metrics: a Cautionary Note.”Math. Social Sci. 4, 261–270.

    Article  MATH  MathSciNet  Google Scholar 

  • Boorman, S. A. and P. Arabie. 1972. “Structural Measures and the Method of Sorting.” InMultidimensional Scaling, Vol. 1, Theory, Eds R. N. Shepard, A. K. Rommey and S. B. Nerlove, pp. 225–249. New York: Seminar Press.

    Google Scholar 

  • —, and D. C. Olivier. 1973. “Metrics on Spaces of Finite Trees.”J. math. Psychol. 10, 26–59.

    Article  MATH  MathSciNet  Google Scholar 

  • Bunke, H. 1983. “What is the Distance Between Graphs?”Bull. Eur. Assoc. theor. Comput. Sci. No. 20, 35–39.

    Google Scholar 

  • Day, W. H. E. 1981. “The Complexity of Computing Metric Distances Between Partitions.”Math. Social Sci. 1, 269–287.

    Article  MATH  MathSciNet  Google Scholar 

  • Flament, C. 1963.Applications of Graph Theory to Group Structure. Englewood Cliffs, NJ, Prentice-Hall.

    Google Scholar 

  • Goodman, N. 1951.The Structure of Appearance. Cambridge MA: Harvard University Press.

    Google Scholar 

  • Kruskal, J. B. 1983. “An Overview of Sequence Comparison: Time Warps, String Edits, and Macromolecules.”SIAM Rev. 25, 201–237.

    Article  MATH  MathSciNet  Google Scholar 

  • Levenshtein, V. I. 1966. “Binary Codes Capable of Correcting Deletions, Insertions, and Reversals.”Soviet Phys. Dok. 10, 707–710.

    MathSciNet  Google Scholar 

  • Lowrance, R. and R. A. Wagner. 1975. “An Extension of the String-to-string Correction Problem.”J. Assoc. Comput. Mach. 22, 177–183.

    MATH  MathSciNet  Google Scholar 

  • Masek, W. J. and M. S. Paterson. 1983. “How to Compute String Edit Distances Quickly” InTime Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison, Eds D. Sankoff and J. B. Kruskal, pp. 337–349. Reading, MA: Addison-Wesley.

    Google Scholar 

  • Monjardet, B. 1981. “Metrics on Partially Ordered Sets—a Survey.”Discrete Math. 35, 173–184.

    Article  MATH  MathSciNet  Google Scholar 

  • Needleman, S. B. and C. D. Wunsch. 1970. “A General Method Applicable to the Search for Similarities in the Amino Acid Sequence of Two Proteins.”J. molec. Biol. 48, 443–453.

    Article  Google Scholar 

  • Restle, F. 1959. “A Metric and an Ordering on Sets.”Psychometrika 24, 207–220.

    Article  MATH  MathSciNet  Google Scholar 

  • Robinson, D. F. 1971. “Comparison of Labeled Trees with Valency Three.”J. Combin. Theory 11, 105–119.

    Article  Google Scholar 

  • Sankoff, D. and J. B. Kruskal, Eds. 1983.Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison. Reading MA: Addison-Wesley.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Memorial University of Newfoundland, A1C 5S7, St. John's, Newfoundland, Canada

    William H. E. Day

Authors
  1. William H. E. Day
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

This work was supported in part by the Natural Sciences and Engineering Research Council of Canada under Grant A-4142.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Day, W.H.E. Properties of levenshtein metrics on sequences. Bltn Mathcal Biology 46, 327–332 (1984). https://doi.org/10.1007/BF02460077

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02460077

Keywords

Search

Navigation