On the duplication distance of binary strings

Noga Alon, Jehoshua Bruck, Farzad Farnoud, Siddharth Jain

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

We study the tandem duplication distance between binary sequences and their roots. This distance is motivated by genomic tandem duplication mutations and counts the smallest number of tandem duplication events that are required to take one sequence to another. We consider both exact and approximate tandem duplications, the latter leading to a combined duplication/Hamming distance. The paper focuses on the maximum value of the duplication distance to the root. For exact duplication, denoting the maximum distance to the root of a sequence of length n by f(n), we prove that f(n) = Θ(n). For the case of approximate duplication, where a β-fraction of symbols may be duplicated incorrectly, we show using the Plotkin bound that the maximum distance has a sharp transition from linear to logarithmic in n at β = 1/2.

Original languageEnglish (US)
Title of host publicationProceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages260-264
Number of pages5
ISBN (Electronic)9781509018062
DOIs
StatePublished - Aug 10 2016
Externally publishedYes
Event2016 IEEE International Symposium on Information Theory, ISIT 2016 - Barcelona, Spain
Duration: Jul 10 2016Jul 15 2016

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
Volume2016-August
ISSN (Print)2157-8095

Other

Other2016 IEEE International Symposium on Information Theory, ISIT 2016
CountrySpain
CityBarcelona
Period7/10/167/15/16

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Fingerprint Dive into the research topics of 'On the duplication distance of binary strings'. Together they form a unique fingerprint.

  • Cite this

    Alon, N., Bruck, J., Farnoud, F., & Jain, S. (2016). On the duplication distance of binary strings. In Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory (pp. 260-264). [7541301] (IEEE International Symposium on Information Theory - Proceedings; Vol. 2016-August). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2016.7541301