Complexity and Enumeration in Models of Genome Rearrangement

Lora Bailey, Heather Smith Blake, Garner Cochran, Nathan Fox, Michael Levet, Reem Mahmoud, Elizabeth Bailey Matson, Inne Singgih, Grace Stadnyk, Xinyi Wang, Alexander Wiedemann

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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

Original languageEnglish (US)
Title of host publicationComputing and Combinatorics - 29th International Conference, COCOON 2023, Proceedings
EditorsWeili Wu, Guangmo Tong
PublisherSpringer Science and Business Media Deutschland GmbH
Pages3-14
Number of pages12
ISBN (Print)9783031491894
DOIs
StatePublished - 2024
Event29th International Computing and Combinatorics Conference, COCOON 2023 - Hawaii, United States
Duration: Dec 15 2023Dec 17 2023

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume14422 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference29th International Computing and Combinatorics Conference, COCOON 2023
Country/TerritoryUnited States
CityHawaii
Period12/15/2312/17/23

Keywords

  • Computational Complexity
  • Genome Rearrangement
  • Phylogenetics
  • Single Cut or Join
  • Single Cut-and-Join

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Complexity and Enumeration in Models of Genome Rearrangement'. Together they form a unique fingerprint.

Cite this