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

2019/07/19 by van Iersel, Leo, Janssen, Remie, Jones, Mark +2
#92D15 05C90 05C85 56R10 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Biological sciences #FOS: Computer and information sciences #FOS: Mathematics #Populations and Evolution (q-bio.PE)

paper · doi:10.48550/arxiv.1907.08474

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 poly(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.

Related

• Generation of orchard and tree-child networks
• The tree-child network problem for line trees and the shortest common supersequences for permutations
• Constructing Phylogenetic Networks via Cherry Picking and Machine Learning
• Computing the Bounds of the Number of Reticulations in a Tree-Child Network That Displays a Set of Trees
• Counting cherry reduction sequences is counting linear extensions (in phylogenetic tree-child networks)