2022-03-25
New FPT algorithms for finding the temporal hybridization number for sets of phylogenetic trees
Publication
Publication
Algorithmica , Volume 84 p. 2050- 2087
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.
| Additional Metadata | |
|---|---|
| , , , | |
| doi.org/10.1007/s00453-022-00946-8 | |
| Algorithmica | |
| Networks | |
| Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
|
Borst, S., van Iersel, L., Jones, M., & Kelk, S. (2022). New FPT algorithms for finding the temporal hybridization number for sets of phylogenetic trees. Algorithmica, 84, 2050–2087. doi:10.1007/s00453-022-00946-8 |
|
