Please use this identifier to cite or link to this item:
https://doi.org/10.1089/cmb.2012.0008
DC Field | Value | |
---|---|---|
dc.title | Polynomial-time algorithms for building a consensus MUL-tree | |
dc.contributor.author | Cui, Y. | |
dc.contributor.author | Jansson, J. | |
dc.contributor.author | Sung, W.-K. | |
dc.date.accessioned | 2013-07-23T09:25:10Z | |
dc.date.available | 2013-07-23T09:25:10Z | |
dc.date.issued | 2012 | |
dc.identifier.citation | Cui, Y., Jansson, J., Sung, W.-K. (2012). Polynomial-time algorithms for building a consensus MUL-tree. Journal of Computational Biology 19 (9) : 1073-1088. ScholarBank@NUS Repository. https://doi.org/10.1089/cmb.2012.0008 | |
dc.identifier.issn | 10665277 | |
dc.identifier.uri | http://scholarbank.nus.edu.sg/handle/10635/43108 | |
dc.description.abstract | A multi-labeled phylogenetic tree, or MUL-tree, is a generalization of a phylogenetic tree that allows each leaf label to be used many times. MUL-trees have applications in biogeography, the study of host-parasite cospeciation, gene evolution studies, and computer science. Here, we consider the problem of inferring a consensus MUL-tree that summarizes a given set of conflicting MUL-trees, and present the first polynomial-time algorithms for solving it. In particular, we give a straightforward, fast algorithm for building a strict consensus MUL-tree for any input set of MUL-trees with identical leaf label multisets, as well as a polynomial-time algorithm for building a majority rule consensus MUL-tree for the special case where every leaf label occurs at most twice. We also show that, although it is NP-hard to find a majority rule consensus MUL-tree in general, the variant that we call the singular majority rule consensus MUL-tree can be constructed efficiently whenever it exists. © 2012, Mary Ann Liebert, Inc. | |
dc.description.uri | http://libproxy1.nus.edu.sg/login?url=http://dx.doi.org/10.1089/cmb.2012.0008 | |
dc.source | Scopus | |
dc.subject | algorithm | |
dc.subject | cluster | |
dc.subject | computational complexity | |
dc.subject | consensus tree | |
dc.subject | MUL-tree. | |
dc.subject | multi-labeled phylogenetic tree multiset | |
dc.type | Article | |
dc.contributor.department | COMPUTER SCIENCE | |
dc.contributor.department | MATHEMATICS | |
dc.description.doi | 10.1089/cmb.2012.0008 | |
dc.description.sourcetitle | Journal of Computational Biology | |
dc.description.volume | 19 | |
dc.description.issue | 9 | |
dc.description.page | 1073-1088 | |
dc.description.coden | JCOBE | |
dc.identifier.isiut | 000308746300007 | |
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.