Polynomial-time algorithms for building a consensus MUL-tree

Yun Cui, Jesper Andreas Jansson, Wing Kin Sung

Research output: Journal article publicationJournal articleAcademic researchpeer-review

9 Citations (Scopus)

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.
Original languageEnglish
Pages (from-to)1073-1088
Number of pages16
JournalJournal of Computational Biology
Volume19
Issue number9
DOIs
Publication statusPublished - 1 Sep 2012
Externally publishedYes

Keywords

  • algorithm
  • cluster
  • computational complexity
  • consensus tree
  • MUL-tree.
  • multi-labeled phylogenetic tree multiset

ASJC Scopus subject areas

  • Molecular Biology
  • Genetics
  • Computational Mathematics
  • Modelling and Simulation
  • Computational Theory and Mathematics

Cite this