Kernelizations for the hybridization number problem on multiple nonbinary trees

DOI10.1007/978-3-319-12340-0_25zbMATH Open1342.68169arXiv1311.4045OpenAlexW2569932043MaRDI QIDQ2945199FDOQ2945199

Authors: Leo Van Iersel, Steven Kelk 

Publication date: 9 September 2015

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Abstract: Given a finite set $X$, a collection $mathcalT$ of rooted phylogenetic trees on $X$ and an integer $k$, the Hybridization Number problem asks if there exists a phylogenetic network on $X$ that displays all trees from $mathcalT$ and has reticulation number at most $k$. We show two kernelization algorithms for Hybridization Number, with kernel sizes $4k(5k{)}^t$ and $20k^2(Delt{a}^{+}-1)$ respectively, with $t$ the number of input trees and $Delt{a}^{+}$ their maximum outdegree. Experiments on simulated data demonstrate the practical relevance of these kernelization algorithms. In addition, we present an $n^{f(k)}t$-time algorithm, with $n=|X|$ and $f$ some computable function of $k$.

Full work available at URL: https://arxiv.org/abs/1311.4045

Recommendations

• Kernelizations for the hybridization number problem on multiple nonbinary trees
• A quadratic kernel for computing the hybridization number of multiple trees
• Hybridization number on three rooted binary trees is EPT
• On unrooted and root-uncertain variants of several well-known phylogenetic network problems
• Attaching leaves and picking cherries to characterise the hybridisation number for a set of phylogenies

Mathematics Subject Classification ID

Problems related to evolution (92D15) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited In (6)

• Attaching leaves and picking cherries to characterise the hybridisation number for a set of phylogenies
• Computing the minimum number of hybridization events for a consistent evolutionary history
• Kernelizations for the hybridization number problem on multiple nonbinary trees
• Hybridization number on three rooted binary trees is EPT
• The hybrid number of a ploidy profile
• A quadratic kernel for computing the hybridization number of multiple trees

This page was built for publication: Kernelizations for the hybridization number problem on multiple nonbinary trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2945199)