title: Polynomial-time algorithms for building a consensus MUL-tree.
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.
authors.affiliation: School of Computing, National University of Singapore, Singapore.
authors.forename: Yun
authors.initials: Y
authors.lastname: Cui
authors.forename: Jesper
authors.initials: J
authors.lastname: Jansson
authors.forename: Wing-Kin
authors.initials: WK
authors.lastname: Sung
mesh_terms: D000465:Algorithms; D000818:Animals; D019295:Computational Biology; D019143:Evolution, Molecular; D006801:Humans; D008957:Models, Genetic; D010802:Phylogeny