Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/74167
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.
URI: http://hdl.handle.net/10397/74167
ISSN: 0890-5401
EISSN: 1090-2651
DOI: 10.1016/j.ic.2017.08.002
Appears in Collections:Journal/Magazine Article

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

Page view(s)

2
Citations as of May 20, 2018

Google ScholarTM

Check

Altmetric


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