TY - GEN
T1 - The complexity of inferring a minimally resolved phylogenetic supertree
AU - Jansson, Jesper Andreas
AU - Lemence, Richard S.
AU - Lingas, Andrzej
PY - 2010/11/10
Y1 - 2010/11/10
N2 - 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 2O(n logk) 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.
AB - 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 2O(n logk) 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.
KW - minimally resolved supertree
KW - NP-hardness
KW - Phylogenetic tree
KW - rooted triplet
KW - tree separator
UR - http://www.scopus.com/inward/record.url?scp=78049455586&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-15294-8_22
DO - 10.1007/978-3-642-15294-8_22
M3 - Conference article published in proceeding or book
SN - 3642152937
SN - 9783642152931
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 262
EP - 273
BT - Algorithms in Bioinformatics - 10th International Workshop, WABI 2010, Proceedings
T2 - 10th International Workshop on Algorithms in Bioinformatics, WABI 2010
Y2 - 6 September 2010 through 8 September 2010
ER -