Please use this identifier to cite or link to this item:
Title: On finding the Adams consensus tree
Authors: Jansson, J 
Li, Z
Sung, WK
Keywords: Adams consensus
Centroid path
Phylogenetic tree
Wavelet tree
Issue Date: 2017
Publisher: Academic Press
Source: Information and computation, 2017, v. 256, p. 334-347 How to cite?
Journal: Information and computation 
Abstract: This article presents a fast algorithm for finding the Adams consensus tree of a set of conflicting phylogenetic trees with identical leaf labels. Its worst-case running time is O(knlog⁡n), where k is the number of input trees and n is the size of the leaf label setMergeCell in comparison, the original algorithm of Adams has a worst-case running time of O(kn2). To achieve subquadratic running time, the centroid path decomposition technique is applied in a novel way that traverses the input trees by following a centroid path in each of them in unison. For k=2, an even faster algorithm running in O(n⋅[Formula presented]) time is provided, which relies on an extension of the wavelet tree-based technique of Bose et al. for orthogonal range counting on a grid. Our extended wavelet tree data structure also supports truncated range maximum/minimum queries efficiently.
ISSN: 0890-5401
EISSN: 1090-2651
DOI: 10.1016/j.ic.2017.08.002
Appears in Collections:Journal/Magazine Article

View full-text via PolyU eLinks SFX Query
Show full item record

Page view(s)

Last Week
Last month
Citations as of Mar 25, 2019

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.