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 @math , where @math and @math are sequences and @math , @math , and @math are their substrings, needed to generate a binary sequence of length @math starting from a square-free sequence from the set @math . 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 @math by @math , we prove that @math . For the case of approximate duplication, where a @math -fraction of symbols may be duplicated incorrectly, we show that the maximum distance has a sharp transition from linear in @math to logarithmic at @math . 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.
Finally, we mention that the stochastic behavior of certain duplication systems has been studied in @cite_3 @cite_11 , and error-correcting codes for combating duplication errors have been introduced in @cite_12 .
@cite_12 @cite_3 @cite_11
2858362441 2029448413 2888898008 2601746657
In this paper, we study codes correcting @math duplications of @math consecutive symbols. These errors are known as tandem duplication errors, where a sequence of symbols is repeated and inserted directly after its original occurrence. Using sphere packing arguments, we derive non-asymptotic upper bounds on the cardinality of codes that correct such errors for any choice of parameters. Based on the fact that a code correcting insertions of @math zero-blocks can be used to correct @math tandem duplications, we construct codes for tandem duplication errors. We compare the cardinalities of these codes with their sphere packing upper bounds. Finally, we discuss the asymptotic behavior of the derived codes and bounds, which yields insights about the tandem duplication channel. We present simple, polynomial time encodable and decodable codes which are asymptotically good for channels allowing insertions, deletions, and transpositions. As a corollary, they achieve exponential error probability in a stochastic model of insertion-deletion. A (tandem) duplication of length @math is an insertion of an exact copy of a substring of length @math next to its original position. This and related types of impairments are of relevance in modeling communication in the presence of synchronization errors, as well as in several information storage applications. We demonstrate that Levenshtein’s construction of binary codes correcting insertions of zeros is, with minor modifications, applicable also to channels with arbitrary alphabets and with duplication errors of arbitrary (but fixed) length @math . Furthermore, we derive bounds on the cardinality of optimal @math -ary codes correcting up to @math duplications of length @math and establish the following corollaries in the asymptotic regime of growing block length: 1) the presented family of codes is optimal for every @math , in the sense of the asymptotic scaling of code redundancy; 2) the upper bound, when specialized to @math , @math , improves upon Levenshtein’s bound for every @math ; and 3) the bounds coincide for @math , thus yielding the exact asymptotic behavior of the size of optimal single-duplication-correcting codes. The ability to store data in the DNA of a living organism has applications in a variety of areas including synthetic biology and watermarking of patented genetically modified organisms. Data stored in this medium are subject to errors arising from various mutations, such as point mutations, indels, and tandem duplication, which need to be corrected to maintain data integrity. In this paper, we provide error-correcting codes for errors caused by tandem duplications, which create a copy of a block of the sequence and insert it in a tandem manner, i.e., next to the original. In particular, we present two families of codes for correcting errors due to tandem duplications of a fixed length: the first family can correct any number of errors, while the second corrects a bounded number of errors. We also study codes for correcting tandem duplications of length up to a given constant @math , where we are primarily focused on the cases of @math . Finally, we provide a full classification of the sets of lengths allowed in tandem duplication that result in a unique root for all sequences.