TY - JOUR
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:
© 2024 Elsevier B.V.
PY - 2024/12/29
Y1 - 2024/12/29
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 et al., 2010 [8]) is #P-complete under polynomial-time Turing reductions. Next, we show that in the Single Cut or Join model (Feijão and Meidanis, 2011 [21]), the problem of enumerating all medians ([Formula presented]) is logspace-computable (FL), improving upon the previous polynomial-time (FP) bound of Miklós & Smith [41].
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 et al., 2010 [8]) is #P-complete under polynomial-time Turing reductions. Next, we show that in the Single Cut or Join model (Feijão and Meidanis, 2011 [21]), the problem of enumerating all medians ([Formula presented]) is logspace-computable (FL), improving upon the previous polynomial-time (FP) bound of Miklós & Smith [41].
UR - http://www.scopus.com/inward/record.url?scp=85204696371&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85204696371&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2024.114880
DO - 10.1016/j.tcs.2024.114880
M3 - Article
AN - SCOPUS:85204696371
SN - 0304-3975
VL - 1022
JO - Theoretical Computer Science
JF - Theoretical Computer Science
M1 - 114880
ER -