Reconstructing Tree-Child Networks from Reticulate-Edge-Deleted Subnetworks

Abstract

Network reconstruction lies at the heart of phylogenetic research. Two well-studied classes of phylogenetic networks include tree-child networks and level-k networks. In a tree-child network, every non-leaf node has a child that is a tree node or a leaf. In a level-k network, the maximum number of reticulations contained in a biconnected component is k. Here, we show that level-k tree-child networks are encoded by their reticulate-edge-deleted subnetworks, which are subnetworks obtained by deleting a single reticulation edge, if [Formula: see text]. Following this, we provide a polynomial-time algorithm for uniquely reconstructing such networks from their reticulate-edge-deleted subnetworks. Moreover, we show that this can even be done when considering subnetworks obtained by deleting one reticulation edge from each biconnected component with k reticulations.

Keywords: Network encoding; Phylogenetic network; Reticulate-edge-deleted subnetworks; Tree-child networks.

Fig. 1

(Color figure online) A level-4 tree-child network N on the set of species $X=\{a,\dots ,n\}$. Though N is a directed acyclic graph, the edge directions are omitted to avoid cluttering. The arcs are directed downwards. The leaf pair $\{e,f\}$ is a cherry since they share a common parent. The leaf pair $\{a,b\}$ is a reticulated cherry since the parent of a is also the parent of the parent of b

Fig. 2

Networks N and $N^{\prime }$ are non-isomorphic but have the same lower-level subnetworks. Hence, any class containing N and $N^{\prime }$ is not level-reconstructible. However, these networks have different subnetworks: $N_1$ is a subnetwork of N but not of $N^{\prime }$; $N_2$ is a subnetwork of $N^{\prime }$ but not of N. So $\{N,N^{\prime }\}$ is subnetwork-reconstructible

Fig. 3

(Color figure online) Three networks $N_1,N_2,N_3$ with their respective maximum subnetworks $N_1^{\prime },N_2^{\prime },N_3^{\prime }$ obtained by deleting the red reticulation edge and subsequently cleaning up. The red reticulation edge in $N_1$ is valid; however, the red dashed reticulation edges in $N_2$ and $N_3$ are invalid. The subnetwork $N_2^{\prime }$ contains 4 fewer nodes and 6 fewer edges than $N_2$, and $N_3^{\prime }$ contains 3 fewer nodes and 5 fewer edges than $N_3$

Fig. 4

(Color figure online) Visual aid for the proof of Lemma 3. The left case is when $N^{\prime }$ contains a reticulation t that is a parent of a reticulation r. The right case is when a tree node t is a parent of two reticulations. In either case, the red dashed edge (u, v) must be inserted in these particular places to obtain N, and in either case N is not tree-child

Fig. 5

A tree-child network N, its maximum subnetworks $N^1,N^2$ obtained from deleting edges 1 and 2, respectively, together with their blob trees

Fig. 6

a A portion of the network showing a lowest reticulated cherry shape in a blob B. b The same portion of the network after isolating the reticulate cherry shape $⟨x,y⟩$. Note here that $p_x$ is a pure node in the subnetwork, but $p_x$ is not a pure node in the original network

Fig. 7

Visual aid for Lemma 10 proof. a Proof of Claim 2. Cutting or isolating $⟨x,y⟩$ results in subnetworks where $p_s$ and p lie in the blob containing $r^{\prime }$. b Proof of the paragraph after Claim 2, which shows that $P^{\prime }\cap P^{\prime \prime }=\mathrm{\varnothing }$

Fig. 8

(Color figure online) $N_i$ for $i=1,2,\dots ,8$ refers to the MLLS of a level-4 tree-child network N obtained by deleting the reticulation edge i.  BT(N) is the blob tree of the network N and $BT(N_i)$ is the blob tree of $N_i$ for each i. The foundation nodes are highlighted in yellow

Fig. 9

(Color figure online) A network N on 4 leaves. The shortest ac up-down distance is 5 (blue dash-dotted path); however, the shortest ac distance in the underlying undirected graph of N is 4 (red dashed path)

Fig. 10

All possible shapes on two leaves $\{x,y\}$ (up to permuting x and y). The dashed line indicates that any ib up-down path has length at least 2

Fig. 11

(Color figure online) Proof visual of Theorem 4, $d_N(x,y)\ge 5$ case. The red dashed up-down path in BT(N) represents the trajectory of every xy up-down path in N, and consequently, the set of blobs $\mathcal{B}$ through which every xy up-down path passes. A zoomed-in portion of the two particular blob nodes illustrates the entry point $t_B$ and exit $h_B$ in N, and the case for when both points can be reticulations

Fig. 12

(Color figure online) An example of 2 shortest xy up-down paths in N, whenever $d_N(x,y)=4$. One up-down path (red dashed) is (x, u), (u, w), (w, v), (v, y) and the other (blue dash-dotted) $(x,u),(u,w^{\prime }),(w^{\prime },v),(v,y)$ (disregarding directions)

Fig. 13

a Two non-isomorphic level-1 networks with girth 3 that share the same subnetworks. b Three non-isomorphic level-1 networks with girth 4 that share the same subnetworks

Fig. 14

The three cases for H(x, y) in Lemma 17. Deleting edge (a, c) yields $\lambda (x,y)$, $\lambda (y,x)$, and $\Pi (x,y)$, respectively

Fig. 15

(Color figure online) Three MLLSs $N_1^{\mathit{mlls}},N_2^{\mathit{mlls}}$, and $N_3^{\mathit{mlls}}$ of a level-2 tree-child network containing exactly two level-2 blobs. The three MLLSs contain $\Lambda (x,y),H(x,y)$, and $\Pi (x,y)$, respectively. We reconstruct the blob B with pure node p in $N_3^{\mathit{mlls}}$ initially and then reconstruct it in the other MLLSs. In $N_3^{\mathit{mlls}}$, nodes a, c are inserted directly above x, y, respectively, and an edge (a, c) is added (red dashed edge). To reconstruct B in $N_1^{\mathit{mlls}}$ the pendant subnetwork rooted at p is replaced by the reconstructed pendant subnetwork

Fig. 16

(Color figure online) An example of the algorithm TCMLLS-Reconstruction($\{N_1,N_2,N_3,N_4\}$). Initially, the common pendant subnetworks of the four input networks are determined by looking at their blob trees. In this case, this is the cherry $\Lambda (v,w)$ (line 1). Upon reducing the cherry $\Lambda (v,w)$ to a leaf $\{v,w\}$ in all the MLLSs, the lowest foundation node is found to be $\{\{v,w\},x,y,z\}$. We find a leaf pair $\{\{v,w\},x\}$ specified in line 4 of the algorithm. Since $N_3$ contains $\Pi (\{v,w\},x)$, we reconstruct this blob in $N_3$, shown by the red dashed edge (line 5). After reconstructing the same blob in all the other networks $N_1,N_2$ and $N_4$, we see that the networks are all isomorphic (we enter the if statement of line 12). The algorithm then returns the network N

Fig. 17

A valid network with a tessellating crown blob and its blob tree. Deleting any of the reticulation edges keeps the original blob biconnected, and hence, it will not affect the blob tree

Fig. 18

(Color figure online) a 2-reticulated cherry on $\{x,y\}$. b MLLS where the red dashed edge is deleted from a. We have two options, $a_1,a_2$, for inserting the reticulation edge

Fig. 19

Two level-2 networks $N_1$ and $N_2$ are non-isomorphic but have the same lower-level subnetworks. In general, invalid networks are not level-reconstructible