Home Issues About JGAA Instructions for Authors
 
DOI: 10.7155/jgaa.00447
Computing phylogenetic trees using topologically related minimum spanning trees
Vol. 21, no. 6, pp. 1003-1025, 2017. Regular paper.
Abstract Choi et al.(Choi et al. JMLR, 2011) introduced a minimum spanning tree (MST)-based method called CLGrouping, for constructing tree-structured probabilistic graphical models, a statistical framework that is commonly used for inferring phylogenetic trees. While CLGrouping works correctly if there is a unique MST, we observe an indeterminacy in the method in the case that there are multiple MSTs. We demonstrate the indeterminacy of CLGrouping using a synthetic quartet tree and a tree over primate genera. The indeterminacy of CLGrouping can be removed if the input MST shares a topological relationship with the corresponding phylogenetic tree. We introduce so-called vertex order based MSTs (VMSTs) that are guaranteed to have the desired topological relationship. We relate the number of leaves in the VMST to the degree of parallelism that is offered by CLGrouping. We provide polynomial-time algorithms for constructing VMSTs and for selecting a VMST with the optimal number of leaves.
Submitted: November 2016.
Reviewed: April 2017.
Revised: May 2017.
Accepted: August 2017.
Final: September 2017.
Published: October 2017.
Communicated by Fabio Vandin
article (PDF)
BibTeX