New FPT Algorithms for Finding the Temporal Hybridization Number for Sets of Phylogenetic Trees

Sander Borst, Leo van Iersel*, Mark Jones, Steven Kelk

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

2 Citations (Scopus)
42 Downloads (Pure)

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) d5 k· k· n· m) time. Lastly, we introduce an O(6 kk! · k· n2) 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 languageEnglish
Pages (from-to)2050-2087
Number of pages38
JournalAlgorithmica
Volume84
Issue number7
DOIs
Publication statusPublished - 2022

Keywords

  • Hybridization number
  • Parameterized algorithms
  • Phylogenetic networks
  • Phylogenetic trees

Fingerprint

Dive into the research topics of 'New FPT Algorithms for Finding the Temporal Hybridization Number for Sets of Phylogenetic Trees'. Together they form a unique fingerprint.

Cite this