Seminár z teoretickej informatiky
Fri 4 May. 2012, 11:00
Title: Complexity of rearrangement problems under breakpoint distance
Speaker: Kuko Kováč
Background: 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 [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).