Labellable Phylogenetic Networks

Abstract

Phylogenetic networks are mathematical representations of evolutionary history that are able to capture both tree-like evolutionary processes (speciations) and non-tree-like 'reticulate' processes such as hybridization or horizontal gene transfer. The additional complexity that comes with this capacity, however, makes networks harder to infer from data, and more complicated to work with as mathematical objects. In this paper, we define a new, large class of phylogenetic networks, that we call labellable, and show that they are in bijection with the set of 'expanding covers' of finite sets. This correspondence is a generalisation of the encoding of phylogenetic forests by partitions of finite sets. Labellable networks can be characterised by a simple combinatorial condition, and we describe the relationship between this large class and other commonly studied classes. Furthermore, we show that all phylogenetic networks have a quotient network that is labellable.

Keywords: Encoding; Orchard; Phylogenetic network; Tree-based.

Fig. 1

A tree that has been labelled according to the algorithm in Erdős and Székely (1989), and its corresponding partition for which the sets are sets of sibling vertices. This labelling algorithm is a special case of that given later for networks, in Algorithm 1

Internal vertex labelling algorithm

Fig. 2

A network substructure that is not labellable, since the vertices labelled 3 and 4 share the same set of parents

Fig. 3

A labelled, degenerate phylogenetic network. This network has the associated cover $\{\{1\},\{3\},\{2,7\},\{4,7\},\{5,8,9\},\{6,8\}$, $\{10,11\}\}$

Network from an expanding cover

Fig. 4

Construction of a network from the expanding cover $\mathcal{C}=\{\{2\},\{5\},\{1,6\},\{4,8\},\{3,6,9\},\{10\},\{7,11\},\{8,12\}\}$ described in Example 4.5. The first step, consisting of five isolated vertices, is omitted. Note that the labels of the reticulate vertices (6 and 8) appear twice in $\mathcal{C}$

Fig. 5

Left: A labellable network that is not orchard. It can be seen to not be orchard because it does not have any cherries or reticulated cherries. Right: A labellable network that is not tree-based. This can be seen because it has a substructure called a zig-zag path, which prevents a network from being tree-based (Zhang 2016), namely between the reticulate vertices 5 and 7 along the path $5-3-6-4-7$

Fig. 6

Relationships between labellable networks and some other classes. This figure applies for non-degenerate networks (non-binary networks permitted)

Fig. 7

An unlabellable network N on the left, with the results of normalising, and taking the derived network. The pendant triangle represents an arbitrary tree. (i) shows its derived network $\mathcal{D}(N)$, where [p] denotes the $\sim$ equivalence class $\{p_1,p_2\}$, and (ii) shows the normalisation of that derived network, $\mathcal{N}(\mathcal{D}(N))$. The bottom row shows the normalisation process described in Francis et al. (2021). (iii) shows the visible vertices and related edges (the first step of the normalisation process), and (iv) shows the complete normalised network $\mathcal{N}(N)$ with degree-two vertices suppressed. Note that $\mathcal{N}(N)\ne \mathcal{N}(\mathcal{D}(N))$ for this example