On finding the Adams consensus tree

Jesper Andreas Jansson, Zhaoxian Li, Wing Kin Sung

Research output: Journal article publicationJournal articleAcademic researchpeer-review

3 Citations (Scopus)

Abstract

Its worst-case running time is O(knlog⁡n), where k is the number of input trees and n is the size of the leaf label set; in comparison, the original algorithm of Adams has a worst-case running time of O(kn2). To achieve subquadratic running time, the centroid path decomposition technique is applied in a novel way that traverses the input trees by following a centroid path in each of them in unison. For k=2, an even faster algorithm running in O(n⋅[Formula presented]) time is provided, which relies on an extension of the wavelet tree-based technique of Bose et al. for orthogonal range counting on a grid. Our extended wavelet tree data structure also supports truncated range maximum/minimum queries efficiently.
Original languageEnglish
Pages (from-to)334-347
Number of pages14
JournalInformation and Computation
Volume256
DOIs
Publication statusPublished - 1 Oct 2017

Keywords

  • Adams consensus
  • Centroid path
  • Phylogenetic tree
  • Wavelet tree

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Cite this