Computational Biology
@ Comenius University in Bratislava

Jakub Kovac. On the complexity of rearrangement problems under the breakpoint distance. Journal of Computational Biology, 21(1):1-15. 2014.

Download preprint: not available

Download from publisher: http://online.liebertpub.com/doi/abs/10.1089/cmb.2013.0004

Related web page: not available

Bibliography entry: BibTeX

See also: early version

Abstract:

We study the complexity of rearrangement problems in the generalized breakpoint
model of Tannier et al. and settle several open questions. We improve the
algorithm for the median problem and show that it is equivalent to the problem of
finding maximum cardinality nonbipartite 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 
a quartet phylogeny. We also show that in the unichromosomal and the multilinear 
breakpoint model the halving problem is NP-hard, refuting the conjecture of
Tannier et al. Interestingly, this is the first problem that is harder in the
breakpoint model than in the double cut and join or reversal models.