Complexity and Enumeration in Models of Genome Rearrangement

05/03/2023

∙

by   Lora Bailey, et al.

∙

0

∙

share

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 #-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 (), improving upon the previous polynomial-time () bound of Miklós Smith (RECOMB 2015).