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

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

doi:10.1109/TCBB.2016.2609923

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 publication › Journal article › Academic research › peer-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 language	English
Pages (from-to)	15-26
Number of pages	12
Journal	IEEE/ACM Transactions on Computational Biology and Bioinformatics
Volume	15
Issue number	1
DOIs	https://doi.org/10.1109/TCBB.2016.2609923
Publication status	Published - 1 Jan 2018
Externally published	Yes

Keywords

cluster
consensus tree
pairwise compatibility
Phylogenetic tree
tree algorithm

ASJC Scopus subject areas

Biotechnology
Genetics
Applied Mathematics

More information

10.1109/TCBB.2016.2609923

Scopus Link

Cite this

@article{5e95e5ef1b9a46ae902833b314efe349,

title = "Algorithms for the Majority Rule (+) Consensus Tree and the Frequency Difference Consensus Tree",

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.",

keywords = "cluster, consensus tree, pairwise compatibility, Phylogenetic tree, tree algorithm",

author = "Jansson, {Jesper Andreas} and Ramesh Rajaby and Chuanqi Shen and Sung, {Wing Kin}",

year = "2018",

month = jan,

day = "1",

doi = "10.1109/TCBB.2016.2609923",

language = "English",

volume = "15",

pages = "15--26",

journal = "IEEE/ACM Transactions on Computational Biology and Bioinformatics",

issn = "1545-5963",

publisher = "IEEE",

number = "1",

}

Algorithms for the Majority Rule (+) Consensus Tree and the Frequency Difference Consensus Tree. / Jansson, Jesper Andreas; Rajaby, Ramesh; Shen, Chuanqi; Sung, Wing Kin.

In: IEEE/ACM Transactions on Computational Biology and Bioinformatics, Vol. 15, No. 1, 01.01.2018, p. 15-26.

Research output: Journal article publication › Journal article › Academic research › peer-review

TY - JOUR

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

AU - Jansson, Jesper Andreas

AU - Rajaby, Ramesh

AU - Shen, Chuanqi

AU - Sung, Wing Kin

PY - 2018/1/1

Y1 - 2018/1/1

N2 - 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.

AB - 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.

KW - cluster

KW - consensus tree

KW - pairwise compatibility

KW - Phylogenetic tree

KW - tree algorithm

UR - http://www.scopus.com/inward/record.url?scp=85042466390&partnerID=8YFLogxK

U2 - 10.1109/TCBB.2016.2609923

DO - 10.1109/TCBB.2016.2609923

M3 - Journal article

VL - 15

SP - 15

EP - 26

JO - IEEE/ACM Transactions on Computational Biology and Bioinformatics

JF - IEEE/ACM Transactions on Computational Biology and Bioinformatics

SN - 1545-5963

IS - 1

ER -