Please use this identifier to cite or link to this item: https://doi.org/10.1109/TCBB.2010.77
Title: Computing a smallest multilabeled phylogenetic tree from rooted triplets
Authors: Guillemot, S.
Jansson, J.
Sung, W.-K. 
Keywords: acyclic tree-partition
dynamic programming.
inapproximability
MUL tree
Phylogenetics
rooted triplet
Issue Date: 2011
Citation: 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
URI: http://scholarbank.nus.edu.sg/handle/10635/39451
ISSN: 15455963
DOI: 10.1109/TCBB.2010.77
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

8
checked on Jul 17, 2018

WEB OF SCIENCETM
Citations

8
checked on Jul 17, 2018

Page view(s)

43
checked on Jul 13, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.