Please use this identifier to cite or link to this item:
|Title:||Computing a smallest multilabeled phylogenetic tree from rooted triplets|
|Source:||Guillemot, S., Jansson, J., Sung, W.-K. (2011). Computing a smallest multilabeled phylogenetic tree from rooted triplets. IEEE/ACM Transactions on Computational Biology and Bioinformatics 8 (4) : 1141-1147. ScholarBank@NUS Repository. https://doi.org/10.1109/TCBB.2010.77|
|Abstract:||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. © 2011 IEEE.|
|Source Title:||IEEE/ACM Transactions on Computational Biology and Bioinformatics|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Jan 17, 2018
WEB OF SCIENCETM
checked on Dec 11, 2017
checked on Jan 14, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.