TY - GEN
T1 - Complexity and Enumeration in Models of Genome Rearrangement
AU - Bailey, Lora
AU - Blake, Heather Smith
AU - Cochran, Garner
AU - Fox, Nathan
AU - Levet, Michael
AU - Mahmoud, Reem
AU - Matson, Elizabeth Bailey
AU - Singgih, Inne
AU - Stadnyk, Grace
AU - Wang, Xinyi
AU - Wiedemann, Alexander
N1 - Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.
PY - 2024
Y1 - 2024
N2 - In this paper, we examine the computational complexity of enumeration in certain genome rearrangement models. We first show that the Pairwise Rearrangement problem in the Single Cut-and-Join model (Bergeron, Medvedev, & Stoye, J. Comput. Biol. 2010) is # P -complete under polynomial-time Turing reductions. Next, we show that in the Single Cut or Join model (Feijao & Meidanis, IEEE ACM Trans. Comp. Biol. Bioinf. 2011), the problem of enumerating all medians (#MEDIAN ) is logspace-computable (FL ), improving upon the previous polynomial-time (FP ) bound of Miklós & Smith (RECOMB 2015).
AB - In this paper, we examine the computational complexity of enumeration in certain genome rearrangement models. We first show that the Pairwise Rearrangement problem in the Single Cut-and-Join model (Bergeron, Medvedev, & Stoye, J. Comput. Biol. 2010) is # P -complete under polynomial-time Turing reductions. Next, we show that in the Single Cut or Join model (Feijao & Meidanis, IEEE ACM Trans. Comp. Biol. Bioinf. 2011), the problem of enumerating all medians (#MEDIAN ) is logspace-computable (FL ), improving upon the previous polynomial-time (FP ) bound of Miklós & Smith (RECOMB 2015).
KW - Computational Complexity
KW - Genome Rearrangement
KW - Phylogenetics
KW - Single Cut or Join
KW - Single Cut-and-Join
UR - http://www.scopus.com/inward/record.url?scp=85180541896&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85180541896&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-49190-0_1
DO - 10.1007/978-3-031-49190-0_1
M3 - Conference contribution
AN - SCOPUS:85180541896
SN - 9783031491894
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 3
EP - 14
BT - Computing and Combinatorics - 29th International Conference, COCOON 2023, Proceedings
A2 - Wu, Weili
A2 - Tong, Guangmo
PB - Springer Science and Business Media Deutschland GmbH
T2 - 29th International Computing and Combinatorics Conference, COCOON 2023
Y2 - 15 December 2023 through 17 December 2023
ER -