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)

Abstract

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
Pages744-753
Number of pages10
DOIs
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

Conference

Conference22nd International Symposium on Algorithms and Computation, ISAAC 2011
CountryJapan
CityYokohama
Period5/12/118/12/11

ASJC Scopus subject areas

  • Computer Science(all)
  • Theoretical Computer Science

Cite this