Faster Algorithms for Computing the R* Consensus Tree

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

Research output: Journal article publicationJournal articleAcademic researchpeer-review

2 Citations (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(n2logn) time when k= 2 (Jansson and Sung in Algorithmica 66(2):329–345, 2013) and O(kn3) time when k≥ 3 (Bryant in Bioconsensus, volume 61 of DIMACS series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, pp 163–184, 2003). This paper shows how to compute it in O(n2) time for k= 2 , O(n2log4 / 3n) time for k= 3 , and O(n2logk+2n) time for unbounded k.
Original languageEnglish
Pages (from-to)1224-1244
Number of pages21
JournalAlgorithmica
Volume76
Issue number4
DOIs
Publication statusPublished - 1 Dec 2016
Externally publishedYes

Keywords

  • Apresjan cluster
  • Phylogenetic tree
  • R* consensus tree
  • Strong cluster
  • Triplet

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Cite this