期刊
ALGORITHMICA
卷 84, 期 7, 页码 2050-2087出版社
SPRINGER
DOI: 10.1007/s00453-022-00946-8
关键词
Parameterized algorithms; Phylogenetic networks; Phylogenetic trees; Hybridization number
资金
- Netherlands Organization for Scientific Research (NWO) [639.072.602]
- NWO
This study addresses the problem of calculating temporal hybridization networks with certain conditions for a set of phylogenetic trees, and proposes corresponding algorithms and measurement methods.
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((8k)(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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据