Exploring the tiers of rooted phylogenetic network space using tail moves
Remie Janssen Mark Jones Péter L. Erdős Leo van Iersel Celine Scornavacca


Persistent Sinai type diffusion in Gaussian random potentials with decaying 
spatial correlations
    Ralf Metzler
    December 30, 2023
=================================================================================================




Spaces of (subsets of) phylogenetic networks are known to be connected by several types of local moves, 
for example the rNNI and rSPR moves defined by Gambette et al. <cit.>, or the SNPR moves defined by Bordewich, Linz and Semple <cit.>.
Building on the concept of rSPR moves, we here propose a more restricted type of move: the tail move. 
Whereas rSPR moves can change either the starting point or the end point of an arc, a tail move can only move the starting point.
Gambette et al. prove that the space of all phylogenetic networks on a set X with k reticulations, which we call the k-th tier of X, is connected by rSPR moves.
Here we prove that, unless k=1 and |X|=2, the k-th tier is already connected when we only use tail moves.
Our proof also gives us a bound on the diameter of this space in terms of the rNNI-distance for networks with at least two leaves.




§ INTRODUCTION







§ DEFINITIONS AND PROPERTIES



 §.§ Phylogenetic networks

Phylogenetic networks are a generalisation of phylogenetic trees. The difference between the two is that in phylogenetic networks branches may recombine. In the network, such an event occurs at a particular node which we call a reticulation. The following definition gives names to all types of nodes we encounter in a phylogenetic network.


Let G be a directed acyclic graph, then we use the following terminology for the nodes of G. 


  * A node with in-degree 0 and out-degree 1 is called a root.

  * A node with in-degree 1 and out-degree ≥ 2 is called a tree node.

  * A node with in-degree ≥ 2 and out-degree 1 is called a reticulation.

  * A node with in-degree 1 and out-degree 0 is called a leaf.
 


We have now named all different kinds of nodes that can be found in a phylogenetic network. We now define such a network using this new terminology.


A phylogenetic network on a finite set X consists of the following:


  * A (connected) directed acyclic graph with no parallel edges and one root node, in which all other nodes are one of the following: a tree node, a reticulation, or a leaf.

  * a bijection between X and the leaf nodes of G.

A phylogenetic network is called binary if the total degree of each node is at most 3.


Note that this definition excludes internal nodes with in-degree 1 and out-degree 1. Suppressing all these nodes does not change the shape of the network, so their exclusion does not change the topological generality of the definition. 

Another topological note about this definition, regards the addition of connected to the restrictions on the network. This addition is not necessary, as having exactly one root and no directed cycles already implies connectedness of the network.

Phylogenetic networks are considered more complex if they are less tree-like. Therefore we need a definition of the tree-likeness of a network. A standard measure for phylogenetic networks is the reticulation number: the number of times branches recombine.


Let N be a phylogenetic network. The reticulation number of N is 

    ∑_v∈ R(N)(v)-1,

where R(N) denotes the set of reticulation nodes of N.


The reticulation number of binary networks is especially easy to compute, since it is equal to the number of reticulation nodes. The reticulation number is one way to define the complexity of a network. It is hence natural to study all networks with the same reticulation number.



Let X be a (finite) set of taxa. The k-th tier on X is the set of all binary phylogenetic networks with label set X containing k reticulation nodes. 


Although this definition could easily be given for arbitrary (non-binary) networks, we restrict to the binary case because our results apply to binary networks only. From this point on, we will only consider binary networks.



  §.§.§ Orders and Ancestors



