Duplication Distance to the Root for Binary Sequences

DOI10.1109/TIT.2017.2730864MaRDI QIDQ4566608zbMATH OpenFDO

Authors Noga Alon, Jehoshua Bruck, Siddharth Jain, Farzad Farnoud (Hassanzadeh)

Publication date 27 June 2018

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1611.05537

Mathematics Subject Classification ID

Measures of information, entropy (94A17) Shift register sequences and sequences over finite alphabets in information and communication theory (94A55)

Abstract: 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 $seqx=seqaseqbseqcoseqy=seqaseqbseqbseqc$, where $seqx$ and $seqy$ are sequences and $seqa$, $seqb$, and $seqc$ 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)=Theta(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 $$. 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.

Cited in

(5)

• The tandem duplication distance problem is hard over bounded alphabets
• Computing the tandem duplication distance is NP-hard
• Tandem Duplications, Segmental Duplications and Deletions, and Their Applications
• scientific article; zbMATH DE number 5494664 (Why is no real title available?)
• The Tandem Duplication Distance Is NP-Hard

This page was built for publication: Duplication Distance to the Root for Binary Sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4566608)