## Abstract

We study the problem of finding a temporal hybridization network containing at most k reticulations, for an input consisting of a set of phylogenetic trees. First, we introduce an FPT algorithm for the problem on an arbitrary set of m binary trees with n leaves each with a running time of O(5 ^{k}· n· m). We also present the concept of temporal distance, which is a measure for how close a tree-child network is to being temporal. Then we introduce an algorithm for computing a tree-child network with temporal distance at most d and at most k reticulations in O((8 k) ^{d}5 ^{k}· k· n· m) time. Lastly, we introduce an O(6 ^{k}k! · k· n^{2}) time algorithm for computing a temporal hybridization network for a set of two nonbinary trees. We also provide an implementation of all algorithms and an experimental analysis on their performance.

Original language | English |
---|---|

Pages (from-to) | 2050-2087 |

Number of pages | 38 |

Journal | Algorithmica |

Volume | 84 |

Issue number | 7 |

DOIs | |

Publication status | Published - 2022 |

## Keywords

- Hybridization number
- Parameterized algorithms
- Phylogenetic networks
- Phylogenetic trees