Kernelizations for the hybridization number problem on multiple nonbinary trees

DOI10.1007/978-3-319-12340-0_25MaRDI QIDQ2945199zbMATH OpenOpenAlexFDO

Authors Leo Van Iersel, Steven Kelk

Publication date 9 September 2015

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

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

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)

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$.

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

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)