文章基本信息

标题：On Finding the Adams Consensus Tree
本地全文：下载
作者：Jesper Jansson ; Zhaoxian Li ; Wing-Kin Sung 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2015
卷号：30
页码：487-499
DOI：10.4230/LIPIcs.STACS.2015.487
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：This paper presents a fast algorithm for finding the Adams consensus tree of a set of conflicting phylogenetic trees with identical leaf labels, for the first time improving the time complexity of a widely used algorithm invented by Adams in 1972 [1]. Our algorithm applies the centroid path decomposition technique [9] in a new way to traverse the input trees' centroid paths in unison, and runs in O(k n \log n) time, where k is the number of input trees and n is the size of the leaf label set. (In comparison, the old algorithm from 1972 has a worst-case running time of O(k n^2).) For the special case of k = 2, an even faster algorithm running in O(n \cdot \frac{\log n}{\log\log n}) time is provided, which relies on an extension of the wavelet tree-based technique by Bose et al. [6] for orthogonal range counting on a grid. Our extended wavelet tree data structure also supports truncated range maximum queries efficiently and may be of independent interest to algorithm designers.
关键词：phylogenetic tree; Adams consensus; centroid path; wavelet tree