In *Proc. of Workshop on Algorithms in Bioinformatics (WABI 2010)*, volume 6293, of *Lect Notes Comput Sci*, pages 262–273, 2010.

doi abstract bibtex

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