New FPT algorithms for finding the temporal hybridization number for sets of phylogenetic trees
S.J. Borst (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Leo van van Iersel – Mentor (TU Delft - Discrete Mathematics and Optimization)
More Info
expand_more
Implementations of the algorithms introduced in this thesis
https://github.com/mathcals/temporal_hybridization_numberOther 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.
Abstract
We study the problem of finding a temporal hybridization network for a set of phylogenetic trees that minimizes the number of reticulations. First, we introduce an FPT algorithm for this problem on an arbitrary set of t binary trees with n leaves each with a running time of O(5^k*n*m) where k is the minimum temporal hybridization number. We also present the concept of temporal distance, which is a measure for how close a tree-child network is to being temporal. Then we introduce an algorithm for computing a tree-child network with temporal distance at most p and at most k reticulations in O((8k)^p*5^k*n*m). Lastly, we introduce a O(6^k*k!*n) algorithm for computing a minimum temporal hybridization network for a set of two nonbinary trees.