Computing a smallest multilabeled phylogenetic tree from rooted triplets.
We investigate the computational complexity of inferring a smallest possible multilabeled phylogenetic tree (MUL tree) which is consistent with each of the rooted triplets in a given set. This problem has not been studied previously in the literature. We prove that even the very restricted case of determining if there exists a MUL tree consistent with the input and having just one leaf duplication is an NP-hard problem. Furthermore, we show that the general minimization problem is difficult to approximate, although a simple polynomial-time approximation algorithm achieves an approximation ratio close to our derived inapproximability bound. Finally, we provide an exact algorithm for the problem running in exponential time and space. As a by-product, we also obtain new, strong inapproximability results for two partitioning problems on directed graphs called ACYCLIC PARTITION and ACYCLIC TREE-PARTITION.
Guillemot
Sylvain
S
Institut Gaspard Monge-Université Paris-Est, 5 boulevard Descartes, Champs-sur-Marne, 77454 Marne-la-Vallée, France. Sylvain.Guillemot@univ-mlv.fr
Jansson
Jesper
J
Sung
Wing-Kin
WK
D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D008957:Models, Genetic; D015233:Models, Statistical; D010802:Phylogeny