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

Please use this identifier to cite or link to this item: https://doi.org/10.1007/978-3-642-15775-2_49

Title:	Constructing the R* consensus tree of two trees in subcubic time
Authors:	Jansson, J. Sung, W.-K.
Issue Date:	2010
Citation:	Jansson, J.,Sung, W.-K. (2010). Constructing the R* consensus tree of two trees in subcubic time. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 6346 LNCS (PART 1) : 573-584. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-642-15775-2_49
Abstract:	The previously fastest algorithms for computing the Rconsensus 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 ℛ maj which may contain Ω(n 3) elements, so any direct approach which explicitly constructs ℛ maj requires Ω(n 3) time. © 2010 Springer-Verlag.
Source Title:	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
URI:	http://scholarbank.nus.edu.sg/handle/10635/41174
ISBN:	3642157742
ISSN:	03029743
DOI:	10.1007/978-3-642-15775-2_49
Appears in Collections:	Staff Publications

There are no files associated with this item.

Check