Algorithms for the Majority Rule (+) Consensus Tree and the Frequency Difference Consensus Tree

Jesper Andreas Jansson, Ramesh Rajaby, Chuanqi Shen, Wing Kin Sung

Research output: Journal article publicationJournal articleAcademic researchpeer-review

2 Citations (Scopus)

Abstract

This article presents two new deterministic algorithms for constructing consensus trees. Given an input of κ phylogenetic trees with identical leaf label sets and n leaves each, the first algorithm constructs the majority rule (+) consensus tree in O(kn) time, which is optimal since the input size is ω (kn) , and the second one constructs the frequency difference consensus tree in μ\lbrace O(kn2), O(kn (k+log2n)) time.
Original languageEnglish
Pages (from-to)15-26
Number of pages12
JournalIEEE/ACM Transactions on Computational Biology and Bioinformatics
Volume15
Issue number1
DOIs
Publication statusPublished - 1 Jan 2018
Externally publishedYes

Keywords

  • cluster
  • consensus tree
  • pairwise compatibility
  • Phylogenetic tree
  • tree algorithm

ASJC Scopus subject areas

  • Biotechnology
  • Genetics
  • Applied Mathematics

Cite this