The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content



Quartet compatability: new results and surprising counterexamples

Grunewald, S (Chinese Academy of Science)
Tuesday 04 September 2007, 11:50-12:10

Seminar Room 1, Newton Institute


Many methods in phylogenetic tree reconstruction are not feasible for a large number of taxa. Hence, it is a natural approach to construct trees on small taxa sets first and then to look for a big tree (supertree) on the union of the taxa sets that contains all information of the small trees. However, even if all input trees are quartets, i.e. binary trees with four leaves, it is an NP-complete problem to decide whether they are compatible.

I will present a sufficient condition for a set of binary phylogenetic trees to be compatible. That result can be used to give a much shorter proof of the known characterization of quartet sets of minimal size which are defining, i.e. compatible with a unique supertree. Further, I will show some quartet sets with surprising properties which are counterintuitive and explain the hardness of the compatibility problem. One example is an incompatible collection of quartets for which every two quartets overlap in at most one taxon. It has been known for fifteen years that such quartet sets exist but the example is the first one that has been constructed.


[ppt ]




The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