TY - GEN
T1 - Pairwise Rearrangement is Fixed-Parameter Tractable in the Single Cut-and-Join Model
AU - Bailey, Lora
AU - Blake, Heather Smith
AU - Cochran, Garner
AU - Fox, Nathan
AU - Levet, Michael
AU - Mahmoud, Reem
AU - Singgih, Inne
AU - Stadnyk, Grace
AU - Wiedemann, Alexander
N1 - Publisher Copyright:
© Lora Bailey, Heather Smith Blake, Garner Cochran, Nathan Fox, Michael Levet, Reem Mahmoud, Inne Singgih, Grace Stadnyk, and Alexander Wiedemann; licensed under Creative Commons License CC-BY 4.0.
PY - 2024/6
Y1 - 2024/6
N2 - Genome rearrangement is a common model for molecular evolution. In this paper, we consider the Pairwise Rearrangement problem, which takes as input two genomes and asks for the number of minimum-length sequences of permissible operations transforming the first genome into the second. In the Single Cut-and-Join model (Bergeron, Medvedev, & Stoye, J. Comput. Biol. 2010), Pairwise Rearrangement is #P-complete (Bailey, et. al., COCOON 2023), which implies that exact sampling is intractable. In order to cope with this intractability, we investigate the parameterized complexity of this problem. We exhibit a fixed-parameter tractable algorithm with respect to the number of components in the adjacency graph that are not cycles of length 2 or paths of length 1. As a consequence, we obtain that Pairwise Rearrangement in the Single Cut-and-Join model is fixed-parameter tractable by distance. Our results suggest that the number of nontrivial components in the adjacency graph serves as the key obstacle for efficient sampling.
AB - Genome rearrangement is a common model for molecular evolution. In this paper, we consider the Pairwise Rearrangement problem, which takes as input two genomes and asks for the number of minimum-length sequences of permissible operations transforming the first genome into the second. In the Single Cut-and-Join model (Bergeron, Medvedev, & Stoye, J. Comput. Biol. 2010), Pairwise Rearrangement is #P-complete (Bailey, et. al., COCOON 2023), which implies that exact sampling is intractable. In order to cope with this intractability, we investigate the parameterized complexity of this problem. We exhibit a fixed-parameter tractable algorithm with respect to the number of components in the adjacency graph that are not cycles of length 2 or paths of length 1. As a consequence, we obtain that Pairwise Rearrangement in the Single Cut-and-Join model is fixed-parameter tractable by distance. Our results suggest that the number of nontrivial components in the adjacency graph serves as the key obstacle for efficient sampling.
KW - Computational Complexity
KW - Genome Rearrangement
KW - Phylogenetics
KW - Single Cut-and-Join
UR - http://www.scopus.com/inward/record.url?scp=85195404579&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85195404579&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.SWAT.2024.3
DO - 10.4230/LIPIcs.SWAT.2024.3
M3 - Conference contribution
AN - SCOPUS:85195404579
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 19th Scandinavian Symposium on Algorithm Theory, SWAT 2024
A2 - Bodlaender, Hans L.
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 19th Scandinavian Symposium on Algorithm Theory, SWAT 2024
Y2 - 12 June 2024 through 14 June 2024
ER -