License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2020.105
URN: urn:nbn:de:0030-drops-125122
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12512/
Go to the corresponding LIPIcs Volume Portal

Wu, Hongxun

Near-Optimal Algorithm for Constructing Greedy Consensus Tree

pdf-format:
LIPIcs-ICALP-2020-105.pdf (0.5 MB)

Abstract

In biology, phylogenetic trees are important tools for describing evolutionary relations, but various data sources may result in conflicting phylogenetic trees. To summarize these conflicting phylogenetic trees, consensus tree methods take k conflicting phylogenetic trees (each with n leaves) as input and output a single phylogenetic tree as consensus.
Among the consensus tree methods, a widely used method is the greedy consensus tree. The previous fastest algorithms for constructing a greedy consensus tree have time complexity Õ(kn^1.5) [Gawrychowski, Landau, Sung, Weimann 2018] and Õ(k²n) [Sung 2019] respectively. In this paper, we improve the running time to Õ(kn). Since k input trees have Θ(kn) nodes in total, our algorithm is optimal up to polylogarithmic factors.

BibTeX - Entry

@InProceedings{wu:LIPIcs:2020:12512,
  author =	{Hongxun Wu},
  title =	{{Near-Optimal Algorithm for Constructing Greedy Consensus Tree}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{105:1--105:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Artur Czumaj and Anuj Dawar and Emanuela Merelli},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12512},
  URN =		{urn:nbn:de:0030-drops-125122},
  doi =		{10.4230/LIPIcs.ICALP.2020.105},
  annote =	{Keywords: phylogenetic trees, greedy consensus trees, splay tree}
}

Keywords: phylogenetic trees, greedy consensus trees, splay tree
Collection: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Issue Date: 2020
Date of publication: 29.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI