Phylogenetic tree reconstruction is a fundamental biological problem. Quartet trees, trees over four species, are the minimal informational unit for phylogenetic classification. While every phylogenetic tree over n species defines (n4) quartets, not every set of quartets is compatible with some phylogenetic tree.#R##N##R##N#Here we focus on the compatibility of quartet sets. We provide several results addressing the question of what can be inferred about the compatibility of a set from its subsets. Most of our results use probabilistic arguments to prove the sought characteristics. In particular we show that there are quartet sets Q of size m = cn log n in which every subset of cardinality c'n/log n is compatible, and yet no fraction of more than 1/3 + e of Q is compatible. On the other hand, in contrast to the classical result stating when Q is the densest, i.e. m = (n4) the consistency of any set of 3 quartets implies full consistency, we show that even for m = Θ((n4)) there are (very) inconsistent sets for which every subset of large constant cardinality is consistent.#R##N##R##N#Our final result, relates to the conjecture of Bandelt and Dress regarding the maximum quartet distance between trees. We provide asymptotic upper and lower bounds for this value.
['Noga Alon', 'Sagi Snir', 'Raphael Yuster']
On the compatibility of quartet trees