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.WABI.2019.12
URN: urn:nbn:de:0030-drops-110420
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11042/
Go to the corresponding LIPIcs Volume Portal

Markin, Alexey ; Eulenstein, Oliver

Consensus Clusters in Robinson-Foulds Reticulation Networks

pdf-format:
LIPIcs-WABI-2019-12.pdf (0.5 MB)

Abstract

Inference of phylogenetic networks - the evolutionary histories of species involving speciation as well as reticulation events - has proved to be an extremely challenging problem even for smaller datasets easily tackled by supertree inference methods. An effective way to boost the scalability of distance-based supertree methods originates from the Pareto (for clusters) property, which is a highly desirable property for phylogenetic consensus methods. In particular, one can employ strict consensus merger algorithms to boost the scalability and accuracy of supertree methods satisfying Pareto; cf. SuperFine. In this work, we establish a Pareto-like property for phylogenetic networks. Then we consider the recently introduced RF-Net method that heuristically solves the so-called RF-Network problem and which was demonstrated to be an efficient and effective tool for the inference of hybridization and reassortment networks. As our main result, we provide a constructive proof (entailing an explicit refinement algorithm) that the Pareto property applies to the RF-Network problem when the solution space is restricted to the popular class of tree-child networks. This result implies that strict consensus merger strategies, similar to SuperFine, can be directly applied to boost both accuracy and scalability of RF-Net significantly. Finally, we further investigate the optimum solutions to the RF-Network problem; in particular, we describe structural properties of all optimum (tree-child) RF-networks in relation to strict consensus clusters of the input trees.

BibTeX - Entry

@InProceedings{markin_et_al:LIPIcs:2019:11042,
  author =	{Alexey Markin and Oliver Eulenstein},
  title =	{{Consensus Clusters in Robinson-Foulds Reticulation Networks}},
  booktitle =	{19th International Workshop on Algorithms in Bioinformatics (WABI 2019)},
  pages =	{12:1--12:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-123-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{143},
  editor =	{Katharina T. Huber and Dan Gusfield},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11042},
  URN =		{urn:nbn:de:0030-drops-110420},
  doi =		{10.4230/LIPIcs.WABI.2019.12},
  annote =	{Keywords: Phylogenetics, phylogenetic tree, phylogenetic network, reticulation network, Robinson-Foulds, Pareto, RF-Net}
}

Keywords: Phylogenetics, phylogenetic tree, phylogenetic network, reticulation network, Robinson-Foulds, Pareto, RF-Net
Collection: 19th International Workshop on Algorithms in Bioinformatics (WABI 2019)
Issue Date: 2019
Date of publication: 03.09.2019

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