Seminár z teoretickej informatiky

Fri 4 May. 2012, 11:00
M213

Title: Complexity of rearrangement problems under breakpoint distance
Speaker: Kuko Kováč

Background:
Tannier et al. [1] 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 [1,2].


Results:
We improve the algorithm for the median problem and show that it is
equivalent to maximum non-bipartite matching (under linear reduction).
We prove that the small phylogeny problem is NP-hard (even APX-hard) already for 4 species (a quartet phylogeny).