8 - Phylogenetic networks from clusters

Summary

In this chapter, we present some methods for computing phylogenetic networks from clusters. Clusters, as opposed to splits, are inherently rooted and this explains why all methods presented in this chapter produce rooted phylogenetic networks. We first briefly mention the cluster-popping algorithm for computing a cluster network, and then present a divide-and-conquer approach for computing rooted phylogenetic networks. Based on this, we discuss how to compute minimum galled trees, galled networks and level-k networks from clusters.

Cluster networks

In Chapter 6, we introduced the concept of a cluster network, which is a rooted phylogenetic network that represents a set of clusters in the hardwired sense. In such a network, every tree edge represents exactly one cluster, which is defined as the set of taxa that label nodes below that edge. Given a set of clusters C on X, the cluster network N that represents C can be efficiently computed using the cluster-popping algorithm presented in Section 6.4. This algorithm is implemented in the Dendroscope program and there it can be used to compute a cluster network from the set of clusters associated with a collection of rooted phylogenetic trees [121].

Application

A typical application of a cluster network is that one is given multiple rooted gene trees for a set of species and one would like to produce a network to illustrate the parts of the phylogeny upon which the trees agree and which parts are resolved in different ways.