Please use this identifier to cite or link to this item:
Title: Polynomial-time algorithms for building a consensus MUL-tree
Authors: Cui, Y. 
Jansson, J.
Sung, W.-K. 
Keywords: algorithm
computational complexity
consensus 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.
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
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.


checked on Dec 2, 2019


checked on Dec 2, 2019

Page view(s)

checked on Dec 2, 2019

Google ScholarTM



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