Walks in phylogenetic treespace

We prove that the spaces of unrooted phylogenetic trees are Hamiltonian for two popular search metrics: Subtree Prune and Regraft (SPR) and Tree Bisection and Reconnection (TBR). Further, we make progress on two conjectures of Bryant on searching phylogenetic treespace: treespace under the Nearest Neighbor Interchange (NNI) metric has a 2-walk, and there exist SPR neighborhoods without complete NNI walks.

► We prove that treespace is Hamiltonian for SPR and TBR metrics. ► Under the NNI metric, we show that treespace has a 2-walk. ► Towards Bryantʼs conjecture, there exists SPR neighborhoods without an NNI walk.