کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950594 | 1440713 | 2017 | 14 صفحه PDF | دانلود رایگان |
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 set; 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â logâ¡nlogâ¡logâ¡n) 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.
Journal: Information and Computation - Volume 256, October 2017, Pages 334-347