Please use this identifier to cite or link to this item: https://doi.org/10.1089/cmb.2012.0008
DC FieldValue
dc.titlePolynomial-time algorithms for building a consensus MUL-tree
dc.contributor.authorCui, Y.
dc.contributor.authorJansson, J.
dc.contributor.authorSung, W.-K.
dc.date.accessioned2013-07-23T09:25:10Z
dc.date.available2013-07-23T09:25:10Z
dc.date.issued2012
dc.identifier.citationCui, 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.issn10665277
dc.identifier.urihttp://scholarbank.nus.edu.sg/handle/10635/43108
dc.description.abstractA 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.urihttp://libproxy1.nus.edu.sg/login?url=http://dx.doi.org/10.1089/cmb.2012.0008
dc.sourceScopus
dc.subjectalgorithm
dc.subjectcluster
dc.subjectcomputational complexity
dc.subjectconsensus tree
dc.subjectMUL-tree.
dc.subjectmulti-labeled phylogenetic tree multiset
dc.typeArticle
dc.contributor.departmentCOMPUTER SCIENCE
dc.contributor.departmentMATHEMATICS
dc.description.doi10.1089/cmb.2012.0008
dc.description.sourcetitleJournal of Computational Biology
dc.description.volume19
dc.description.issue9
dc.description.page1073-1088
dc.description.codenJCOBE
dc.identifier.isiut000308746300007
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

9
checked on Dec 9, 2019

WEB OF SCIENCETM
Citations

8
checked on Dec 2, 2019

Page view(s)

78
checked on Dec 2, 2019

Google ScholarTM

Check

Altmetric


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