论文标题
用于寻找系统发育树集的时间杂交数的新FPT算法
New FPT algorithms for finding the temporal hybridization number for sets of phylogenetic trees
论文作者
论文摘要
我们研究了找到一组系统发育树的时间杂交网络的问题，该网络可最大程度地减少网状数量。首先，我们在任意的$ m $二进制树上为此问题引入了fpt算法，每个$ n $叶子的运行时间为$ o（5^k \ cdot n \ cdot m）$，其中$ k $是最小的时间杂交数量。我们还提出了时间距离的概念，这是衡量树木网络与暂时性的距离的衡量标准。然后，我们引入了一种用于计算最多$ d $的树孩子网络的算法，最多只有$ k $ o（（8k）^ d5^ k \ cdot n \ cdot m）$时间。最后，我们引入了一个$ O（6^kk！\ cdot k \ cdot n^2）$ time算法用于计算一组两种非二进制树的最小时间杂交网络。我们还提供了所有算法的实现以及对其性能的实验分析。
We study the problem of finding a temporal hybridization network for a set of phylogenetic trees that minimizes the number of reticulations. First, we introduce an FPT algorithm for this problem on an arbitrary set of $m$ binary trees with $n$ leaves each with a running time of $O(5^k\cdot n\cdot m)$, where $k$ is the minimum temporal hybridization number. 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)^d5^ k\cdot n\cdot m)$ time. Lastly, we introduce a $O(6^kk!\cdot k\cdot n^2)$ time algorithm for computing a minimum 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.
