A Practical Fixed-Parameter Algorithm for Constructing Tree-Child Networks from Multiple Binary Trees
L.J.J. Van Iersel (TU Delft - Discrete Mathematics and Optimization)
Remie Janssen (TU Delft - Discrete Mathematics and Optimization)
M.E.L. Jones (TU Delft - Discrete Mathematics and Optimization)
Yukihiro Murakami (TU Delft - Discrete Mathematics and Optimization)
Norbert Zeh (Dalhousie University)
More Info
expand_more
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.
Abstract
We present the first fixed-parameter algorithm for constructing a tree-child phylogenetic network that displays an arbitrary number of binary input trees and has the minimum number of reticulations among all such networks. The algorithm uses the recently introduced framework of cherry picking sequences and runs in O((8 k) kpoly (n, t)) time, where n is the number of leaves of every tree, t is the number of trees, and k is the reticulation number of the constructed network. Moreover, we provide an efficient parallel implementation of the algorithm and show that it can deal with up to 100 input trees on a standard desktop computer, thereby providing a major improvement over previous phylogenetic network construction methods.