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 -