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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Complexity and Enumeration in Models of Genome Rearrangement
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, & …
Maximum likelihood estimates of pairwise rearrangement distances
Accurate estimation of evolutionary distances between taxa is important for many phylogenetic reconstruction methods. In the case of bacteria, distances can be estimated using a range of different evolutionary models, fr…
PEARL: Parallelized Expert-Assisted Reinforcement Learning for Scene Rearrangement Planning
Scene Rearrangement Planning (SRP) is an interior task proposed recently. The previous work defines the action space of this task with handcrafted coarse-grained actions that are inflexible to be used for transforming sc…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Rearrangement Events on Circular Genomes
Early literature on genome rearrangement modelling views the problem of computing evolutionary distances as an inherently combinatorial one. In particular, attention was given to estimating distances using the minimum nu…
Strong Backdoors for Default Logic
In this paper, we introduce a notion of backdoors to Reiter's propositional default logic and study structural properties of it. Also we consider the problems of backdoor detection (parameterised by the solution size) as…