Pairwise Rearrangement is Fixed-Parameter Tractable in the Single Cut-and-Join Model
<|reference_start|>Pairwise Rearrangement is Fixed-Parameter Tractable in the Single Cut-and-Join Model: 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 $\#\textsf{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.<|reference_end|>
@article{bailey2024pairwise,
    title={Pairwise Rearrangement is Fixed-Parameter Tractable in the Single
  Cut-and-Join Model},
    author={Lora Bailey, Heather Smith Blake, Garner Cochran, Nathan Fox, Michael
  Levet, Reem Mahmoud, Inne Singgih, Grace Stadnyk, Alexander Wiedemann},
    journal={arXiv preprint arXiv:2402.01942},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.01942},
    primaryClass={q-bio.GN cs.DS math.CO}
}