Please use this identifier to cite or link to this item: https://doi.org/10.1007/978-3-642-10631-6_121
Title: Computing a smallest multi-labeled phylogenetic tree from rooted triplets
Authors: Guillemot, S.
Jansson, J.
Sung, W.-K. 
Issue Date: 2009
Source: Guillemot, S.,Jansson, J.,Sung, W.-K. (2009). Computing a smallest multi-labeled phylogenetic tree from rooted triplets. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 5878 LNCS : 1205-1214. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-642-10631-6_121
Abstract: We investigate the computational complexity of a new combinatorial problem of inferring a smallest possible multi-labeled phylogenetic tree (MUL tree) which is consistent with each of the rooted triplets in a given set. We prove that even the restricted case of determining if there exists a MUL tree consistent with the input and having just one leaf duplication is NP-hard. Furthermore, we show that the general minimization problem is NP-hard to approximate within a ratio of n 1-ε for any constant 0<ε≤1, where n denotes the number of distinct leaf labels in the input set, although a simple polynomial-time approximation algorithm achieves the approximation ratio n. We also provide an exact algorithm for the problem running in O *(7 n ) time and O *(3 n ) space. © 2009 Springer-Verlag Berlin Heidelberg.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
URI: http://scholarbank.nus.edu.sg/handle/10635/40478
ISBN: 3642106307
ISSN: 03029743
DOI: 10.1007/978-3-642-10631-6_121
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

2
checked on Dec 13, 2017

Page view(s)

47
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


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