License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.WABI.2023.4
URN: urn:nbn:de:0030-drops-186309
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18630/
Go to the corresponding LIPIcs Volume Portal

Arasti, Shayesteh ; Mirarab, Siavash

Optimal Subtree Prune and Regraft for Quartet Score in Sub-Quadratic Time

pdf-format:
LIPIcs-WABI-2023-4.pdf (2 MB)

Abstract

Finding a tree with the minimum total distance to a given set of trees (the median tree) is increasingly needed in phylogenetics. Defining tree distance as the number of induced four-taxon unrooted (i.e., quartet) trees with different topologies, the median of a set of gene trees is a statistically consistent estimator of the species tree under several models of gene tree species tree discordance. Because of this, median trees defined with quartet distance are widely used in practice for species tree inference. Nevertheless, the problem is NP-Hard and the widely-used solutions are heuristics. In this paper, we pave the way for a new type of heuristic solution to this problem. We show that the optimal place to add a subtree of size m onto a tree with n leaves can be found in time that grows quasi-linearly with n and is nearly independent of m. This algorithm can be used to perform subtree prune and regraft (SPR) moves efficiently, which in turn enables the hill-climbing heuristic search for the optimal tree. In exploratory experiments, we show that our algorithm can improve the quartet score of trees obtained using the existing widely-used methods.

BibTeX - Entry

@InProceedings{arasti_et_al:LIPIcs.WABI.2023.4,
  author =	{Arasti, Shayesteh and Mirarab, Siavash},
  title =	{{Optimal Subtree Prune and Regraft for Quartet Score in Sub-Quadratic Time}},
  booktitle =	{23rd International Workshop on Algorithms in Bioinformatics (WABI 2023)},
  pages =	{4:1--4:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-294-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{273},
  editor =	{Belazzougui, Djamal and Ouangraoua, A\"{i}da},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18630},
  URN =		{urn:nbn:de:0030-drops-186309},
  doi =		{10.4230/LIPIcs.WABI.2023.4},
  annote =	{Keywords: Phylogenetics, Gene tree discordance, Quartet score, Quartet distance, Subtree prune and regraft, Tree search, ASTRAL}
}

Keywords: Phylogenetics, Gene tree discordance, Quartet score, Quartet distance, Subtree prune and regraft, Tree search, ASTRAL
Collection: 23rd International Workshop on Algorithms in Bioinformatics (WABI 2023)
Issue Date: 2023
Date of publication: 29.08.2023
Supplementary Material: Text (Figures): https://doi.org/10.6084/m9.figshare.23582676

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