Duplication with transposition distance to the root for q-ary strings

Nikita Polyanskii, Ilya Vorobyev

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

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/logn. 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/logn to logn 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.

Original languageEnglish
Title of host publication2020 IEEE International Symposium on Information Theory, ISIT 2020 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages2903-2908
Number of pages6
ISBN (Electronic)9781728164328
DOIs
Publication statusPublished - Jun 2020
Event2020 IEEE International Symposium on Information Theory, ISIT 2020 - Los Angeles, United States
Duration: 21 Jul 202026 Jul 2020

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
Volume2020-June
ISSN (Print)2157-8095

Conference

Conference2020 IEEE International Symposium on Information Theory, ISIT 2020
Country/TerritoryUnited States
CityLos Angeles
Period21/07/2026/07/20

Keywords

  • combinatorics on words
  • de Bruijn sequences
  • DNA codes
  • Duplication with transposition

Fingerprint

Dive into the research topics of 'Duplication with transposition distance to the root for q-ary strings'. Together they form a unique fingerprint.

Cite this