On the duplication distance of binary strings

Noga Alon; Jehoshua Bruck; Farzad Farnoud; Siddharth Jain

doi:10.1109/ISIT.2016.7541301

On the duplication distance of binary strings

Noga Alon, Jehoshua Bruck, Farzad Farnoud, Siddharth Jain

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	260-264
Number of pages	5
ISBN (Electronic)	9781509018062
DOIs	https://doi.org/10.1109/ISIT.2016.7541301
State	Published - Aug 10 2016
Externally published	Yes
Event	2016 IEEE International Symposium on Information Theory, ISIT 2016 - Barcelona, Spain Duration: Jul 10 2016 → Jul 15 2016

Publication series

Name	IEEE International Symposium on Information Theory - Proceedings
Volume	2016-August
ISSN (Print)	2157-8095

Other

Other	2016 IEEE International Symposium on Information Theory, ISIT 2016
Country/Territory	Spain
City	Barcelona
Period	7/10/16 → 7/15/16

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Information Systems
Modeling and Simulation
Applied Mathematics

Access to Document

10.1109/ISIT.2016.7541301

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). Article 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

@inproceedings{eb765c8250754c1b98806ed6d28c535b,

title = "On the duplication distance of binary strings",

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.",

author = "Noga Alon and Jehoshua Bruck and Farzad Farnoud and Siddharth Jain",

note = "Publisher Copyright: {\textcopyright} 2016 IEEE.; 2016 IEEE International Symposium on Information Theory, ISIT 2016 ; Conference date: 10-07-2016 Through 15-07-2016",

year = "2016",

month = aug,

day = "10",

doi = "10.1109/ISIT.2016.7541301",

language = "English (US)",

series = "IEEE International Symposium on Information Theory - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "260--264",

booktitle = "Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory",

address = "United States",

}

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., 7541301, IEEE International Symposium on Information Theory - Proceedings, vol. 2016-August, Institute of Electrical and Electronics Engineers Inc., pp. 260-264, 2016 IEEE International Symposium on Information Theory, ISIT 2016, Barcelona, Spain, 7/10/16. https://doi.org/10.1109/ISIT.2016.7541301

On the duplication distance of binary strings. / Alon, Noga; Bruck, Jehoshua; Farnoud, Farzad et al.
Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory. Institute of Electrical and Electronics Engineers Inc., 2016. p. 260-264 7541301 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2016-August).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - On the duplication distance of binary strings

AU - Alon, Noga

AU - Bruck, Jehoshua

AU - Farnoud, Farzad

AU - Jain, Siddharth

PY - 2016/8/10

Y1 - 2016/8/10

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84985916609&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84985916609&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2016.7541301

DO - 10.1109/ISIT.2016.7541301

M3 - Conference contribution

AN - SCOPUS:84985916609

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 260

EP - 264

BT - Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2016 IEEE International Symposium on Information Theory, ISIT 2016

Y2 - 10 July 2016 through 15 July 2016

ER -

On the duplication distance of binary strings

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this