Constructing the R* consensus tree of two trees in subcubic time

Jesper Andreas Jansson, Wing Kin Sung

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

2 Citations (Scopus)

Abstract

The previously fastest algorithms for computing the R*consensus tree of two given (rooted) phylogenetic trees T1and T2with a leaf label set of cardinality n run in Θ(n3) time [3,8]. In this manuscript, we describe a new O(n2log n)-time algorithm to solve the problem. This is a significant improvement because the R* consensus tree is defined in terms of a set ℛmajwhich may contain Ω(n3) elements, so any direct approach which explicitly constructs ℛmajrequires Ω(n3) time.
Original languageEnglish
Title of host publicationAlgorithms, ESA 2010 - 18th Annual European Symposium, Proceedings
Pages573-584
Number of pages12
EditionPART 1
DOIs
Publication statusPublished - 19 Nov 2010
Externally publishedYes
Event18th Annual European Symposium on Algorithms, ESA 2010 - Liverpool, United Kingdom
Duration: 6 Sep 20108 Sep 2010

Publication series

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

Conference

Conference18th Annual European Symposium on Algorithms, ESA 2010
Country/TerritoryUnited Kingdom
CityLiverpool
Period6/09/108/09/10

ASJC Scopus subject areas

  • Computer Science(all)
  • Theoretical Computer Science

Cite this