论文标题
系统发育基因的最大简约距离：线性内核和常数因子近似算法
Maximum parsimony distance on phylogenetictrees: a linear kernel and constant factor approximation algorithm
论文作者
论文摘要
最大简约距离是一种量度，用于量化两条未根源的系统发育树的差异。计算是NP的，由于其复杂的组合结构，很少有正算法结果已知。在这里，我们通过证明该问题是固定参数可处理的，解决了这一缺点。我们通过建立线性内核来做到这一点，即在应用某些还原规则后，所得实例的大小由距离的线性函数界定。作为此结果的强大推论，我们证明该问题允许多项式恒定因子近似算法。系统发育学中遇到的天然辅助图结构的树宽是距离的函数。距离在两棵树的最大一致森林的恒定因素之内，这是一种在系统发育学中进行的经过良好研究的物体。
Maximum parsimony distance is a measure used to quantify the dissimilarity of two unrooted phylogenetic trees. It is NP-hard to compute, and very few positive algorithmic results are known due to its complex combinatorial structure. Here we address this shortcoming by showing that the problem is fixed parameter tractable. We do this by establishing a linear kernel i.e., that after applying certain reduction rules the resulting instance has size that is bounded by a linear function of the distance. As powerful corollaries to this result we prove that the problem permits a polynomial-time constant-factor approximation algorithm; that the treewidth of a natural auxiliary graph structure encountered in phylogenetics is bounded by a function of the distance; and that the distance is within a constant factor of the size of a maximum agreement forest of the two trees, a well studied object in phylogenetics.
