Please use this identifier to cite or link to this item:
https://doi.org/10.1007/978-3-642-10631-6_121
DC Field | Value | |
---|---|---|
dc.title | Computing a smallest multi-labeled phylogenetic tree from rooted triplets | |
dc.contributor.author | Guillemot, S. | |
dc.contributor.author | Jansson, J. | |
dc.contributor.author | Sung, W.-K. | |
dc.date.accessioned | 2013-07-04T08:05:14Z | |
dc.date.available | 2013-07-04T08:05:14Z | |
dc.date.issued | 2009 | |
dc.identifier.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. <a href="https://doi.org/10.1007/978-3-642-10631-6_121" target="_blank">https://doi.org/10.1007/978-3-642-10631-6_121</a> | |
dc.identifier.isbn | 3642106307 | |
dc.identifier.issn | 03029743 | |
dc.identifier.uri | http://scholarbank.nus.edu.sg/handle/10635/40478 | |
dc.description.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. | |
dc.description.uri | http://libproxy1.nus.edu.sg/login?url=http://dx.doi.org/10.1007/978-3-642-10631-6_121 | |
dc.source | Scopus | |
dc.type | Conference Paper | |
dc.contributor.department | COMPUTER SCIENCE | |
dc.description.doi | 10.1007/978-3-642-10631-6_121 | |
dc.description.sourcetitle | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | |
dc.description.volume | 5878 LNCS | |
dc.description.page | 1205-1214 | |
dc.identifier.isiut | NOT_IN_WOS | |
Appears in Collections: | Staff Publications |
Show simple item record
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.