Computational protocol: A Survey of Methods for Constructing Rooted Phylogenetic Networks

Similar protocols

Protocol publication

[…] So far, the main methods for constructing rooted phylogenetic networks from rooted phylogenetic trees are the cluster network, the galled network, the CASS, the LNETWORK and the BIMLR. The following will give a brief introduction to each method.The cluster network is a method for constructing rooted phylogenetic networks, which is based on the Hasse diagram. Given a set of clusters C. It first defines a partial order which is a binary relation ≼ on C: for u,v∈C, u ≼ v if and only if u ⊆ v. The (C,⪯) is called a partially ordered set. Then it draws a Hasse diagram H = (V, E) for (C,⪯), which is a DAG with node set V=C and the edge set E, where there is an edge e = (u, v) if and only if v⪵u and there exists no other node w in V such that v⪵w⪵u. Finally it labels the leaves of H by the taxa of X and assigns the root of H. The result DAG is the rooted phylogenetic network representing C.The galled network is a method based on the seed-growing algorithm. It first finds a set of taxa S⊂X by seed-growing algorithm such that the set C′=C|X\S is compatible. Next it constructs a rooted tree T for C′. Finally it attaches the reticulate nodes to T under a certain amount of constraints, where the labels of nodes which are children of reticulate nodes are the taxa of S. The constructed network represents C.The CASS, the LNETWORK and the BIMLR are the methods based on the decomposition property of networks. They first find all non-trivial biconnected components C1,C2,⋯,Ck of IG(C); and then construct the subnetwork for Ci(1≤i≤k); next integrate those subnetworks into a final network. The difference among them is the construction of the subnetworks.We have known that a network N represents an incompatible set of clusters. After removing all reticulate nodes from N, N becomes a tree representing a compatible set of clusters. However, the construction of networks is the inverse process mentioned above. Given a set of clusters C on X. We can construct a tree for C if it is compatible, otherwise, we first remove some taxa from X, such that the result set C′ is compatible, then construct a tree for C′, finally append the removed taxa to the tree under certain conditions.The CASS, the LNETWORK and the BIMLR construct subnetworks by the above description. Assume that the taxa set of Ci is Xi (1 ≤ i ≤ k). When constructing the subnetworks for Ci, they first remove a few taxa of Xi from each cluster in Ci, such that the result set C0 is compatible, then construct a rooted tree T for C0, next attach some new reticulate nodes to T, finally add a new leaf below each reticulate node and label it as the removed taxon. From the process, we can see that the removed taxa in Xi are very pivotal.The difference among the CASS, the LNETWORK and the BIMLR is the removed taxa. The CASS tries to remove a few taxa, i.e. by means of trial and error, it randomly removes some taxa, if it can construct a network representing the set of clusters, then it stops; otherwise it continues to remove other taxa. The LNETWORK removes the taxa computed by seed-growing algorithm. The BIMLR removes the incompatibility taxa with the maximal frequency. The CASS method aims at minimizing the number of reticulate nodes, while the LNETWORK and the BIMLR not only minimize the number of redundant of clusters but also let the reticulate nodes as few as possible.When constructing networks, the LNETWORK and the BIMLR find all networks representing the cluster set, mainly to reduce the number of redundant clusters in the resulting network and lessen the influence of the input data order on the resulting network. […]

Pipeline specifications

Software tools LNETWORK, BIMLR
Databases C-It
Application Phylogenetics