The complexity of inferring a minimally resolved phylogenetic supertree
Research output: Contribution to journal › Article
Abstract
A recursive algorithm by Aho et al. [SIAM J. Comput., 10 (1981), pp. 405421] forms the basis for many modern rooted supertree methods employed in Phylogenetics. However, as observed by Bryant [Building Trees, Hunting for Trees, and Comparing Trees: Theory and Methods in Phylogenetic Analysis, Ph.D. thesis, University of Canterbury, Christchurch, New Zealand, 1997], the tree output by the algorithm of Aho et al. is not always minimal; there may exist other trees which contain fewer nodes yet are still consistent with the input. In this paper, we prove strong polynomialtime inapproximability results for the problem of inferring a minimally resolved supertree from a given consistent set of rooted triplets (MINRS). Furthermore, we show that the decision version of MINRS is NPhard for any fixed positive integer q >= 4, where q is the number of allowed internal nodes, but lineartime solvable for q <= 3. In contrast, MINRS becomes polynomialtime solvable for any q when restricted to caterpillars. We also present an exponentialtime algorithm based on tree separators for solving MINRS exactly. It runs in 2(O(n log p)) time when every node may have at most p children that are internal nodes and where n is the cardinality of the leaf label set. Finally, we demonstrate that augmenting the algorithm of Aho et al. with an algorithm for optimal graph coloring to help merge certain blocks of leaves during the execution does not improve the output solution much in the worst case.
Details
Authors  

Research areas and keywords  Subject classification (UKÄ) – MANDATORY
Keywords

Original language  English 

Pages (fromto)  272291 
Journal  SIAM Journal on Computing 
Volume  41 
Issue number  1 
State  Published  2012 
Peerreviewed  Yes 