Extension operations on sets of leaf-labelled trees (Q1914784)

Trees with labelled leaves are useful models for representing evolutionary relationships, particularly in biology (where they are called phylogenetic trees). The wider availability of genetic sequence data, and the use of tree-building programs has led to a substantial increase in the size and number of phylogenetic trees. This trend has heightened the relevance of the generalized tree compatibility problem: determining whether a collection of phylogenetic trees on overlapping sets of taxa can be combined into one all-inclusive tree. Any ``divide and conquer'' technique for large classifications encounters this problem, as would any attempt to incorporate the many existing phylogenies into new phylogenetic trees. Tree compatibility can be efficiently determined when all the input trees are either all rooted or have a leaf in common. If the trees have the same leaf sets then compatibility can be determined in linear time. However, the general problem for unrooted trees is NP-complete. A further problem in combining phylogenetic trees is that any tree constructed might be only one among a multitude of possible trees, each of which is well supported by the data. In practice there are often thousands of suitable trees consistent with any given data set. This reflects the exponentially large number of possible phylogenetic trees. Our approach is to break the initial collection of trees into an equivalent set of binary trees, each with three leaves (rooted triples) or four leaves (quartets). In this way, many of the original problems involving phylogenetic trees can be converted into equivalent problems involving these sets. In the remainder of this section we define phylogenetic trees and compatibility, giving a brief survey of related concepts in the literature. We characterize compatibility in terms of quartets and rooted triples and discuss when a collection of subtrees defines a unique tree. Section 2 introduces compatibility rules for quartet sets and proves a number of related properties. Section 3 examines sets of rooted triples and presents a new graphical characterization of consistency and closure. In Section 4 we use this graphical representation to prove that there are rules of any order that cannot be derived from rules of lesser order. The result is proved first for rooted triples and then extended to quartets.