Back to Search Start Over

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

Authors :
Borst, Sander
van Iersel, Leo
Jones, Mark
Kelk, Steven
Source :
Algorithmica. Jul2022, Vol. 84 Issue 7, p2050-2087. 38p.
Publication Year :
2022

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. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
01784617
Volume :
84
Issue :
7
Database :
Academic Search Index
Journal :
Algorithmica
Publication Type :
Academic Journal
Accession number :
157613813
Full Text :
https://doi.org/10.1007/s00453-022-00946-8