A Caltech Library Service

Duplication Distance to the Root for Binary Sequences

Alon, Noga and Bruck, Jehoshua and Farnoud, Farzad and Jain, Siddharth (2016) Duplication Distance to the Root for Binary Sequences. California Institute of Technology , Pasadena, CA. (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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 = abc → y = abbc, 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 sequences with a given root and for special classes of sequences, namely, the de Bruijn sequences, the Thue-Morse sequence, and the Fibbonaci 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.

Item Type:Report or Paper (Technical Report)
Related URLs:
URLURL TypeDescription ItemPublished Version
Bruck, Jehoshua0000-0001-8474-0812
Farnoud, Farzad0000-0002-8684-4487
Jain, Siddharth0000-0002-9164-6119
Additional Information:This paper was presented in part at 2016 IEEE International Symposium on Information Theory in Barcelona, Spain. This work was supported in part by the NSF Expeditions in Computing Program (The Molecular Programming Project), by a USA-Israeli BSF grant 2012/107, by an ISF grant 620/13, and by the Israeli I-Core program.
Group:Parallel and Distributed Systems Group
Funding AgencyGrant Number
Binational Science Foundation (USA-Israel)2012/107
Israel Science Foundation620/13
I-CORE Program of the Planning and Budgeting CommitteeUNSPECIFIED
Other Numbering System:
Other Numbering System NameOther Numbering System ID
Record Number:CaltechAUTHORS:20161108-134615672
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:71814
Deposited By: Kristin Buxton
Deposited On:09 Nov 2016 00:48
Last Modified:09 Mar 2020 13:18

Repository Staff Only: item control page