| Article ID: | iaor20114461 |
| Volume: | 111 |
| Issue: | 12 |
| Start Page Number: | 600 |
| End Page Number: | 604 |
| Publication Date: | Jun 2011 |
| Journal: | Information Processing Letters |
| Authors: | Caceres Alan Joseph J, Daley Samantha, DeJesus John, Hintze Michael, Moore Diquan, John Katherine St |
| Keywords: | random walk, trees |
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.