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.ESA.2017.56
URN: urn:nbn:de:0030-drops-78819
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7881/
Go to the corresponding LIPIcs Volume Portal

Li, Zhijiang ; Zeh, Norbert

Computing Maximum Agreement Forests without Cluster Partitioning is Folly

pdf-format:
LIPIcs-ESA-2017-56.pdf (0.7 MB)

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.

BibTeX - Entry

@InProceedings{li_et_al:LIPIcs:2017:7881,
  author =	{Zhijiang Li and Norbert Zeh},
  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 =	{Kirk Pruhs and Christian Sohler},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7881},
  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}
}

Keywords: fixed-parameter tractability, agreement forests, hybridization, subtree prune-and-regraft
Collection: 25th Annual European Symposium on Algorithms (ESA 2017)
Issue Date: 2017
Date of publication: 01.09.2017

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