论文标题
循环发电机和Rooted子树修剪距离的改进线性内核
Cyclic generators and an improved linear kernel for the rooted subtree prune and regraft distance
论文作者
论文摘要
两个根二元系统发育树之间的根subtre Prune和Repraft（RSPR）距离是对拓扑差异的良好量度，是NP-HARD的拓扑差异。在这里，我们描述了该问题的改进线性内核。特别是，我们表明，如果经典的子树和链条还原规则通过修改的链减少规则增强，则最多的树木最多具有9k-3叶，其中k是RSPR距离；而且这个界限很紧。以前最著名的线性内核具有O（28K）。为了实现这种改进，我们引入了环状发电机，可以将其视为系统发育网络文献中使用的发电机的循环类似物。作为我们的主要结果的推论，我们还为两根生根二元系统发育树的最小杂交问题提供了改进的加权线性内核。
The rooted subtree prune and regraft (rSPR) distance between two rooted binary phylogenetic trees is a well-studied measure of topological dissimilarity that is NP-hard to compute. Here we describe an improved linear kernel for the problem. In particular, we show that if the classical subtree and chain reduction rules are augmented with a modified type of chain reduction rule, the resulting trees have at most 9k-3 leaves, where k is the rSPR distance; and that this bound is tight. The previous best-known linear kernel had size O(28k). To achieve this improvement we introduce cyclic generators, which can be viewed as cyclic analogues of the generators used in the phylogenetic networks literature. As a corollary to our main result we also give an improved weighted linear kernel for the minimum hybridization problem on two rooted binary phylogenetic trees.
