论文标题
在系统发育学中的树一分配和重新连接（TBR）距离的深核化
Deep kernelization for the Tree Bisection and Reconnnect (TBR) distance in phylogenetics
论文作者
论文摘要
我们描述了9K-8大小的内核，用于计算树一分配和重新连接（TBR）距离K之间的NP硬化问题，k之间的两个未根的二元系统发育树之间的距离。我们通过使用三个新的新还原规则扩展现有的减少规则组合来实现这一目标。其中两个规则是基于以远距离进行拓扑转换树的想法，以确保执行早期的还原规则。第三个规则将（Kelk和Linz，Combinatorics 24（3），2020年）中引入的本地邻域方法扩展到了更多的全球结构，从而允许删除叶子肯定会将TBR距离降低时，可以鉴定出新的情况。内核大小上的绑定到一个添加术语。我们的结果还适用于在两条未根的二元系统发育树之间计算最大一致森林（MAF）的同等问题。我们预计我们的结果将更加广泛地适用于计算基于协议 - 森林的差异措施。
We describe a kernel of size 9k-8 for the NP-hard problem of computing the Tree Bisection and Reconnect (TBR) distance k between two unrooted binary phylogenetic trees. We achieve this by extending the existing portfolio of reduction rules with three novel new reduction rules. Two of the rules are based on the idea of topologically transforming the trees in a distance-preserving way in order to guarantee execution of earlier reduction rules. The third rule extends the local neighbourhood approach introduced in (Kelk and Linz, Annals of Combinatorics 24(3), 2020) to more global structures, allowing new situations to be identified when deletion of a leaf definitely reduces the TBR distance by one. The bound on the kernel size is tight up to an additive term. Our results also apply to the equivalent problem of computing a Maximum Agreement Forest (MAF) between two unrooted binary phylogenetic trees. We anticipate that our results will be more widely applicable for computing agreement-forest based dissimilarity measures.
