The Complexity of Inferring a Minimally Resolved Phylogenetic Supertree. Jansson, J., Lemence, R., & Lingas, A. In Proc. of Workshop on Algorithms in Bioinformatics (WABI 2010), volume 6293, of Lect Notes Comput Sci, pages 262–273, 2010.
doi  abstract   bibtex   
A recursive algorithm by Aho, Sagiv, Szymanski, and Ullman [1] forms the basis for many modern rooted supertree methods employed in Phylogenetics. However, as observed by Bryant [4], 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). We also present an exponential-time algorithm for solving MinRS exactly which is based on tree separators. It runs in 2^O(n log k) time when every node is required to have at most k children which are internal nodes and where n is the cardinality of the leaf label set of the input trees.
@InProceedings{jansson10complexity,
  author    = {Jansson, Jesper and Lemence, RichardS. and Lingas, Andrzej},
  title     = {The Complexity of Inferring a Minimally Resolved Phylogenetic Supertree},
  booktitle = {Proc. of Workshop on Algorithms in Bioinformatics (WABI 2010)},
  year      = {2010},
  volume    = {6293},
  series    = lncs,
  pages     = {262--273},
  publisher = Springer,
  abstract  = {A recursive algorithm by Aho, Sagiv, Szymanski, and Ullman [1] forms the basis for many modern rooted supertree methods employed in Phylogenetics. However, as observed by Bryant [4], 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). We also present an exponential-time algorithm for solving MinRS exactly which is based on tree separators. It runs in 2^O(n log k) time when every node is required to have at most k children which are internal nodes and where n is the cardinality of the leaf label set of the input trees.},
  doi       = {10.1007/978-3-642-15294-8_22},
  isbn      = {978-3-642-15293-1},
  keywords  = {Phylogenetic tree; rooted triplet; minimally resolved supertree; NP-hardness; tree separator},
  owner     = {Sebastian},
  timestamp = {2014.10.09},
}
Downloads: 0