Kernelizations for the hybridization number problem on multiple nonbinary trees

Journal article (2016)

Authors

L.J.J. van Iersel Discrete Mathematics and Optimization - EEMCS
Steven Kelk Universiteit Maastricht
Celine Scornavacca Université de Montpellier
Research Group
Discrete Mathematics and Optimization (EEMCS) (TU Delft)
Phylogenetic network Phylogenetic tree Kernelization Fixed-parameter tractability Hybridization number
More Info
expand_more

Published Date

2016

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Delft Institute of Applied Mathematics

Research Group

Discrete Mathematics and Optimization

Abstract

Given a finite set X, a collection Tof rooted phylogenetic trees on Xand an integerk, theHybridization Numberproblem asks if there exists a phylogenetic network onXthat displays all trees fromTand has reticulation number at mostk. We show two kernelization algorithms forHybridization Number, with kernel sizes 4k(5k)tand 20k2(+−1)respectively, withtthe number of input trees and+their maximum outdegree. Experiments on simulated data demonstrate the practical relevance of our kernelization algorithms. In addition, we present an nf(k)t-time algorithm, with n =|X|and fsome computable function ofk.