Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-26T17:15:02.612Z Has data issue: false hasContentIssue false
  • English
  • Français

On minimal Hamming compatible distances

Published online by Cambridge University Press:  05 November 2014

Parsa Bakhtary  and
Othman Echi
Parsa Bakhtary
Affiliation:
(Data Scientist) Facebook, Inc. Menlo Park, CA 94025, USA.. [email protected]
Othman Echi
Affiliation:
King Fahd University of Petroleum and Minerals, Department of Mathematics and Statistics PO Box 5046, Dhahran 31261, Saudi Arabia.; [email protected]; [email protected]
Get access

Abstract

A Hamming compatible metric is an integer-valued metric on the words of a finite alphabet which agrees with the usual Hamming distance for words of equal length. We define a new Hamming compatible metric and show this metric is minimal in the class of all “well-behaved” Hamming compatible metrics. This gives a negative answer to a question stated by Echi in his paper [O. Echi, Appl. Math. Sci. (Ruse) 3 (2009) 813–824.].

Keywords

Edit distanceHamming distancemetric space
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 48 , Issue 5 , December 2014 , pp. 495 - 503
Copyright
© EDP Sciences 2014

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Brazma, A. and Vilo, J., Gene expression data analysis. FEBS Lett. 480 (2000) 17–24. Google ScholarPubMed
Echi, O., The cardinality of a sphere relative to an edit distance. Appl. Math. Sci. (Ruse) 3 (2009) 813–824. Google Scholar
Hamming, R.W., Error detecting and error correcting codes. Bell System Technical Journal 29 (1950) 147–160. Google Scholar
Halperin, E., Buhler, J., Karp, R., Krauthgamer, R. and Westover, B., Detecting protein sequence conservation via metric embeddings. Bioinformatics 19 (2003) i122–i129. Google Scholar
Levenshtein, V.I., Binary codes capable of correcting, deletions, insertions and reversals. Soviet Phys. Dokl. 10 (1966) 707–710. Google Scholar
He, M.X., Petoukhov, S.V. and Ricci, P.E., Genetic code, Hamming distance and stochastic matrices. Bull. Math. Biol. 66 (2004) 1405–1421. Google ScholarPubMed
Pilcher, C.D., Wong, J.K. and Pillai, S.K., Inferring HIV Transmission Dynamics from Phylogenetic Sequence Relationships. PLoS Med. 5 (2008) e69. Google Scholar