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

Jesper Andreas Jansson, Wing Kin Sung

Research output: Journal article publicationJournal articleAcademic researchpeer-review

6 Citations (Scopus)

Abstract

The previously fastest algorithms for computing the R*consensus tree of two given (rooted) phylogenetic trees with a leaf label set of cardinality n run in Θ(n3) time (Bryant and Berry in Adv. Appl. Math. 27(4):705-732, 2001; Kannan et al. in SIAM J. Comput. 27(6):1695-1724, 1998). In this manuscript, we describe a new O(n2√log n-time algorithm to solve the problem. This is a significant improvement because the R*consensus tree is defined in terms of a set Rmajwhich may contain Ω(n3) elements, so any direct approach that explicitly constructs Rmajrequires Ω(n3) time.
Original languageEnglish
Pages (from-to)329-345
Number of pages17
JournalAlgorithmica
Volume66
Issue number2
DOIs
Publication statusPublished - 1 Jun 2013
Externally publishedYes

Keywords

  • Apresjan cluster
  • consensus tree
  • Lowest common ancestor
  • Offline orthogonal range counting
  • Phylogenetic tree
  • R
  • Strong cluster
  • Triplet

ASJC Scopus subject areas

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

Cite this