On the Complexity of Rearrangement Problems under the Breakpoint Distance

Details On the Complexity of Rearrangement Problems under the Breakpoint Distance On the Complexity of Rearrangement Problems under the Breakpoint Distance

2011-12-09

arxiv.org/abs/1112.2172v1

Computer Science

Discrete Mathematics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

On the Complexity of Rearrangement Problems under the Breakpoint Distance does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Complexity of Rearrangement Problems under the Breakpoint Distance, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Complexity of Rearrangement Problems under the Breakpoint Distance will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-44555