Open Access
Lecture Notes in Computer Science, pages 573-584
Constructing the R* Consensus Tree of Two Trees in Subcubic Time
3
Genome Institute of Singapore, Genome, Singapore
|
Publication type: Book Chapter
Publication date: 2010-09-01
Journal:
Lecture Notes in Computer Science
Q2
SJR: 0.606
CiteScore: 2.6
Impact factor: —
ISSN: 03029743, 16113349, 18612075, 18612083
Abstract
The previously fastest algorithms for computing the R* consensus tree of two given (rooted) phylogenetic trees T
1 and T
2 with a leaf label set of cardinality n run in Θ(n
3) time [3,8]. In this manuscript, we describe a new O(n
2 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
$\mathcal{R}_{maj}$
which may contain Ω(n
3) elements, so any direct approach which explicitly constructs
$\mathcal{R}_{maj}$
requires Ω(n
3) time.
Found
Found
Top-30
Journals
|
1
|
|
|
Lecture Notes in Computer Science
1 publication, 100%
|
|
|
1
|
Publishers
|
1
|
|
|
Springer Nature
1 publication, 100%
|
|
|
1
|
- We do not take into account publications without a DOI.
- Statistics recalculated only for publications connected to researchers, organizations and labs registered on the platform.
- Statistics recalculated weekly.
Are you a researcher?
Create a profile to get free access to personal recommendations for colleagues and new articles.
Metrics
Cite this
GOST |
RIS |
BibTex
Cite this
GOST
Copy
Jansson J., SUNG W. Constructing the R* Consensus Tree of Two Trees in Subcubic Time // Lecture Notes in Computer Science. 2010. pp. 573-584.
GOST all authors (up to 50)
Copy
Jansson J., SUNG W. Constructing the R* Consensus Tree of Two Trees in Subcubic Time // Lecture Notes in Computer Science. 2010. pp. 573-584.
Cite this
RIS
Copy
TY - GENERIC
DO - 10.1007/978-3-642-15775-2_49
UR - https://doi.org/10.1007/978-3-642-15775-2_49
TI - Constructing the R* Consensus Tree of Two Trees in Subcubic Time
T2 - Lecture Notes in Computer Science
AU - Jansson, Jesper
AU - SUNG, WING-KIN
PY - 2010
DA - 2010/09/01
PB - Springer Nature
SP - 573-584
SN - 0302-9743
SN - 1611-3349
SN - 1861-2075
SN - 1861-2083
ER -
Cite this
BibTex (up to 50 authors)
Copy
@incollection{2010_Jansson,
author = {Jesper Jansson and WING-KIN SUNG},
title = {Constructing the R* Consensus Tree of Two Trees in Subcubic Time},
publisher = {Springer Nature},
year = {2010},
pages = {573--584},
month = {sep}
}