2020/01/17 by Nikita Polyanskii, Polyanskii, Nikita, Ilya Vorobyev +1
Computer Science · Mathematics · #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.2001.06242
6 pages, 1 table, submitted to International Symposium on Information Theory (ISIT) 2020
arxiv created 2020/01/17 · arxiv updated 2020/01/20
We study the duplication with transposition distance between strings of length n over a q-ary alphabet and their roots. In other words, we investigate the number of duplication operations of the form x = (abcd) → y = (abcbd), where x and y are strings and a, b, c and d are their substrings, needed to get a q-ary string of length n starting from the set of strings without duplications. For exact duplication, we prove that the maximal distance between a string of length at most n and its root has the asymptotic order n/log n. For approximate duplication, where a β-fraction of symbols may be duplicated incorrectly, we show that the maximal distance has a sharp transition from the order n/log n to log n at β=(q-1)/q. The motivation for this problem comes from genomics, where such duplications represent a special kind of mutation and the distance between a given biological sequence and its root is the smallest number of transposition mutations required to generate the sequence.