In rooted trees and rooted networks, all edges are directed away from the root. We depict all phylogenetic networks and trees with the root at the top and the leaves at the bottom. In this representation all arcs are directed downward. In line with these conventions, we use the following terminology for `directions'.


Let u and v be nodes in a phylogenetic network, then we say u is above v and v is below u if u ≤ v in the order induced by the directed graph underlying the network.

Similarly, if e=(x,y) is an edge of the network and u a node, then we say that e is above u if y is above u and e is below u if x is below u. 


This definition is about order over possibly large distances in the network, the next is about directional relations over a short distance.


Let e=(u,v) be an arc of a phylogenetic network, then we say that u is the tail of e and v is the head of e. In this situation, we also say that u is a parent of v, or u is directly above v and v is a child of u or v is directly below u.


Note that in a rooted tree, there is always a unique (shortest) path between two nodes, and such a path always goes up, and then down. The node at which it switches from going up to going down is called the lowest common ancestor. In a phylogenetic network there is no unique node through which such paths go. Hence we will define a lowest common ancestor of two nodes, and directly after we prove that there is at least one such lowest common ancestor for any pair of vertices.


Let u and v be nodes of a phylogenetic network. A lowest common ancestor (LCA) of u and v is a node x (often denoted (u,v)) such that 

    x ≤ u  x ≤ v,

and for any other x' with the same property we have x≰x'.



For every pair of vertices u,v of a phylogenetic network there is at least one LCA.


Consider the set of nodes which are above u and v

    V={x∈ V(N): x≤ u , x≤ v },

then the LCAs of u and v are the maximal elements of this set under the induced partial order.
The set V is non-empty because it contains the root. It is finite because the network consists of a finite number of nodes. Hence the set of maximal elements is non-empty.



Let u and v be distinct nodes of a phylogenetic network. Then every LCA of these nodes is a tree node, and any node and edge under this LCA is above at most one of u and v.








 §.§ Local moves

To search the space of phylogenetic networks in an orderly way, we want to have a concept of locality. Several analogues of local tree moves have been defined for phylogenetic networks.<cit.> 
Such a local move typically changes the head, the tail, or both head and tail of one edge.


Let e=(u,v) and f be edges of a phylogenetic network. A head move of e to f consists of the following steps:


  * removal of edge e,

  * subdividing f with a new node v',

  * suppressing the in-degree 1, out-degree 1 node v,

  * adding the edge (u,v').

Head moves are only allowed if the resulting digraph is a phylogenetic network.
We say that the move is over distance d if there is a path from v to v' of graph length d+1 in the underlying undirected graph where both nodes exist (after step 2).



Let e=(u,v) and f be edges of a phylogenetic network. A tail move of e to f consists of the following steps:


  * removal of edge e,

  * subdividing f with a new node u',

  * suppressing the in-degree 1, out-degree 1 node u,

  * adding the edge (u',v).

Tail moves are only allowed if the resulting digraph is a phylogenetic network.
We say that the move is over distance d if there is a path from u to u' of graph length d+1 in the underlying undirected graph where both nodes exist (after step 2).


Note that connectedness after a move implies that all allowed moves are over a well defined finite distance. Because if this distance were undefined, i.e. no path between v and v' for head moves or u and u' in the case of tail moves, the resulting network would be disconnected.

It should also be noted that head moves are only possible for reticulation arcs, otherwise we create a node which does not fit any of the descriptions of Definition <ref>. This means that head moves are actually not part of the natural generalisation of SPR moves on trees, which consist of only tail moves. Here, we study the connectivity of the tiers of phylogenetic network space using only tail moves. We initially prove our connectivity result using the following theorem by Gambette et al.<cit.>, who study the rNNI move which is equivalent to either a head move or a tail move over distance 1.


Let N and N' be two rooted binary phylogenetic networks on tier k of X. Then there exists a sequence of rNNI moves turning N into N'. 


The fact that not all edges of a network can be moved by a tail move (e.g. edges with a reticulation node as tail) is quite important. Hence we want to have a notion of movability of edges.


Let e=(u,v) be an edge in a phylogenetic network. Then e is called non-movable if u is the root, if u is a reticulation, or if removal of e followed by subduing u creates parallel edges. Otherwise, it is called movable.


It is clear that there is only one situation in which removing an edge can result in parallel edges. This is when one would move the tail of an edge (u,v) and there is an arc from the parent of u to the child of u other than v. The situation is characterized in the following definition.


Let N be a phylogenetic network and let x,u,y be nodes of N. We say x,u and y form a triangle if there are arcs (x,u), (u,y) and (x,y). The edge (x,y) is called the long edge and (u,y) is called the bottom edge.


The interesting case in Definition <ref> is when the node on the side of the triangle is a tree node. Let x,u and y form a triangle in a network, and let v be the other child of u. The edge (u,v) is not movable because it creates parallel edges from x to y. 
The edge (u,y) is movable, however, 
and if it is moved sufficiently far up, the new edge (x,v) is also movable. 





The following remark is an important part of the arguments we use in the next section.


Let u be a tree node, then at least one of its child edges is movable. This is a direct consequence of Remark <ref>.


Note that movability does not consider whether there actually is a valid tail move of e: it only considers whether we can remove the tail without problems, not if we can also reattach it anywhere else. Of course a tail can always be attached to the root edge, but it is not certain that this results in a non-isomorphic network. The following remark characterizes valid moves.


The tail of an edge e=(u,v) can be moved to another edge f=(s,t) iff all the following hold:


  * e is movable, 

  * v is not above f, 

  * and t≠ v.

The first condition assures that the tail can be removed, the second that we do not create cycles, and the third that we do not create parallel edges.


The following lemma is related to the previous remarks, and will be used to find a tail that can be moved down sufficiently far.


Let x,y be nodes of a phylogenetic network N. Then there exists a movable edge in N that is not both above x and above y.


Consider an arbitrary LCA u of x and y. This LCA is a tree node, and both child edges are above at most one of x and y. Because at least one of the child edges of a tree node is movable (Remark <ref>), at least one of the child edges of the LCA has the desired properties.








§ HEAD MOVES REWRITTEN

This section presents the main result: the connectedness of tier k of phylogenetic networks on a fixed leaf set X using tail moves. Theorem <ref> tells us that it is connected by rNNI moves, i.e. head and tail moves over distance one. This means that, to achieve our goal, it suffices to prove that any distance-one head move can be replaced with a sequence of tail moves. To this end, we distinguish all different situations in which we can do such a head move.


Each distance one head move belongs to exactly one of the cases (a)-(f) in Figure <ref>. Note that the figure does not indicate whether u,w,x,y are distinct. It turns out that there are only a few cases in which u,w,x,y are not all distinct, and the head move is valid. Identification of x and y in move (a) and of u and y in move (d and f) are valid, but result in isomorphic networks. Identification of u and w in move (a) is the only identification which results in non-isomorphic networks. All other identifications make a head move invalid by introducing a cycle or parallel edges. 





It is easy to see that moves (c) and (e) as well as moves (d) and (f) are each others reversions. Because all tail moves are also reversible, we only have to show that head moves (a)-(d) can be rewritten as a sequence of tail moves.


We now treat all cases separately in the following lemma. We also take care of all the subcases given by the location of the tail of the edge whose head we move.


All head moves over distance one can be substituted by a sequence of tail moves, except for the head move in the network depicted in Figure <ref>.



In light of Remark <ref>, we distinguish two cases: u≠ w and u=w. All other nodes in Figure <ref> are distinct.


  *  u≠ w. 
In this case we can use the sequence of tail moves depicted in Figure <ref>. The sequence in the figure only depicts part of the network. In this part of the network, we do not find any directed cycles or parallel edges, but this does not imply the validity of the tail moves in the whole network. We have to check that validity of the head move implies the intermediate network does not contain directed cycles or parallel edges.

If the intermediate network were cyclic, then the (directed) cycle must involve edge (z',y), and there is a path from y to z'. This implies there is a path from y to v, which then implies there is a path from y to either u or to w. Because the tail move does not change any other part of the network, this path must also exist in the networks before and after the head move. This leads to a contradiction, because then one of these networks already contains a cycle, making the head move invalid. 

It is immediately clear that the moving tails do not connect to triangles by inspection of Figure <ref>. The only other possibility for creating parallel edges, is if x=y. But in that case the networks before and after the head move are isomorphic. We conclude that the intermediate network is valid, and that therefore the sequence of tail moves is valid.





  *  u=w. 
Note that u and v form a triangle together with the tree node z. In this situation, we cannot directly use the same sequence as before, since this sequence would create parallel edges. We can solve this problem in two ways.


  *  Using an extra tail. 
Instead of moving edge e directly, we first subdivide it by moving a tail to e. Then we can do the sequence of moves depicted in Figure <ref>. Barring the addition of the extra tail, the sequence of moves is quite similar to the moves in case <ref>.


  *  Destroying the triangle.
The bottom edge of the triangle, edge (z,v) is movable. If it is moved elsewhere, the situation changes to that of case <ref>. Do the sequence of moves for that case, and move the bottom edge of the triangle back.



Option <ref> is possible if there is at least one vertex above the triangle in addition to the root: move the bottom edge to the root. And, option <ref> can be used if there is a tree node somewhere not above the triangle.



The two networks to which neither of these conditions apply are shown in Figure <ref>. The first is the network on one leaf with two reticulations. In this network no head move leads to a different (non-isomorphic) network. The only non-trivial case is the excluded network with two leaves and one reticulation. The head move cannot be substituted by a sequence of tail moves, because there is no valid tail move. 






The idea of this substitution is to use an extra tail again. The proposed sequence is given in Figure <ref>.



The main problem is to find a usable tail: to use the sequence of moves, we need a tail that can be moved below either x or y. This is sufficient because of the symmetry of the situation and the reversibility of tail moves: if the movable edge is not above y, we do the sequence of moves in reverse order, where we switch the labels x and y.

Consider an LCA of x and y in Figure <ref>. At least one of the child edges of this LCA can be moved (Lemma <ref>), and this edge is not above both x and y. Hence we can move this tail down below one of these nodes (Remark <ref>).

Without loss of generality, let the movable edge (s,t) be above y and not above x. There are two situations in which the sequence of moves invalid: x is a tree node with children v and t, then one of the networks has parallel edges from x to t; and x=s then the sequence cannot be used as show, because it shows s' and x as distinct nodes. We now give solutions for both these problems.



  *  The children of x are v and t.
Note that we have (s,t) with s=(x,y) above y movable. Because there is an edge from x to t, there is a path from x to y. Hence x is an LCA of x and y, but then x must be the unique such LCA. We conclude s=x, which is the next case we treat.


  *  x=LCA(x,y).
Because x is the LCA of x and y and there is no path from v to y, x must be a tree node. Let the children of x be v and t, and let the parent of x be p.


  *  (x,v) is movable. In this case we can use a similar sequence as before, but without the addition of a tail: (x,v) to (y,z), (x',z) to (p,t).

  * (x,v) is  not movable. In this case p,x and t form a triangle. We employ a strategy to break the triangle similar to the strategy for Case <ref> of head move (a).


  * There is a node above the triangle besides the root. 
Move the bottom edge of the triangle to the root, we have reduced the problem to Case <ref> with p instead of x in the situation. Do the sequence of tail moves and move x back to the original position below p.

  * The node above the triangle is the root.
If there is no node above the triangle, then there is a tree node not above x (e.g. LCA(u,y)) and hence an edge e that can be moved to (x,t). With this move, we make (x,v) movable, and we can do the moves as in Case <ref>, after which we move e back to its original position.



In all sequences we gave, no directed cycles occur, because such cycles imply directed cycles in one of the networks before and after the head move. We conclude that any allowed head move of type (b) can be substituted by a sequence of tail moves.




This is the easiest case, as we can substitute the head move by exactly one tail move: (z,y) to (w,v), with labelling as in Figure <ref>. Parallel edges and directed cycles cannot occur because there are no intermediate networks. 















This head move is in some sense the most involved, as there are easy cases, and a very complicated cases. We exploit the following symmetry of this case: relabelling u↔ y and v↔ z transforms the network before the head move into the network after the head move. Let us start with the easiest case:


  *  Either (u,v) or (y,z) is movable.
Assume w.l.o.g. that (u,v) is movable and that the other child and parent of u are p and t, we move (u,v) to (y,z) and then (u',z) to (p,t).

  *  Either u or y is a tree node. 
If one of them is movable, we are in the previous situation, otherwise we do something similar: we ignore the triangle and restore it later as shown in Figure <ref>.




  * both u and y are reticulations.
In this case we try to recreate the situation of Case <ref> by adding a tail on one of the edges (u,v) and (y,z).


  *  The network contains at least two leaves.
We can pick two distinct leaves, at least one of which is below w. Suppose first that both of these leaves are below w, then an LCA of the leaves is also below the reticulation and one of its child edges can be used as the extra tail. 

If only one of the leaves is below the reticulation, then any LCA of the leaves has one edge that is not above w. If this edge can be moved, we can directly use it, otherwise, we first move the lower part of the triangle to the root, and then still use this edge.




  * The network contains one leaf, and w is not this leaf.
The only leaf is below the lowest reticulation r of the network, which is not z. By removing the lowest reticulation and the leaf below it, and then adding leaves to the loosened edges, we reduce to Case <ref>. The associated sequence of moves where we treat the parents of r as leaves substitutes the head move.



  * The only leaf in the network is w.
We have not found a way to solve this case `locally' as we did before. Go up from these reticulations to some nearest tree nodes. The idea, then, is to use one of these tree edges to do the switch as in the case we discussed previously (Figure <ref>). 

