A navigation system for tree space
Vol. 20, no. 2, pp. 247-268, 2016. Regular paper.
Abstract The reconstruction of evolutionary trees from data sets on overlapping sets of species is a central problem in phylogenetics. Provided that the tree reconstructed for each subset of species is rooted and that these trees fit together consistently, the space of all parent trees that `display' these trees was recently shown to satisfy the following strong property: there exists a path from any one parent tree to any other parent tree by a sequence of local rearrangements (nearest neighbour interchanges) so that each intermediate tree also lies in this same tree space. However, the proof of this result uses a non-constructive argument. In this paper we describe a specific, polynomial-time procedure for navigating from any given parent tree to another while remaining in this tree space. The results are of particular relevance to the recent study of `phylogenetic terraces'.
Submitted: January 2016.
Reviewed: February 2016.
Revised: March 2016.
Accepted: March 2016.
Final: March 2016.
Published: April 2016.
Communicated by Tandy Warnow
article (PDF)