Advanced

The complexity of inferring a minimally resolved phylogenetic supertree

Jansson, Jesper; Lemence, Richard S. and Lingas, Andrzej LU (2012) In SIAM Journal on Computing 41(1). p.272-291
Abstract
A recursive algorithm by Aho et al. [SIAM J. Comput., 10 (1981), pp. 405-421] 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 polynomial-time inapproximability results for the problem of inferring a minimally resolved supertree from a given consistent set of rooted triplets (MINRS). Furthermore, we show that... (More)
A recursive algorithm by Aho et al. [SIAM J. Comput., 10 (1981), pp. 405-421] 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 polynomial-time 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 NP-hard for any fixed positive integer q >= 4, where q is the number of allowed internal nodes, but linear-time solvable for q <= 3. In contrast, MINRS becomes polynomial-time solvable for any q when restricted to caterpillars. We also present an exponential-time 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. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
tree separator, graph coloring, NP-hardness, minimally resolved supertree, rooted triplet, phylogenetic tree
in
SIAM Journal on Computing
volume
41
issue
1
pages
272 - 291
publisher
SIAM Publications
external identifiers
  • wos:000300892300012
  • scopus:84861639410
ISSN
0097-5397
DOI
10.1137/100811489
language
English
LU publication?
yes
id
68624f95-32cf-45be-8f98-aaf5803e9b0f (old id 2517538)
date added to LUP
2012-05-15 07:21:22
date last changed
2017-05-21 03:48:11
@article{68624f95-32cf-45be-8f98-aaf5803e9b0f,
  abstract     = {A recursive algorithm by Aho et al. [SIAM J. Comput., 10 (1981), pp. 405-421] 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 polynomial-time 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 NP-hard for any fixed positive integer q &gt;= 4, where q is the number of allowed internal nodes, but linear-time solvable for q &lt;= 3. In contrast, MINRS becomes polynomial-time solvable for any q when restricted to caterpillars. We also present an exponential-time 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.},
  author       = {Jansson, Jesper and Lemence, Richard S. and Lingas, Andrzej},
  issn         = {0097-5397},
  keyword      = {tree separator,graph coloring,NP-hardness,minimally resolved supertree,rooted triplet,phylogenetic tree},
  language     = {eng},
  number       = {1},
  pages        = {272--291},
  publisher    = {SIAM Publications},
  series       = {SIAM Journal on Computing},
  title        = {The complexity of inferring a minimally resolved phylogenetic supertree},
  url          = {http://dx.doi.org/10.1137/100811489},
  volume       = {41},
  year         = {2012},
}