The result is that all reticulations on the path to the nearest tree node move with the tree edge. These reticulations can be moved back to the other side using the previously discussed moves. In particular we move the heads sideways using head move (b), and then we move them up using head move (f) where the main reticulation (z) is not the lowest reticulation in the network.



















Using Theorem <ref> and the above lemma, we directly get the connectivity result for tail moves.

Let N and N' be two rooted binary networks on the k-th tier of X. Then there exists a sequence of tail moves turning N into N', except if k=1 and |X|=2. 





§ DIAMETER BOUNDS





 Let N, N' be two networks with leaves labeled with X.
 Then an isomorphism between N and N' is a bijection ϕ: V(N) → V(N') such that 
 
  
  * Two nodes u,v ∈ V(N) are adjacent in N if and only if ϕ(u) and ϕ(v) are adjacent in N';
  
  * For any leaf u ∈ L(N), ϕ(u) is the leaf in L(N') that has the same label as u.
 
We say N and N' are isomorphic if there exists an isomorphism between N and N'.



Given a binary phylogenetic network N and a set of nodes Y in N,
we say Y is downward-closed if for any u ∈ Y, every child of u is in Y.


 Let N and N' be binary networks on X with the same number of reticulations,
such that N and N' are not the networks depicted in Figure <ref>.
 Let Y ⊆ V(N), Y' ⊆ V(N') be downward-closed sets of nodes such that
 L(N)⊆ Y, L(N') ⊆ Y', and N[Y] is isomorphic to N[Y'].
 Then there is a sequence of at most 4|N∖ Y| tail moves turning N into N'.


By setting Y = L(N) and Y' = L(N'), we note that such Y and Y' always exist.



We first observe that any isomorphism between N[Y] and N[Y'] maps reticulations (tree nodes) of N to reticulations (tree nodes) of N'.
Indeed, every node in N is mapped to a node in N' of the same out-degree, and the tree nodes are exactly those with out-degree 2.
It follows that Y and Y' contain the same number of reticulations and the same number of tree nodes. 
Furthermore, as N and N' have the same number of reticulations (and thus the same number of tree nodes), it also follows that V(N)∖ Y and V(N')∖ Y' contain the same number of reticulations and the same number of tree nodes.

 We prove the claim by induction on |N ∖ Y|.
 If  |N ∖ Y| = 0, then N = N[Y], which is isomorphic to N'[Y'] = N', and so there is a sequence of 0 moves turning N into N'.
 
 If  |N ∖ Y| = 1, then as Y is downward-closed, N ∖ Y consists of ρ_N, the root of N, and by a similar argument N '∖ Y' consists of ρ_N'.
 Let x be the only child of ρ_N, and note that in N[Y], x is the only node of in-degree 0, out-degree 2.
 It follows that in the isomorphism between N[Y] and N'[Y'], x is mapped to the only node in N'[Y'] of in-degree 0, out-degree 2, and this node is necessarily the child of ρ_N'.
 Thus we can extend the isomorphism between N[Y] and N'[Y'] to an isomorphism between N and N' by letting ρ_N be mapped to ρ_N'.
 Thus again there is a sequence of 0 moves turning N into N'.
 
 So now assume that |N ∖ Y| > 1.
 We consider three cases, which split into further subcases.
 In what follows, a lowest node of N ∖ Y (N' ∖ Y') is a node u in V(N)∖ Y (V(N')∖ Y') such that all descendants of u are in Y (Y').
 Note that such a node always exists, as Y (Y') is downward-closed.
 
 
  
  *   There exists a lowest node u' of N' ∖ Y' such that u' is a reticulation: In this case, let x' be the single child of u'.
 Then x' is in Y', and therefore there exists a node x ∈ Y such that x is mapped to x' by the isomorphism between N[Y] and N'[Y'].
 Furthermore, x has the same number of parents in N as x' does in N', and the same number of parents in Y as x' has in Y'.
 Thus x has at least one parent z such that z is not in Y.
 
 We now split into two subcases:
 
    
    
  *  z is a reticulation: in this case, let Y_1 = Y ∪{z} and Y_1' = Y' ∪{u'}, and extend the isomorphism between N[Y] and N[Y'] to an isomorphism between N[Y_1] and N[Y_1'], by letting z be mapped to u' (see Figure <ref>).
    We now have that Y_1 and Y_1' are downward-closed sets of nodes such that N[Y_1] is isomorphic to N[Y_1'], and L(N)⊆ Y_1, L(N') ⊆ Y_1'.
    Furthermore |N ∖ Y_1| = |N ∖ Y|-1.
    Thus by the inductive hypothesis, there is a sequence of 4|N ∖ Y_1| =  4|N ∖ Y|-4 tail moves turning N into N'.
    
    
 
    
  * z is not a reticulation: then z cannot be the root of N (as this would imply  |N ∖ Y| = 1), so z is a tree node. It follows that the edge (z,x) is movable, unless the removal of (z,x) followed by suppressing z creates parallel edges.
 
 
	
	 
  *  (z,x) is movable: In this case, let u be any reticulation in N ∖ Y (such a node must exist, as u' exists and N ∖ Y,  N' ∖ Y' have the same number of reticulations).
	 Let v be the child of u (which may be in Y), and observe that the edge (u,v) is not below x (as x ∈ Y and u ∉ Y). If v = x, then u is a reticulation parent of x that is not in Y, and by substituting v for z, we have case <ref>. So we may assume v ≠ x. Then it follows from Remark <ref> that the tail of (z,x) can be moved to (u,v).	 
	 Let N_1 be the network derived from N by applying this tail move, and let z_1 be the new node created by subdividing (u,v) during the tail move (see Figure <ref>). Thus, N_1 contains the edges (u,z_1), (z_1,v), (z_1,x).
     (Note that if z is immediately below u in N i.e. z=v, then in fact N_1 = N. In this case we may skip the move from N to N_1, and in what follows substitute z for z_1.)
     
     
     Note that (z_1,v) is movable in N_1 (since the parent u  of z is a reticulation node, and therefore deleting u and suppressing z_1 cannot create parallel edges). Let a be one of the parents of u in N_1. Then the tail of (z_1,v) can be moved to (a,u) (as u ≠ v, and (a,u) is not below v  as this would imply a cycle in N_1).
    
     So now let N_2 be the network derived from N_1 by applying this tail move (again see Figure <ref>). In N_2, the reticulation u is the parent of x (as z_1 was suppressed), and thus case <ref> applies to N_2 and N'. Therefore there exists a sequence of 4|N ∖ Y|-4 tail moves turning N_2 into N'. As N_2 is derived from N by two tail moves, there exists a sequence of 4|N ∖ Y|-2 tail moves turning N into N'.
     
         
	 

	 
	 
	 
  * The removal of (z,x) followed by suppressing z creates parallel edges: 

	 Then there exists nodes c ≠ x, d ≠ x such that c,d,z form a triangle with long edge (c,d).
	 As c has out-degree 2 it is not the root of N, so let b denote the parent of c.
	 
	    
	    
  *   b is not the root of N:   In this case, let a be a parent of b in N. Observe that the edge (a,b) is not below d and that b ≠ d. Furthermore, (c,d) is movable since c is not a reticulation or the root, and there is no edge (b,d) (such an edge would mean b has in-degree 3, as the edges (c,d) and (z,d) exist).
	    It follows that the tail of (c,d) can be moved to (a,b)  (again using Remark <ref>).	    
	    Let N_1 be the network derived from N by applying this tail move (see figure <ref>). 
	    
	    Observe that in N_1 we now have the edge (b,z) (as c was suppressed), and still have the edge (z,d) but still do not have the edge (b,d). Thus, deleting (z,x) and suppressing z will not create parallel edges, and so (z,x) is movable in N_1.	   
	    Thus case <ref> applies to N_1 and N', and so there exists a sequence of 4|N ∖ Y|-2 tail moves turning N_1 into N'.
	    As N_1 is derived from N by a single tail move, there exists a sequence of 4|N ∖ Y|-1 tail moves turning N into N'.
	    
               

       
  *  b is the root of N: In this case, we observe that 

	    if d ∈ Y then every reticulation in N is in Y. This contradicts the fact that N∖ Y and N'∖ Y' contain the same number of reticulations. Therefore we may assume that d ∉ Y.
	    Then we may proceed as follows.
	    Let N_1 be the network derived from Y by moving the head of (c,d) to (z,x) (see Figure <ref>).
	    We observe that this move cannot create a cycle (such a cycle is only possible if there is a path in N  from x to c, a contradiction as x ∈ Y, c ∉ Y), and cannot create parallel edges (such parallel edges would have to be out-edges of z, and this does not happen as one of the out-neighbors of z is the newly created node subdividing (z,x)).
	    Thus, this is a valid head move. 
	    Furthermore, this is a head move of type (a), and therefore can be replaced with a sequence of 4 tail moves.
	    
	    Observe that in N_1,  x has a parent not in Y which is a reticulation, and that N_1[Y] = N[Y]. Then case <ref> applies to N_1 and N', and so there exists a sequence of 4|N ∖ Y|-4 tail moves turning N_1 into N'.
	    As N_1 can be derived from N by at most 4 tail moves, it follows that there exists a sequence of 4|N ∖ Y| tail moves turning N into N'.
        
                       
        
        
	    
	 
	 
 
    
    
 
  *  There exists a lowest node u of N ∖ Y such that u is a reticulation: By symmetric arguments to case <ref> , we have that there is a sequence of at most 4|N∖ Y| tail moves turning N' into N. As all tail moves are reversible, there is also a sequence of at most 4|N∖ Y| tail moves turning N into N'.
 
 
  * Every lowest node of N ∖ Y and every lowest node of N'∖ Y' is not a reticulation: As |N ∖ Y| > 1, we have that in fact every lowest node of N ∖ Y and every lowest node of N'∖ Y' is a tree node. Then we proceed as follows. Let u' be an arbitrary lowest node of N' ∖ Y', with x' and y' its children.

  Then x',y' are in Y', and therefore there exist nodes x,y ∈ Y such that x (y) is mapped to x' (y') by the isomorphism between N[Y] and N'[Y'].
 Furthermore, x has the same number of parents in N as x' does in N', and the same number of parents in Y as x' has in Y'.
 Thus x has at least one parent not in Y. Similarly, y has at least one parent not in Y.
 
    
     
  *  x and y have a common parent u not in Y: In this case, let Y_1 = Y ∪{u} and Y_1' = Y' ∪{u'}, and extend the isomorphism between N[Y] and N[Y'] to an isomorphism between N[Y_1] and N[Y_1'], by letting u be mapped to u' (see figure <ref>).
    We now have that Y_1 and Y_1' are downward-closed sets of nodes such that N[Y_1] is isomorphic to N[Y_1'], and L(N)⊆ Y_1, L(N') ⊆ Y_1'.
    Furthermore |N ∖ Y_1| < |N ∖ Y|.
    Thus by the inductive hypothesis, there is a sequence of 4|N ∖ Y_1| =  4|N ∖ Y|-4 tail moves turning N into N'.
    

        
    
    
  * x and y do not have a common parent not in Y: In this case, let z_x be a parent of x not in Y, and let z_y be a parent of y not in Y. Recall that z_x and z_y are both tree nodes. It follows that either one of (z_x,x), (z_y,y) is movable, or deleting (z_x,x) and suppressing x  (deleting (z_y,y) and suppressing y) would create parallel edges.
    
	
	  
  *   (z_x,x), is movable:  in this case, observe that the edge (z_y,y) is not below x (as x ∈ Y and z_Y ∉ Y), and that x ≠ y.  Then by Remark <ref>, the tail of (z_x,x) can be moved to (z_y,y).
	  
	 Let N_1 be the network derived from N by applying this tail move (see Figure <ref>).
	 Then as x and y have a common parent in N_1 not in Y, and as N_1[Y] = N[Y], we may apply the arguments of case <ref>  to show that there exists a sequence of 4|N ∖ Y|-4 tail moves turning N_1 into N'. As N_1 is derived from N by a single tail move, there exists a sequence of 4|N ∖ Y|-3 tail moves turning N into N'.
	 
     
     
	 
  *   (z_y,y) is movable: By symmetric arguments to case <ref>, we have that there is a sequence of at most  4|N ∖ Y|-3  tail moves turning N into N'.
	 
	 
  * Neither (z_x,x) nor (z_y,y) is movable: 

	 In this case, there must exist nodes d_x,c_x, d_y, c_y such that 

	 c_x,d_x,z_x form a triangle with long edge (c_x,d_x), and  c_y,d_y,z_y form a triangle with long edge (c_y,d_y).
	 Moreover, as z_x,z_y are different nodes with one parent each, c_x ≠ c_y. It follows that one of c_x,c_y is not the child of the root of N. Suppose without loss of generality that c_x is not the child of the root. Then there exist nodes a_x,b_x and edges (a_x,b_x), (b_x,c_x).
	 
	 By similar arguments to those used in Case <ref>, the tail of (c_x,d_x) can be moved to (a_x,b_x), and in the resulting network N_1, (z_x,x) is movable (see Figre <ref>).
	 Thus case <ref> applies to N_1 and N', and so there exists a sequence of 4|N∖ Y|-2 tail moves turning N_1 into N'. As N_1 is derived from N by a single tail move, there exists a sequence of 4|N∖ Y|-1 tail moves turning N into N'.
     
          
	
    
 

 
 



 By setting Y = L(N) and Y' = L(N'), we have the following:
 
 Let N and N' be binary networks on X with the same number of reticulations,
such that N and N' are not the networks depicted in Figure <ref>.
 Then there is a sequence of at most 4(|N|-|X|) tail moves turning N into N'.





§ TAIL DISTANCE



 §.§ Relation with other distances













 §.§ Tail1 distance

Comparing rNNI and tail moves directly might be hard because rNNI moves are more local. To make this comparison easier, we would like to consider local tail moves separately. The following lemma indicates how restricting to distance-1 tail moves influences our results.


Let e=(u,v) to f=(s,t) be a valid tail move, then there is a sequence of distance-1 tail moves resulting in the same network.


Note that there exist (possibly non-unique) directed paths u←(u,s)→ s for any choice of (u,s). We prove that a tail move of e to any edge on either path is valid, this gives a sequence of distance-1 tail moves.

Let g=(x,y) be an edge of either path. We first use a proof by contradiction to show that the move to g cannot create cycles, then we prove that we do not create parallel edges.

Suppose moving e to g creates a cycle, then this cycle must involve the new edge e' from g to v. This means there is a path from v to x. However, x is above u or above s, which means that either the begin situation is not a phylogenetic network, or the move e to f is not valid. From this contradiction, we conclude that the move of e to g does not create cycles.

Note that e is movable, because the move of e to f is valid. Hence the only way to create parallel edges, is by moving e=(u,v) to an edge g=(x,y) with y=v. It is clear that g is not in the path u←(u,s), as this would imply there is a cycle in the original network. Hence g must be on the other path. If f=g, then the original move of e to f would create parallel edges, and if g is above f, the original move moves e to below e creating a cycle. We conclude that there cannot be an edge g=(x,y) on either path such that y=v, hence we do not create parallel edges.





Lemma <ref> gives an upper bound on the number of distance-1 tail moves needed to get the same result as one general tail move. 






 §.§ Computation

























spmpsci


