Faster algorithms for computing the R* Consensus tree

Jesper Andreas Jansson, Wing Kin Sung, Hoa Vu, Siu Ming Yiu

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

1 Citation (Scopus)

Abstract

The fastest known algorithms for computing the R* consensus tree of k rooted phylogenetic trees with n leaves each and identical leaf label sets run in O(n2 √ log n) time when k = 2 (ref. [10]) and O(kn3) time when k ≥ 3 (ref. [4]). This paper shows how to compute it in O(n2) time for k = 2, O(n2 log4/3n) time for k = 3, and O(n2 logk+2n) time for unbounded k.
Original languageEnglish
Title of host publicationAlgorithms and Computation - 25th International Symposium, ISAAC 2014, Proceedings
EditorsHee-Kap Ahn, Chan-Su Shin
Pages414-425
Number of pages12
ISBN (Electronic)9783319130743
DOIs
Publication statusPublished - 1 Jan 2014
Externally publishedYes
Event25th International Symposium on Algorithms and Computation, ISAAC 2014 - Jeonju, Korea, Republic of
Duration: 15 Dec 201417 Dec 2014

Publication series

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

Conference

Conference25th International Symposium on Algorithms and Computation, ISAAC 2014
CountryKorea, Republic of
CityJeonju
Period15/12/1417/12/14

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this