Algorithms for building consensus MUL-trees

Yun Cui, Jesper Andreas Jansson, Wing Kin Sung

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

1 Citation (Scopus)


A MUL-tree is a generalization of a phylogenetic tree that allows the same leaf label to be used many times. Lott et al. [9,10] recently introduced the problem of inferring a so-called consensus MUL-tree from a set of conflicting MUL-trees and gave an exponential-time algorithm for a special greedy variant. Here, we study strict and majority rule consensus MUL-trees, and present the first ever polynomial-time algorithms for building a consensus MUL-tree. We give a simple, fast algorithm for building a strict consensus MUL-tree. We also show that although it is NP-hard to find a majority rule consensus MUL-tree, the variant which we call the singular majority rule consensus MUL-tree is unique and can be constructed efficiently.
Original languageEnglish
Title of host publicationAlgorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings
Number of pages10
Publication statusPublished - 26 Dec 2011
Externally publishedYes
Event22nd International Symposium on Algorithms and Computation, ISAAC 2011 - Yokohama, Japan
Duration: 5 Dec 20118 Dec 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7074 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference22nd International Symposium on Algorithms and Computation, ISAAC 2011

ASJC Scopus subject areas

  • Computer Science(all)
  • Theoretical Computer Science

Cite this