Exploring the Tiers of Rooted Phylogenetic Network Space Using Tail Moves

Abstract

Popular methods for exploring the space of rooted phylogenetic trees use rearrangement moves such as rooted Nearest Neighbour Interchange (rNNI) and rooted Subtree Prune and Regraft (rSPR). Recently, these moves were generalized to rooted phylogenetic networks, which are a more suitable representation of reticulate evolutionary histories, and it was shown that any two rooted phylogenetic networks of the same complexity are connected by a sequence of either rSPR or rNNI moves. Here, we show that this is possible using only tail moves, which are a restricted version of rSPR moves on networks that are more closely related to rSPR moves on trees. The connectedness still holds even when we restrict to distance-1 tail moves (a localized version of tail moves). Moreover, we give bounds on the number of (distance-1) tail moves necessary to turn one network into another, which in turn yield new bounds for rSPR, rNNI and SPR (i.e. the equivalent of rSPR on unrooted networks). The upper bounds are constructive, meaning that we can actually find a sequence with at most this length for any pair of networks. Finally, we show that finding a shortest sequence of tail or rSPR moves is NP-hard.

Keywords: Diameter; Head-move operation; Network space; Phylogenetic network; Rearrangement; Tail-move operation.

Fig. 1

(Color figure online) Starting with the rooted phylogenetic network on the left, if we move the tail of (u, v) to (x, y) we produce the network in the middle. If we instead move the head of (u, v) to (x, y), we produce the network on the right

Fig. 2

(Color figure online) A head move as described in Definition 2.5

Fig. 3

(Color figure online) A tail move as described in Definition 2.6

Fig. 4

An unrootable unrooted network

Fig. 5

(Color figure online) Illustration of all possible distance-1 head moves: a sideways movement below a tree node, b sideways movement above a reticulation, c downward movement through a tree node, d downward movement through a reticulation, e upward movement through a tree node, f upward movement through a reticulation

Fig. 6

(Color figure online) Proof of Lemma 3.3: the sequence of tail moves needed to simulate head move (a) in Case 1. Moving edges are dash-dotted before a move, and dashed after a move

Fig. 7

(Color figure online) Proof of Lemma 3.3: the sequence of tail moves used to simulate head move (a) in Case 2. The “extra tail” s of edge (s, t) is used in the sequence of moves: (s, t) to (z, y), $(s^{\prime },y)$ to (v, x), $(s^{\prime \prime },x)$ to (z, t) and $(s^{\prime \prime \prime },t)$ to (p, r). Here, p and r are, respectively, the parent and (other) child of s in the network before the head move

Fig. 8

(Color figure online) The networks for which there are no valid tail moves to simulate a distance-1 head move of type (a). Left: The network with one leaf and 2 reticulations where all valid head moves give isomorphic networks. Right: A network in which one non-trivial head move of type (a) is possible. There are no non-trivial tail moves for this network, therefore the head move cannot be simulated by tail moves

Fig. 9

(Color figure online) Proof of Lemma 3.3: the sequence of tail moves used to simulate head move (b). The moving edges are coloured, and the colouring of the edges is consistent throughout the sequence. The tail of the extra edge (light blue) is first moved to (x, v), then the orange edge $(s^{\prime },v)$ is moved to (y, z), then the green edge $(s^{\prime \prime },z)$ is moved to (x, t), and finally the light blue edge $(s^{\prime \prime \prime },t)$ (the “extra tail”) is moved back

Fig. 10

(Color figure online) Proof of Lemma 3.3: the sequence of tail moves used to simulate head move (d) in Case 3iii. All reticulations on the path to the nearest tree node above it move with it to the other side

Fig. 11

From left to right: a mycorrhizal forest $M=(\mathcal{T},R)$, its tree components $\mathcal{T}=(T_1,T_2)$ and the root component R

Fig. 12

Proof of Lemma 4.6, Case 1a: If $u^{\prime }$ is a lowest reticulation in $N^{\prime }\backslash Y^{\prime }$ with child $x^{\prime }$, and the node $x\in Y$ corresponding to $x^{\prime }$ has a reticulation parent z in $N\backslash Y$, then we may add z to Y and $u^{\prime }$ to $Y^{\prime }$

Fig. 13

(Color figure online) Proof of Lemma 4.6, Case 1(b)i: If (z, x) is movable, we may move the tail of (z, x) to (u, v) so that the parent $z_1$ of x is below u, then move the tail of $(z_1,v)$ so that the reticulation u becomes a parent of x

Fig. 14

(Color figure online) Proof of Lemma 4.6, Case 1(b)iiA: If (z, x) is not movable because of the triangle with long edge (c, d), and the parent of c is not the root of N, then we move the tail of (c, d) ‘further up’ in order to make (z, x) movable

Fig. 15

(Color figure online) Proof of Lemma 4.6, Case 1(b)iiB: Note that the set of tail moves depicted is equivalent to moving the head of (c, d) to (z, x). After this sequence of moves, x now has a reticulation parent

Fig. 16

(Color figure online) Proof of Lemma 4.6, Case 3a: If $u^{\prime }$ is a lowest reticulation in $N^{\prime }\backslash Y^{\prime }$ with children $x^{\prime },y^{\prime }$, and the nodes $x,y\in Y$ corresponding to $x^{\prime },y^{\prime }$ share a reticulation parent u in $N\backslash Y$, then we may add u to Y and $u^{\prime }$ to $Y^{\prime }$

Fig. 17

(Color figure online) Proof of Lemma 4.6, Case 3(b)i: If $(z_x,x)$ is movable, we may move the tail of $(z_x,x)$ to $(z_y,y)$ so that x and y share a parent

Fig. 18

(Color figure online) Proof of Lemma 4.6, Case 3(b)iii: If neither $(z_x,x)$ or $(z_y,y)$ is movable, we can make at least one of them movable by moving the long edge of its triangle “further up”

Fig. 19

The SPR move used to remove redundant terminal component B. The big circle represents all of U except for B. Note that in the unrooted network on the right, B is not a redundant terminal component anymore, and no extra redundant terminal components have been created

Fig. 20

The re-orientation of the bottom edge of a triangle, all of whose nodes are above Y

Fig. 21

(Color figure online) The tail move used in the proof of Case 3a in the proof of Theorem 4.22

Fig. 22

Two networks for which subtree reduction does not preserve tail-move distance