7 - Phylogenetic networks from splits

Summary

In Chapter 5, we introduced splits and split networks and presented the Buneman graph as the canonical split network associated with a given set of splits. Splits can be computed from many different types of data, as we discuss in some of the following chapters. The focus of this chapter is on the problem of computing a split network N for a given set of splits S on X. We present two different approaches. The first is the convex hull algorithm that computes the Buneman graph and can be applied to any set of splits, using an exponential number of nodes and edges in the worst case [11]. It is also used in Section 9.4 to compute median networks. The second is the circular network algorithm, which can be applied to any set of circular splits and produces an outer-labeled planar network with only a quadratic number of nodes and edges [62].

Both algorithms proceed in two steps. In the first step, all trivial splits in S = {S₁, …, S_m} are processed to obtain a star network consisting of a central node and one leaf per taxon. Then, in the second step, the remaining splits are inserted one by one so as to obtain the final network.

To avoid some technical complexities, in the following we will assume that S contains all n trivial splits on X = {x₁, …, x_n}.