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, & Stoye, J. Comput. Biol. 2010) is $\#\textsf{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 ($\textsf{FL}$), improving upon the previous polynomial-time ($\textsf{FP}$) bound of Mikl\'os & Smith (RECOMB 2015).
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Generalized Hultman Numbers and Cycle Structures of Breakpoint Graphs
Genome rearrangements can be modeled as $k$-breaks, which break a genome at k positions and glue the resulting fragments in a new order. In particular, reversals, translocations, fusions, and fissions are modeled as $2$-…
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 permi…
A Computational Method for the Rate Estimation of Evolutionary Transpositions
Genome rearrangements are evolutionary events that shuffle genomic architectures. Most frequent genome rearrangements are reversals, translocations, fusions, and fissions. While there are some more complex genome rearran…
Estimation of the True Evolutionary Distance under the Fragile Breakage Model
The ability to estimate the evolutionary distance between extant genomes plays a crucial role in many phylogenomic studies. Often such estimation is based on the parsimony assumption, implying that the distance between t…
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…