TY - JOUR
T1 - Duplication Distance to the Root for Binary Sequences
AU - Alon, Noga
AU - Bruck, Jehoshua
AU - Hassanzadeh, Farzad Farnoud
AU - Jain, Siddharth
N1 - Funding Information:
Manuscript received October 26, 2016; revised June 14, 2017; accepted July 9, 2017. Date of publication July 26, 2017; date of current version November 20, 2017. This work was supported in part by the NSF Expeditions in Computing Program (The Molecular Programming Project), in part by USA-Israeli BSF under Grant 2012/107, in part by ISF under Grant 620/13, and in part by the Israeli I-Core Program. This paper was presented at the 2016 IEEE International Symposium on Information Theory.
Publisher Copyright:
© 1963-2012 IEEE.
PY - 2017/12
Y1 - 2017/12
N2 - We study the tandem duplication distance between binary sequences and their roots. In other words, the quantity of interest is the number of tandem duplication operations of the form x = a b c\to y = a b b c, where x and y are sequences and a, b, and c are their substrings, needed to generate a binary sequence of length n starting from a square-free sequence from the set 0, 1, 01, 10, 010, 101. This problem is a restricted case of finding the duplication/deduplication distance between two sequences, defined as the minimum number of duplication and deduplication operations required to transform one sequence to the other. We consider both exact and approximate tandem duplications. 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 that the maximum distance has a sharp transition from linear in n to logarithmic at β =1/2. We also study the duplication distance to the root for the set of sequences arising from a given root and for special classes of sequences, namely, the De Bruijn sequences, the Thue-Morse sequence, and the Fibonacci words. The problem is motivated by genomic tandem duplication mutations and the smallest number of tandem duplication events required to generate a given biological sequence.
AB - We study the tandem duplication distance between binary sequences and their roots. In other words, the quantity of interest is the number of tandem duplication operations of the form x = a b c\to y = a b b c, where x and y are sequences and a, b, and c are their substrings, needed to generate a binary sequence of length n starting from a square-free sequence from the set 0, 1, 01, 10, 010, 101. This problem is a restricted case of finding the duplication/deduplication distance between two sequences, defined as the minimum number of duplication and deduplication operations required to transform one sequence to the other. We consider both exact and approximate tandem duplications. 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 that the maximum distance has a sharp transition from linear in n to logarithmic at β =1/2. We also study the duplication distance to the root for the set of sequences arising from a given root and for special classes of sequences, namely, the De Bruijn sequences, the Thue-Morse sequence, and the Fibonacci words. The problem is motivated by genomic tandem duplication mutations and the smallest number of tandem duplication events required to generate a given biological sequence.
KW - Sequences
KW - deduplication
KW - root
KW - substrings
KW - tandem duplication
UR - http://www.scopus.com/inward/record.url?scp=85028930570&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85028930570&partnerID=8YFLogxK
U2 - 10.1109/TIT.2017.2730864
DO - 10.1109/TIT.2017.2730864
M3 - Article
AN - SCOPUS:85028930570
SN - 0018-9448
VL - 63
SP - 7793
EP - 7803
JO - IRE Professional Group on Information Theory
JF - IRE Professional Group on Information Theory
IS - 12
M1 - 7993073
ER -