Sorting signed permutations by tandem duplication random loss and inverse tandem duplication random loss

被引：0

作者：

Schmidt, Bruno J. ^{[2
,3
]}

Hartmann, Tom ^{[1
]}

Stadler, Peter F. ^{[1
,2
,3
,4
,5
,6
]}

机构：

[1] Univ Leipzig, Dept Comp Sci & Interdisciplinary, Bioinformat Grp, Ctr Bioinformat, D-04107 Leipzig, Germany

[2] Ctr Scalable Data Analyt & Artificial Intelligence, Dresden Leipzig, Germany

[3] Max Planck Inst Math Sci, Inselstr 22, D-04103 Leipzig, Germany

[4] Univ Vienna, Inst Theoret Chem, Wahringerstr 17, A-1090 Vienna, Austria

[5] Univ Nacl Colombia, Fac Ciencias, Bogota, Colombia

[6] Santa Fe Inst, 1399 Hyde Pk Rd, Santa Fe, NM 87501 USA

来源：

ADVANCES IN APPLIED MATHEMATICS | 2024年 / 161卷

关键词：

Permutation sorting problem; Efficient algorithms; Genome rearrangements; MITOCHONDRIAL GENE ORDER; GENOME REARRANGEMENT; EVOLUTION; COMBINATORICS;

D O I：

10.1016/j.aam.2024.102757

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Tandem duplication random loss (TDRL) and inverse tandem duplication random loss (iTDRL) are mechanisms of mitochondrial genome rearrangement that can be modeled as simple operations on signed permutations. Informally, they comprise the duplication of a subsequence of a permutation, where in the case of iTDRL the copy is inserted with inverted order and signs. In the second step, one copy of each duplicate element is removed, such that the result is again a signed permutation. The TDRL/iTDRL sorting problem consists in finding the minimal number of TDRL or iTDRL operations necessary to convert the identity permutation iota into a given permutation pi. We introduce a simple signature, called the misc-encoding, of permutation pi. This construction is used to design an O(n ( n log n ) algorithm to solve the TDRL/iTDRL sorting problem. (c) 2024 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY-NC-ND license (http://creativecommons .org /licenses /by -nc -nd /4 .0/).

引用

页数：32

共 36 条

[11] Boore J.L., 2000, Comparative Genomes: Empirical and Analytical Approaches to Gene Order Dynamics, Map Alignment and the Evolution of Gene Families, P133, DOI DOI 10.1007/978-94-011-4309-7_13
[12] Animal mitochondrial genomes
Boore, JL
[J]. NUCLEIC ACIDS RESEARCH, 1999, 27 (08) : 1767 - 1780
[13] Big trees from little genomes: mitochondrial gene order as a phylogenetic tool
Boore, JL
Brown, WM
[J]. CURRENT OPINION IN GENETICS & DEVELOPMENT, 1998, 8 (06) : 668 - 674
[14] SORTING BY TRANSPOSITIONS IS DIFFICULT
Bulteau, Laurent
Fertin, Guillaume
Rusu, Irena
[J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2012, 26 (03) : 1148 - 1180
[15] On the tandem duplication-random loss model of genome rearrangement
Chaudhuri, Kamalika
Chen, Kevin
Mihaescu, Radu
Rao, Satish
[J]. PROCEEDINGS OF THE SEVENTHEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2006, : 564 - +
[16] Christie D.A., 1998, THESIS U GLASGOW
[17] Dobzhansky T, 1938, GENETICS, V23, P28
[18] Epstein R.A., 2012, The Theory of Gambling and Statistical Logic
[19] Fertin G., 2009, Combinatorics of genome rearrangements
[20] The combinatorics of biased riffle shuffles
Fulman, J
[J]. COMBINATORICA, 1998, 18 (02) : 173 - 184

← 1 2 3 4 →