Computational Biology
@ Comenius University in Bratislava

Jakub Kovac. On the Complexity of Rearrangement Problems under the Breakpoint Distance. Technical Report arXiv:1112.2172, arXiv.org, 2011.

Download preprint: not available

Download from publisher: http://arxiv.org/abs/1112.2172

Related web page: not available

Bibliography entry: BibTeX

Abstract:

Tannier et al. introduced a generalization of breakpoint distance for 
multichromosomal genomes. They showed that the median problem under the 
breakpoint distance is solvable in polynomial time in the multichromosomal 
circular and mixed models. This is intriguing, since in all other 
rearrangement models (DCJ, reversal, unichromosomal or multilinear 
breakpoint models), the problem is NP-hard. The complexity of the small or 
even the large phylogeny problem under the breakpoint distance remained an 
open problem.

We improve the algorithm for the median problem and show that it is 
equivalent to the problem of finding maximum cardinality non-bipartite 
matching (under linear reduction). On the other hand, we prove that the 
more general small phylogeny problem is NP-hard. Surprisingly, we show 
that it is already NP-hard (or even APX-hard) for 4 species (a quartet 
phylogeny). In other words, while finding an ancestor for 3 species is 
easy, already finding two ancestors for 4 species is hard.

We also show that, in the unichromosomal and the multilinear breakpoint 
model, the halving problem is NP-hard, thus refuting the conjecture of 
Tannier et al. Interestingly, this is the first problem which is harder in 
the breakpoint model than in the DCJ or reversal models.