Uprooted Phylogenetic Networks

Abstract

The need for structures capable of accommodating complex evolutionary signals such as those found in, for example, wheat has fueled research into phylogenetic networks. Such structures generalize the standard model of a phylogenetic tree by also allowing for cycles and have been introduced in rooted and unrooted form. In contrast to phylogenetic trees or their unrooted versions, rooted phylogenetic networks are notoriously difficult to understand. To help alleviate this, recent work on them has also centered on their "uprooted" versions. By focusing on such graphs and the combinatorial concept of a split system which underpins an unrooted phylogenetic network, we show that not only can a so-called (uprooted) 1-nested network N be obtained from the Buneman graph (sometimes also called a median network) associated with the split system [Formula: see text] induced on the set of leaves of N but also that that graph is, in a well-defined sense, optimal. Along the way, we establish the 1-nested analogue of the fundamental "splits equivalence theorem" for phylogenetic trees and characterize maximal circular split systems.

Keywords: Buneman graph; Circular split system; Closure; Median network; PC-trees; Phylogenetic network.

Fig. 1

a A phylogenetic network N on $X=\{1,\dots ,8\}$. The root is labeled by $\mathit{\rho }$, all edges are directed downwards, and vertices $h_1$ and $h_2$ represent hypothesized reticulate evolutionary events. b The uprooted version $N^{\prime }:=U(N)$ of N. c An unrooted phylogenetic network on X in the form of the Buneman graph $G(\mathrm{\Sigma }(N))$ on the split system $\mathrm{\Sigma }(N)$ induced by $N^{\prime }$. The dashed line indicates the split 234|15678—see Sect. 2 for details

Fig. 2

A 1-nested network for which the induced split system is $\mathrm{\Sigma }(N^{\prime })$ where $N^{\prime }$ is the uprooted network in Fig. 1b. As in Fig. 1c, the dashed line indicates the split 234|15678

Fig. 3

For a simple level-1 network on $\{1,\dots ,6\}$, we depict the splits $S_1$ and $S_2$ in terms of two straight bold lines and the four splits that make up $\mathit{\iota }(S_1,S_2)$ in terms of four dashed lines

Fig. 4

a An illustration of the reduction process considered in the proof of Case (a) of Theorem 1. b Again for that theorem, the graph $G^{\prime }$ obtained from N by adding subdivision vertices r and $r^{\prime }$

Fig. 5

For $k=6$, we depict in a the Buneman graph $G({\mathrm{\Sigma }}_6)$ in terms of bold and dashed edges and the associated 6-marguerite $M({\mathrm{\Sigma }}_6)$ in terms of bold edges. In addition, we indicated the vertex ${\mathit{\varphi }}_1^2$ of $G({\mathrm{\Sigma }}_6)$. We picture the 8-marguerite in b and indicate again the vertex ${\mathit{\varphi }}_1^2$