Fixed-Parameter Algorithm for Hybridization Number of Two Multifurcating Trees

Abstract

Phylogenetic trees are used to represent the evolution of a set of species. However, this history may include reticulation events where taxa acquire genes from more than one ancestor or from contemporaries, which leads to non-tree-like ancestry relationships that cannot be represented using trees alone. Hybridization networks can be used to model such histories. The hybridization number is NP-hard to compute and we present a fixed-parameter algorithm to compute the hybridization number (and a corresponding network) of two multifurcating trees. The running time of our algorithm is $O(4.83^{k}n)$, where $k$ is the computed hybridization number, which is more efficient than two previous algorithms with complexity $O(2^{n}poly(n))$ and $O((6^{k}k!)poly(n))$, respectively. We verified the practicality of our algorithm by implementing it and evaluating its performance on real data. Our algorithm is obtained using a non-trivial combination of novel ideas with techniques from previous algorithms for multifurcating SPR distance and binary hybridization number.