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
Source: 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.

SCOPUSTM   
Citations

5
checked on Dec 6, 2017

WEB OF SCIENCETM
Citations

3
checked on Nov 21, 2017

Page view(s)

56
checked on Dec 10, 2017

Google ScholarTM

Check

Altmetric


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