Constructing the R*consensus tree of two trees in subcubic time

Jesper Andreas Jansson; Wing Kin Sung

doi:10.1007/s00453-012-9639-1

Constructing the R*consensus tree of two trees in subcubic time

Jesper Andreas Jansson, Wing Kin Sung

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

6 Citations (Scopus)

Abstract

The previously fastest algorithms for computing the R*consensus tree of two given (rooted) phylogenetic trees with a leaf label set of cardinality n run in Θ(n3) time (Bryant and Berry in Adv. Appl. Math. 27(4):705-732, 2001; Kannan et al. in SIAM J. Comput. 27(6):1695-1724, 1998). In this manuscript, we describe a new O(n2√log n-time algorithm to solve the problem. This is a significant improvement because the R*consensus tree is defined in terms of a set Rmajwhich may contain Ω(n3) elements, so any direct approach that explicitly constructs Rmajrequires Ω(n3) time.

Original language	English
Pages (from-to)	329-345
Number of pages	17
Journal	Algorithmica
Volume	66
Issue number	2
DOIs	https://doi.org/10.1007/s00453-012-9639-1
Publication status	Published - 1 Jun 2013
Externally published	Yes

Keywords

Apresjan cluster
consensus tree
Lowest common ancestor
Offline orthogonal range counting
Phylogenetic tree
R
Strong cluster
Triplet

ASJC Scopus subject areas

General Computer Science
Computer Science Applications
Applied Mathematics

More information

10.1007/s00453-012-9639-1

Cite this

@article{cf50e2416bda483caf3bddbc6237de1d,

title = "Constructing the R*consensus tree of two trees in subcubic time",

abstract = "The previously fastest algorithms for computing the R*consensus tree of two given (rooted) phylogenetic trees with a leaf label set of cardinality n run in Θ(n3) time (Bryant and Berry in Adv. Appl. Math. 27(4):705-732, 2001; Kannan et al. in SIAM J. Comput. 27(6):1695-1724, 1998). In this manuscript, we describe a new O(n2√log n-time algorithm to solve the problem. This is a significant improvement because the R*consensus tree is defined in terms of a set Rmajwhich may contain Ω(n3) elements, so any direct approach that explicitly constructs Rmajrequires Ω(n3) time.",

keywords = "Apresjan cluster, consensus tree, Lowest common ancestor, Offline orthogonal range counting, Phylogenetic tree, R, Strong cluster, Triplet",

author = "Jansson, {Jesper Andreas} and Sung, {Wing Kin}",

year = "2013",

month = jun,

day = "1",

doi = "10.1007/s00453-012-9639-1",

language = "English",

volume = "66",

pages = "329--345",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer New York",

number = "2",

}

TY - JOUR

T1 - Constructing the R*consensus tree of two trees in subcubic time

AU - Jansson, Jesper Andreas

AU - Sung, Wing Kin

PY - 2013/6/1

Y1 - 2013/6/1

N2 - The previously fastest algorithms for computing the R*consensus tree of two given (rooted) phylogenetic trees with a leaf label set of cardinality n run in Θ(n3) time (Bryant and Berry in Adv. Appl. Math. 27(4):705-732, 2001; Kannan et al. in SIAM J. Comput. 27(6):1695-1724, 1998). In this manuscript, we describe a new O(n2√log n-time algorithm to solve the problem. This is a significant improvement because the R*consensus tree is defined in terms of a set Rmajwhich may contain Ω(n3) elements, so any direct approach that explicitly constructs Rmajrequires Ω(n3) time.

AB - The previously fastest algorithms for computing the R*consensus tree of two given (rooted) phylogenetic trees with a leaf label set of cardinality n run in Θ(n3) time (Bryant and Berry in Adv. Appl. Math. 27(4):705-732, 2001; Kannan et al. in SIAM J. Comput. 27(6):1695-1724, 1998). In this manuscript, we describe a new O(n2√log n-time algorithm to solve the problem. This is a significant improvement because the R*consensus tree is defined in terms of a set Rmajwhich may contain Ω(n3) elements, so any direct approach that explicitly constructs Rmajrequires Ω(n3) time.

KW - Apresjan cluster

KW - consensus tree

KW - Lowest common ancestor

KW - Offline orthogonal range counting

KW - Phylogenetic tree

KW - R

KW - Strong cluster

KW - Triplet

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

U2 - 10.1007/s00453-012-9639-1

DO - 10.1007/s00453-012-9639-1

M3 - Journal article

SN - 0178-4617

VL - 66

SP - 329

EP - 345

JO - Algorithmica

JF - Algorithmica

IS - 2

ER -

Constructing the R*consensus tree of two trees in subcubic time

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this