Home Issues About JGAA Instructions for Authors
 
DOI: 10.7155/jgaa.00392
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)
BibTeX