In the preceding chapters, we have seen how to encode trees in terms of splits, metrics, and quartets, and we have studied the relationship between these various types of encodings. Most of our discussions were concerned with what we might call “ideal data”, that is, data that correspond perfectly to a tree. However, as one might imagine, real biological data rarely come in this form. In consequence, many methods have been devised for tree and network reconstruction that try to find a tree or network that “best” fits the data, usually relative to some measure of optimality (see e.g., [76]).

It is beyond the scope of this book to review all of these methods here. Instead, we will briefly illustrate in this chapter how measuring inconsistencies in our three basic structures, split systems, metrics, and quartet systems, can be of some use in guiding the process of tree and network reconstruction.

To avoid uninteresting discussions of small cases, we will assume throughout this chapter that X is a finite set of cardinality n ≥ 3.

k-compatibility

We have seen in Chapter 3 that compatible split systems are precisely those split systems that encode X-trees. Given that split systems arising from real data will rarely be compatible, we will now consider a simple way to measure how far a given split system is from being compatible. This yields some interesting mathematical results and, as we shall see, can also provide a useful tool for analyzing biological data.

In the last chapter, we saw that X-trees can be encoded, up to canonical isomorphism, in terms of certain split systems, quartet systems, or metrics. We now start to explore how, conversely, split systems, quartet systems, or metrics can be used to (re-)construct phylogenetic relationships in terms of trees or, more generally, networks, beginning the investigation in this chapter with split systems.

Using a recursive argument, we saw already in the previous chapter that an X-tree may be encoded by — and, thus, reconstructed recursively from — the associated system of pairwise compatible X-splits. However, split systems arising in “real life” (defined, e.g., in terms of a family of naturally arising binary characters) are rarely compatible. To see how even such data may still be dealt with using “graphical” methods, consider the following example: For X ≔ 〈5〉, consider the two compatible splits S1 ={1, 2}|{3, 4, 5} and S2 = {1, 2, 3}|{4, 5} that encode the X-tree depicted in Figure 4.1(a). Clearly, it is impossible to “pop-out” the split S3 ={1, 2, 4}|{3, 5} in this X-tree by introducing a single edge, reflecting of course the fact that S2 and S3 are incompatible. However, we could still “expand” the tree along the edge connecting the vertices that are labeled with 3 and 5 so as to obtain the labeled network in Figure 4.1(b). In this graph, the split S1 can be “obtained” by deleting the pendant edge, the split S3 can be “obtained” by deleting the two parallel dashed edges, whereas the split S2 can be “obtained” by deleting the remaining two, also parallel edges.