Please use this identifier to cite or link to this item:
|Title:||Computing a smallest multi-labeled phylogenetic tree from rooted triplets|
|Citation:||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)|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Dec 9, 2018
checked on Nov 17, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.