4 - From split systems to networks

Summary

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 S₁ ={1, 2}|{3, 4, 5} and S₂ = {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 S₃ ={1, 2, 4}|{3, 5} in this X-tree by introducing a single edge, reflecting of course the fact that S₂ and S₃ 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 S₁ can be “obtained” by deleting the pendant edge, the split S₃ can be “obtained” by deleting the two parallel dashed edges, whereas the split S₂ can be “obtained” by deleting the remaining two, also parallel edges.