Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-13T10:14:16.808Z 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.. bakhtary@gmail.com
Othman Echi
Affiliation:
King Fahd University of Petroleum and Minerals, Department of Mathematics and Statistics PO Box 5046, Dhahran 31261, Saudi Arabia.; othechi@yahoo.com; echi@kfupm.edu.sa

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

A Hamming compatible metric is an integer-valued metric on the words of a finite alphabetwhich agrees with the usual Hamming distance for words of equal length. We define a newHamming 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 questionstated by Echi in his paper [O. Echi, Appl. Math. Sci. (Ruse) 3(2009) 813–824.].

Keywords

Edit distanceHamming distancemetric space

Information

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

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