Please use this identifier to cite or link to this item:
https://doi.org/10.1089/cmb.2012.0008
Title: | Polynomial-time algorithms for building a consensus MUL-tree | Authors: | Cui, Y. Jansson, J. Sung, W.-K. |
Keywords: | algorithm cluster computational complexity consensus tree MUL-tree. multi-labeled phylogenetic tree multiset |
Issue Date: | 2012 | 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 | 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. | Source Title: | Journal of Computational Biology | URI: | http://scholarbank.nus.edu.sg/handle/10635/43108 | ISSN: | 10665277 | DOI: | 10.1089/cmb.2012.0008 |
Appears in Collections: | Staff Publications |
Show full 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.