Ranked Subtree Prune and Regraft

Abstract

Phylogenetic trees are a mathematical formalisation of evolutionary histories between organisms, species, genes, cancer cells, etc. For many applications, e.g. when analysing virus transmission trees or cancer evolution, (phylogenetic) time trees are of interest, where branch lengths represent times. Computational methods for reconstructing time trees from (typically molecular) sequence data, for example Bayesian phylogenetic inference using Markov Chain Monte Carlo (MCMC) methods, rely on algorithms that sample the treespace. They employ tree rearrangement operations such as [Formula: see text] (Subtree Prune and Regraft) and [Formula: see text] (Nearest Neighbour Interchange) or, in the case of time tree inference, versions of these that take times of internal nodes into account. While the classic [Formula: see text] tree rearrangement is well-studied, its variants for time trees are less understood, limiting comparative analysis for time tree methods. In this paper we consider a modification of the classical [Formula: see text] rearrangement on the space of ranked phylogenetic trees, which are trees equipped with a ranking of all internal nodes. This modification results in two novel treespaces, which we propose to study. We begin this study by discussing algorithmic properties of these treespaces, focusing on those relating to the complexity of computing distances under the ranked [Formula: see text] operations as well as similarities and differences to known tree rearrangement based treespaces. Surprisingly, we show the counterintuitive result that adding leaves to trees can actually decrease their ranked [Formula: see text] distance, which may have an impact on the results of time tree sampling algorithms given uncertain "rogue taxa".

Keywords: Phylogenetics; Ranked trees; Time trees; Tree Rearrangements; Tree distance; Treespace.

Fig. 1

Two rooted $\text{SPR}$ moves. The cross marks the edge that is cut to prune the subtree ${T|}_v$ of T with leaf set $\{l_1,l_2\}$. In the tree on the left this subtree is reattached on the edge highlighted by a circle, connecting $l_5$ with its parent, and in the tree on the right the pruned subtree is reattached as child of a newly introduced root ${\rho }^{\prime }$

Fig. 2

A rooted tree $T_u$ on the left and a ranked tree $T=(T_u,\text{rank})$ on the right

Fig. 3

Rank move on the left, swapping the ranks of the nodes highlighted the leftmost tree. On the right an $\text{HSPR}$ move at rank 2 is illustrated, moving the subtree induced by $\{l_1,l_2\}$ by cutting the edge highlighted by a cross and re-attaching it at the edge highlighted by a circle

Fig. 4

$\text{HSPR}$ move pruning the subtree ${T|}_v$, moving it to the edge $(i^{+},i^{-})$. Dotted edges represent parts of the tree that potentially contain further nodes

Fig. 5

Path between T and $T_2$ as described in the proof of Theorem 4. Only subtrees involved in the moves given in the theorem are shown in this illustration

Fig. 6

Trees T and R of the counterexample to the weak cluster property in $\text{RSPR}$ and $\text{HSPR}$ in Theorem 7. The labels of the arrows indicate leaves that are pruned in the corresponding $\text{HSPR}$ moves

Fig. 7

Shortest $\text{HSPR}$ path between trees T and R. The subtree consisting of only the leaf $a_5$ is moved by the first and the last $\text{HSPR}$ move. The path displayed here does not preserve the shared cluster $\{a_1,a_2,a_3\}$ at rank three. The nodes inducing this cluster are highlighted in T and R. On this path only subtrees consisting of single leaves move

Fig. 8

Trees T and R with cherry $\{x,y\}$ at rank one and all moves on a path p from T to R that does not preserve the cherry as described in the proof of Theorem 9. The labels of the arrows indicate the leaves that are pruned and reattached by the corresponding $\text{HSPR}$ moves

Fig. 9

Trees T, $T^{\prime }$, and R on p, and alternative path $p^{\prime }$ from T to R via $T^{\prime \prime }$ at the bottom if T and $T^{\prime }$ are connected by an $\text{HSPR}$ move at rank k and the nodes of rank k and $k+1$ in T are connected by an edge, as explained in case 2.1. The dotted parts of the trees might contain further nodes and leaves

Fig. 10

Trees T, $T^{\prime }$, and R on p at the top, and alternative path $p^{\prime }$ from T to R via $T^{\prime \prime }$ at the bottom if T and $T^{\prime }$ are connected by an $\text{HSPR}$ move at rank k and the nodes of rank k and $k+1$ in T are not connected by an edge. The dotted parts of the trees might contain further nodes and leaves

Fig. 11

Trees T, $T^{\prime }$, and R on p, and alternative path $p^{\prime }$ from T to R via $T^{\prime \prime }$ at the bottom if T and $T^{\prime }$ are connected by an $\text{HSPR}$ move at rank $k+1$ and the nodes of rank k and $k+1$ in T are connected by an edge, The dotted parts of the trees might contain further nodes and leaves

Fig. 12

Trees T, $T^{\prime }$, and R on p at the top, and alternative path $p^{\prime }$ from T to R via $T^{\prime \prime }$ at the bottom if T and $T^{\prime }$ are connected by an $\text{HSPR}$ move at rank k and the nodes of rank k and $k+1$ in T are not connected by an edge. The dotted parts of the trees might contain further nodes and leaves

Fig. 13

Top: trees T and R with $\text{HSPR}$ distance greater than or equal to $\frac{n-1}{2}$ (Lemma 6). Bottom: Adding leaf $l_{n+1}$ to both T and R results in trees $T^{\prime }$ and $R^{\prime }$ that are connected by one $\text{HSPR}$ move that moves $l_1$