TY - JOUR

T1 - Exploring the Tiers of Rooted Phylogenetic Network Space Using Tail Moves

AU - Janssen, Remie

AU - Jones, Mark

AU - Erdős, Péter L.

AU - van Iersel, Leo

AU - Scornavacca, Celine

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

KW - Diameter

KW - Head-move operation

KW - Network space

KW - Phylogenetic network

KW - Rearrangement

KW - Tail-move operation

UR - http://www.scopus.com/inward/record.url?scp=85048594629&partnerID=8YFLogxK

U2 - 10.1007/s11538-018-0452-0

DO - 10.1007/s11538-018-0452-0

M3 - Article

AN - SCOPUS:85048594629

VL - 80

SP - 2177

EP - 2208

JO - Bulletin of Mathematical Biology

JF - Bulletin of Mathematical Biology

SN - 0092-8240

IS - 8

ER -