1 Search Results for "Li, Zhijiang"

Document
DOI: 10.4230/LIPIcs.ESA.2017.56
Computing Maximum Agreement Forests without Cluster Partitioning is Folly

Authors: Zhijiang Li and Norbert Zeh

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
Computing a maximum (acyclic) agreement forest (M(A)AF) of a pair of phylogenetic trees is known to be fixed-parameter tractable; the two main techniques are kernelization and depth-bounded search. In theory, kernelization-based algorithms for this problem are not competitive, but they perform remarkably well in practice. We shed light on why this is the case. Our results show that, probably unsurprisingly, the kernel is often much smaller in practice than the theoretical worst case, but not small enough to fully explain the good performance of these algorithms. The key to performance is cluster partitioning, a technique used in almost all fast M(A)AF algorithms. In theory, cluster partitioning does not help: some instances are highly clusterable, others not at all. However, our experiments show that cluster partitioning leads to substantial performance improvements for kernelization-based M(A)AF algorithms. In contrast, kernelizing the individual clusters before solving them using exponential search yields only very modest performance improvements or even hurts performance; for the vast majority of inputs, kernelization leads to no reduction in the maximal cluster size at all. The choice of the algorithm applied to solve individual clusters also significantly impacts performance, even though our limited experiment to evaluate this produced no clear winner; depth-bounded search, exponential search interleaved with kernelization, and an ILP-based algorithm all achieved competitive performance.
Cite as

Zhijiang Li and Norbert Zeh. Computing Maximum Agreement Forests without Cluster Partitioning is Folly. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 56:1-56:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.ESA.2017.56,
  author =	{Li, Zhijiang and Zeh, Norbert},
  title =	{{Computing Maximum Agreement Forests without Cluster Partitioning is Folly}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{56:1--56:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.56},
  URN =		{urn:nbn:de:0030-drops-78819},
  doi =		{10.4230/LIPIcs.ESA.2017.56},
  annote =	{Keywords: fixed-parameter tractability, agreement forests, hybridization, subtree prune-and-regraft}
}
  • Refine by Author
  • 1 Li, Zhijiang
  • 1 Zeh, Norbert

  • Refine by Classification

  • Refine by Keyword
  • 1 agreement forests
  • 1 fixed-parameter tractability
  • 1 hybridization
  • 1 subtree prune-and-regraft

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

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