Faster Algorithms for Computing the R* Consensus Tree

Jesper Andreas Jansson; Wing Kin Sung; Hoa Vu; Siu Ming Yiu

doi:10.1007/s00453-016-0122-2

Faster Algorithms for Computing the R* Consensus Tree

Jesper Andreas Jansson, Wing Kin Sung, Hoa Vu, Siu Ming Yiu

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

2 Citations (Scopus)

Abstract

The fastest known algorithms for computing the R* consensus tree of k rooted phylogenetic trees with n leaves each and identical leaf label sets run in O(n2logn) time when k= 2 (Jansson and Sung in Algorithmica 66(2):329–345, 2013) and O(kn3) time when k≥ 3 (Bryant in Bioconsensus, volume 61 of DIMACS series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, pp 163–184, 2003). This paper shows how to compute it in O(n2) time for k= 2 , O(n2log4 / 3n) time for k= 3 , and O(n2logk+2n) time for unbounded k.

Original language	English
Pages (from-to)	1224-1244
Number of pages	21
Journal	Algorithmica
Volume	76
Issue number	4
DOIs	https://doi.org/10.1007/s00453-016-0122-2
Publication status	Published - 1 Dec 2016
Externally published	Yes

Keywords

Apresjan cluster
Phylogenetic tree
R* consensus tree
Strong cluster
Triplet

ASJC Scopus subject areas

General Computer Science
Computer Science Applications
Applied Mathematics

More information

10.1007/s00453-016-0122-2

Cite this

@article{f390104063304abd8b8179402228fdbc,

title = "Faster Algorithms for Computing the R* Consensus Tree",

abstract = "The fastest known algorithms for computing the R* consensus tree of k rooted phylogenetic trees with n leaves each and identical leaf label sets run in O(n2logn) time when k= 2 (Jansson and Sung in Algorithmica 66(2):329–345, 2013) and O(kn3) time when k≥ 3 (Bryant in Bioconsensus, volume 61 of DIMACS series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, pp 163–184, 2003). This paper shows how to compute it in O(n2) time for k= 2 , O(n2log4 / 3n) time for k= 3 , and O(n2logk+2n) time for unbounded k.",

keywords = "Apresjan cluster, Phylogenetic tree, R* consensus tree, Strong cluster, Triplet",

author = "Jansson, {Jesper Andreas} and Sung, {Wing Kin} and Hoa Vu and Yiu, {Siu Ming}",

year = "2016",

month = dec,

day = "1",

doi = "10.1007/s00453-016-0122-2",

language = "English",

volume = "76",

pages = "1224--1244",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer New York",

number = "4",

}

TY - JOUR

T1 - Faster Algorithms for Computing the R* Consensus Tree

AU - Jansson, Jesper Andreas

AU - Sung, Wing Kin

AU - Vu, Hoa

AU - Yiu, Siu Ming

PY - 2016/12/1

Y1 - 2016/12/1

N2 - The fastest known algorithms for computing the R* consensus tree of k rooted phylogenetic trees with n leaves each and identical leaf label sets run in O(n2logn) time when k= 2 (Jansson and Sung in Algorithmica 66(2):329–345, 2013) and O(kn3) time when k≥ 3 (Bryant in Bioconsensus, volume 61 of DIMACS series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, pp 163–184, 2003). This paper shows how to compute it in O(n2) time for k= 2 , O(n2log4 / 3n) time for k= 3 , and O(n2logk+2n) time for unbounded k.

AB - The fastest known algorithms for computing the R* consensus tree of k rooted phylogenetic trees with n leaves each and identical leaf label sets run in O(n2logn) time when k= 2 (Jansson and Sung in Algorithmica 66(2):329–345, 2013) and O(kn3) time when k≥ 3 (Bryant in Bioconsensus, volume 61 of DIMACS series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, pp 163–184, 2003). This paper shows how to compute it in O(n2) time for k= 2 , O(n2log4 / 3n) time for k= 3 , and O(n2logk+2n) time for unbounded k.

KW - Apresjan cluster

KW - Phylogenetic tree

KW - R consensus tree

KW - Strong cluster

KW - Triplet

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

U2 - 10.1007/s00453-016-0122-2

DO - 10.1007/s00453-016-0122-2

M3 - Journal article

SN - 0178-4617

VL - 76

SP - 1224

EP - 1244

JO - Algorithmica

JF - Algorithmica

IS - 4

ER -

Faster Algorithms for Computing the R* Consensus Tree

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this