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.