1 Search Results for "Li, Zhaoxian"

Document
DOI: 10.4230/LIPIcs.STACS.2015.487
On Finding the Adams Consensus Tree

Authors: Jesper Jansson, Zhaoxian Li, and Wing-Kin Sung

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract
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.
Cite as

Jesper Jansson, Zhaoxian Li, and Wing-Kin Sung. On Finding the Adams Consensus Tree. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 487-499, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{jansson_et_al:LIPIcs.STACS.2015.487,
  author =	{Jansson, Jesper and Li, Zhaoxian and Sung, Wing-Kin},
  title =	{{On Finding the Adams Consensus Tree}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{487--499},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.487},
  URN =		{urn:nbn:de:0030-drops-49364},
  doi =		{10.4230/LIPIcs.STACS.2015.487},
  annote =	{Keywords: phylogenetic tree, Adams consensus, centroid path, wavelet tree}
}
  • Refine by Author
  • 1 Jansson, Jesper
  • 1 Li, Zhaoxian
  • 1 Sung, Wing-Kin

  • Refine by Classification

  • Refine by Keyword
  • 1 Adams consensus
  • 1 centroid path
  • 1 phylogenetic tree
  • 1 wavelet tree

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2015

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact