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 et al., 2010 [8]) is #P-complete under polynomial-time Turing reductions. Next, we show that...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2024-12, Vol.1022, p.114880, Article 114880
Main Authors: Bailey, Lora, Blake, Heather Smith, Cochran, Garner, Fox, Nathan, Levet, Michael, Mahmoud, Reem, Matson, Elizabeth Bailey, Singgih, Inne, Stadnyk, Grace, Wang, Xinyi, Wiedemann, Alexander
Format: Article
Language:English
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 (▪) is logspace-computable (FL), improving upon the previous polynomial-time (FP) bound of Miklós & Smith [41].
ISSN:0304-3975
DOI:10.1016/j.tcs.2024.114880