Complexity and Enumeration in Models of Genome Rearrangement

MaRDI QIDQ6435122zbMATH OpenFDO

Authors Lora D. Bailey, Heather Smith Blake, Garner Cochran, Nathan Fox, Michael Levet, Reem Mahmoud, Inne Singgih, Grace Stadnyk, Alexander Wiedemann

Publication date 2 May 2023

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational methods for problems pertaining to biology (92-08) Genetics and epigenetics (92D10) Protein sequences, DNA sequences (92D20)

Abstract: 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 ($extsfFL$), improving upon the previous polynomial-time ($extsfFP$) bound of Mikl'os & Smith (RECOMB 2015).

This page was built for publication: Complexity and Enumeration in Models of Genome Rearrangement

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6435122)