Complexity and Enumeration in Models of Genome Rearrangement

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 is sharp-P-complete under polynomial-time Turing reductions. Next, we show that in the Single Cut or Join model, the problem of enumerating all medians is logspace-computable, improving upon the previous polynomial-time bound of Miklós & Smith.

Elena (Xinyi) Wang

PhD Student at CMSE

My research interests include topological data analysis(TDA), computational topology and geometry, and machine learning.