On finding the Adams consensus tree

Jesper Andreas Jansson, Zhaoxian Li, Wing Kin Sung

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

1 Citation (Scopus)

Abstract

This paper presents a fast algorithm for finding the Adams consensus tree of a set of conflicting phylogenetic trees with identical leaf labels, for the first time improving the time complexity of a widely used algorithm invented by Adams in 1972 [1]. Our algorithm applies the centroid path decomposition technique [9] in a new way to traverse the input trees' centroid paths in unison, and runs in O(kn log n) time, where k is the number of input trees and n is the size of the leaf label set. (In comparison, the old algorithm from 1972 has a worst-case running time of O(kn2).) For the special case of k = 2, an even faster algorithm running in O(n · log n/log log n) time is provided, which relies on an extension of the wavelet tree-based technique by Bose et al. [6] for orthogonal range counting on a grid. Our extended wavelet tree data structure also supports truncated range maximum queries efficiently and may be of independent interest to algorithm designers.
Original languageEnglish
Title of host publication32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages487-499
Number of pages13
Volume30
ISBN (Electronic)9783939897781
DOIs
Publication statusPublished - 1 Jan 2015
Externally publishedYes
Event32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015 - Garching, Germany
Duration: 4 Mar 20157 Mar 2015

Conference

Conference32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015
CountryGermany
CityGarching
Period4/03/157/03/15

Keywords

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

ASJC Scopus subject areas

  • Software

Cite this