Algorithms for the majority rule (+) consensus tree and the frequency difference consensus tree

Jesper Andreas Jansson, Chuanqi Shen, Wing Kin Sung

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

4 Citations (Scopus)

Abstract

This paper presents two new deterministic algorithms for constructing consensus trees. Given an input of k phylogenetic trees with identical leaf label sets and n leaves each, the first algorithm constructs the majority rule (+) consensus tree in O(k n) time, which is optimal since the input size is Ω(k n), and the second one constructs the frequency difference consensus tree in min {O(kn2), O(k n (k + log2n))} time.
Original languageEnglish
Title of host publicationAlgorithms in Bioinformatics - 13th International Workshop, WABI 2013, Proceedings
Pages141-155
Number of pages15
DOIs
Publication statusPublished - 25 Sep 2013
Externally publishedYes
Event13th Workshop on Algorithms in Bioinformatics, WABI 2013 - Sophia Antipolis, France
Duration: 2 Sep 20134 Sep 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8126 LNBI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference13th Workshop on Algorithms in Bioinformatics, WABI 2013
CountryFrance
CitySophia Antipolis
Period2/09/134/09/13

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this