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

Jesper Andreas Jansson; Wing Kin Sung

doi:10.1007/978-3-642-15775-2_49

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

Jesper Andreas Jansson, Wing Kin Sung

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

2 Citations (Scopus)

Abstract

The previously fastest algorithms for computing the R*consensus tree of two given (rooted) phylogenetic trees T1and T2with a leaf label set of cardinality n run in Θ(n3) time [3,8]. In this manuscript, we describe a new O(n2log n)-time algorithm to solve the problem. This is a significant improvement because the R* consensus tree is defined in terms of a set ℛmajwhich may contain Ω(n3) elements, so any direct approach which explicitly constructs ℛmajrequires Ω(n3) time.

Original language	English
Title of host publication	Algorithms, ESA 2010 - 18th Annual European Symposium, Proceedings
Pages	573-584
Number of pages	12
Edition	PART 1
DOIs	https://doi.org/10.1007/978-3-642-15775-2_49
Publication status	Published - 19 Nov 2010
Externally published	Yes
Event	18th Annual European Symposium on Algorithms, ESA 2010 - Liverpool, United Kingdom Duration: 6 Sept 2010 → 8 Sept 2010

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 1
Volume	6346 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	18th Annual European Symposium on Algorithms, ESA 2010
Country/Territory	United Kingdom
City	Liverpool
Period	6/09/10 → 8/09/10

ASJC Scopus subject areas

General Computer Science
Theoretical Computer Science

More information

10.1007/978-3-642-15775-2_49

Cite this

Jansson, J. A., & Sung, W. K. (2010). Constructing the R* consensus tree of two trees in subcubic time. In Algorithms, ESA 2010 - 18th Annual European Symposium, Proceedings (PART 1 ed., pp. 573-584). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6346 LNCS, No. PART 1). https://doi.org/10.1007/978-3-642-15775-2_49

@inproceedings{600150d325aa4242ab2f455239aed919,

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 T1and T2with a leaf label set of cardinality n run in Θ(n3) time [3,8]. In this manuscript, we describe a new O(n2log n)-time algorithm to solve the problem. This is a significant improvement because the R* consensus tree is defined in terms of a set ℛmajwhich may contain Ω(n3) elements, so any direct approach which explicitly constructs ℛmajrequires Ω(n3) time.",

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

year = "2010",

month = nov,

day = "19",

doi = "10.1007/978-3-642-15775-2_49",

language = "English",

isbn = "3642157742",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

number = "PART 1",

pages = "573--584",

booktitle = "Algorithms, ESA 2010 - 18th Annual European Symposium, Proceedings",

edition = "PART 1",

note = "18th Annual European Symposium on Algorithms, ESA 2010 ; Conference date: 06-09-2010 Through 08-09-2010",

}

Jansson, JA & Sung, WK 2010, Constructing the R* consensus tree of two trees in subcubic time. in Algorithms, ESA 2010 - 18th Annual European Symposium, Proceedings. PART 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 1, vol. 6346 LNCS, pp. 573-584, 18th Annual European Symposium on Algorithms, ESA 2010, Liverpool, United Kingdom, 6/09/10. https://doi.org/10.1007/978-3-642-15775-2_49

Constructing the R* consensus tree of two trees in subcubic time. / Jansson, Jesper Andreas; Sung, Wing Kin.
Algorithms, ESA 2010 - 18th Annual European Symposium, Proceedings. PART 1. ed. 2010. p. 573-584 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6346 LNCS, No. PART 1).

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

TY - GEN

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

AU - Jansson, Jesper Andreas

AU - Sung, Wing Kin

PY - 2010/11/19

Y1 - 2010/11/19

N2 - The previously fastest algorithms for computing the R*consensus tree of two given (rooted) phylogenetic trees T1and T2with a leaf label set of cardinality n run in Θ(n3) time [3,8]. In this manuscript, we describe a new O(n2log n)-time algorithm to solve the problem. This is a significant improvement because the R* consensus tree is defined in terms of a set ℛmajwhich may contain Ω(n3) elements, so any direct approach which explicitly constructs ℛmajrequires Ω(n3) time.

AB - The previously fastest algorithms for computing the R*consensus tree of two given (rooted) phylogenetic trees T1and T2with a leaf label set of cardinality n run in Θ(n3) time [3,8]. In this manuscript, we describe a new O(n2log n)-time algorithm to solve the problem. This is a significant improvement because the R* consensus tree is defined in terms of a set ℛmajwhich may contain Ω(n3) elements, so any direct approach which explicitly constructs ℛmajrequires Ω(n3) time.

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

U2 - 10.1007/978-3-642-15775-2_49

DO - 10.1007/978-3-642-15775-2_49

M3 - Conference article published in proceeding or book

SN - 3642157742

SN - 9783642157745

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 573

EP - 584

BT - Algorithms, ESA 2010 - 18th Annual European Symposium, Proceedings

T2 - 18th Annual European Symposium on Algorithms, ESA 2010

Y2 - 6 September 2010 through 8 September 2010

ER -

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

Abstract

Publication series

Conference

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this