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

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

van Iersel, L.J.J. (TU Delft Discrete Mathematics and Optimization)
Janssen, R. (TU Delft Discrete Mathematics and Optimization)
Jones, M.E.L. (TU Delft Discrete Mathematics and Optimization)
Murakami, Yukihiro (TU Delft Discrete Mathematics and Optimization)
Zeh, Norbert (Dalhousie University)

2022

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.

Fixed-parameter algorithms
Hybridization number
Phylogenetic networks

http://resolver.tudelft.nl/uuid:70e72477-d616-4b6f-a275-f16df603453b

https://doi.org/10.1007/s00453-021-00914-8

2022-08-31

0178-4617

Algorithmica, 84 (4), 917-960

Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

Institutional Repository

journal article

© 2022 L.J.J. van Iersel, R. Janssen, M.E.L. Jones, Yukihiro Murakami, Norbert Zeh