A Practical Fixed-Parameter Algorithm for Constructing Tree-Child Networks from Multiple Binary Trees

DOI10.1007/S00453-021-00914-8MaRDI QIDQ6322366arXivFDO

Authors Leo Van Iersel, Remie Janssen, Mark P. Jones, Yukihiro Murakami, Norbert Zeh

Publication date 19 July 2019

Published in arXiv

Full work available at URL https://doi.org/10.1007/S00453-021-00914-8

Mathematics Subject Classification ID

Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Problems related to evolution (92D15)

arXiv classification

cs.DMmath.COq-bio.PE

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((8k{)}^{k}mathrmpoly(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.

This page was built for publication: A Practical Fixed-Parameter Algorithm for Constructing Tree-Child Networks from Multiple Binary Trees

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