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.
view more