Some Enumeration Problems in the Duplication-Loss Model of Genome Rearrangement

Autor:	Kovačević, Mladen, Brdar, Sanja, Crnojević, Vladimir
Rok vydání:	2019
Předmět:	Computer Science - Discrete Mathematics Computer Science - Information Theory Quantitative Biology - Genomics Quantitative Biology - Quantitative Methods 05A05 68R05 92B99 92D20 94B25
Druh dokumentu:	Working Paper
DOI:	10.1109/ISIT.2019.8849847
Popis:	Tandem-duplication-random-loss (TDRL) is an important genome rearrangement operation studied in evolutionary biology. This paper investigates some of the formal properties of TDRL operations on the symmetric group (the space of permutations over an $ n $-set). In particular, the cardinality of `balls' of radius one in the TDRL metric, as well as the cardinality of the maximum intersection of two such balls, are determined. The corresponding problems for the so-called mirror (or palindromic) TDRL rearrangement operations are also solved. The results represent an initial step in the study of error correction and reconstruction problems in this context and are of potential interest in DNA-based data storage applications. Comment: 5 pages (double-column). To be presented at the 2019 IEEE International Symposium on Information Theory (ISIT), Paris, France
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1902.00230 Zobrazit plný text záznamu View this record from Arxiv