| Computing a smallest multilabeled phylogenetic tree from rooted triplets. | |
| | |
MedLine Citation:
|
PMID: 20733243 Owner: NLM Status: In-Process |
Abstract/OtherAbstract:
|
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. |
| | |
Authors:
|
Sylvain Guillemot; Jesper Jansson; Wing-Kin Sung |
Related Documents
:
|
20513723 - Computer-aided maxillofacial surgery: an update. 17746873 - Computer applications in the humanities. 10105863 - How to keep your best people for the '90s. |
Publication Detail:
|
Type: Journal Article; Research Support, Non-U.S. Gov't |
Journal Detail:
|
Title: IEEE/ACM transactions on computational biology and bioinformatics / IEEE, ACM Volume: 8 ISSN: 1557-9964 ISO Abbreviation: IEEE/ACM Trans Comput Biol Bioinform Publication Date: 2011 Jul-Aug |
Date Detail:
|
Created Date: 2011-08-02 Completed Date: - Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 101196755 Medline TA: IEEE/ACM Trans Comput Biol Bioinform Country: United States |
Other Details:
|
Languages: eng Pagination: 1141-7 Citation Subset: IM |
Affiliation:
|
Institut Gaspard Monge-Université Paris-Est, 5 boulevard Descartes, Champs-sur-Marne, 77454 Marne-la-Vallée, France. Sylvain.Guillemot@univ-mlv.fr |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
|
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: FEAST: sensitive local alignment with multiple rates of evolution.
Next Document: A fast hierarchical clustering algorithm for functional modules discovery in protein interaction net...