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
关键词
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 条
  • [1] Longest increasing subsequences: From patience sorting to the Baik-Deift-Johansson theorem
    Aldous, D
    Diaconis, P
    [J]. BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 1999, 36 (04) : 413 - 432
  • [2] SHUFFLING CARDS AND STOPPING-TIMES
    ALDOUS, D
    DIACONIS, P
    [J]. AMERICAN MATHEMATICAL MONTHLY, 1986, 93 (05) : 333 - 348
  • [3] Is It an Ant or a Butterfly? Convergent Evolution in the Mitochondrial Gene Order of Hymenoptera and Lepidoptera
    Babbucci, Massimiliano
    Basso, Andrea
    Scupola, Antonio
    Patarnello, Tomaso
    Negrisolo, Enrico
    [J]. GENOME BIOLOGY AND EVOLUTION, 2014, 6 (12): : 3326 - 3343
  • [4] BAFNA V, 1995, PROCEEDINGS OF THE SIXTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P614
  • [5] Perfect sorting by reversals is not always difficult
    Berard, Severine
    Bergeron, Anne
    Chauve, Cedric
    Paul, Christophe
    [J]. IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS, 2007, 4 (01) : 4 - 16
  • [7] CREx: inferring genomic rearrangements based on common intervals
    Bernt, Matthias
    Merkle, Daniel
    Ramsch, Kai
    Fritzsch, Guido
    Perseke, Marleen
    Bernhard, Detlef
    Schlegel, Martin
    Stadler, Peter F.
    Middendorf, Martin
    [J]. BIOINFORMATICS, 2007, 23 (21) : 2957 - 2958
  • [8] Genetic aspects of mitochondrial genome evolution
    Bernt, Matthias
    Braband, Anke
    Schierwater, Bernd
    Stadler, Peter F.
    [J]. MOLECULAR PHYLOGENETICS AND EVOLUTION, 2013, 69 (02) : 328 - 338
  • [9] Finding all sorting tandem duplication random loss operations
    Bernt, Matthias
    Chen, Kuan-Yu
    Chen, Ming-Chiang
    Chu, An-Chiang
    Merkle, Daniel
    Wang, Hung-Lung
    Chao, Kun-Mao
    Middendorf, Martin
    [J]. JOURNAL OF DISCRETE ALGORITHMS, 2011, 9 (01) : 32 - 48
  • [10] Bona M., 2022, Combinatorics and permutations, Vthird