Department of Computer Science, Technical University of Catalonia, Barcelona, Spain.
BMC Evol Biol. 2010 Oct 29;10:334. doi: 10.1186/1471-2148-10-334.
Recently, Hill et al. 1 implemented a new software package--called SPRIT--which aims at calculating the minimum number of horizontal gene transfer events that is needed to simultaneously explain the evolution of two rooted binary phylogenetic trees on the same set of taxa. To this end, SPRIT computes the closely related so-called rooted subtree prune and regraft distance between two phylogenies. However, calculating this distance is an NP-hard problem and exact algorithms are often only applicable to small- or medium-sized problem instances. Trying to overcome this problem, Hill et al. propose a divide-and-conquer approach to speed up their algorithm and conjecture that this approach can be used to compute the rooted subtree prune and regraft distance exactly.
In this note, we present a counterexample to Hill et al's conjecture and subsequently show that a modified version of their conjecture holds.
While Hill et al's conjecture may result in an overestimate of the rooted subtree prune and regraft distance, a slightly more restricted version of their approach gives the desired outcome and can be applied to speed up the exact calculation of this distance between two phylogenies.
最近，Hill 等人 1 实施了一个新的软件包——称为 SPRIT——旨在计算同时解释同一组分类单元上的两个有根二叉系统发育树的进化所需的最少水平基因转移事件数。为此，SPRIT 计算两个系统发育树之间密切相关的所谓有根子树修剪和重新嫁接距离。然而，计算这个距离是一个 NP 难问题，精确算法通常只适用于小或中等规模的问题实例。为了克服这个问题，Hill 等人提出了一种分而治之的方法来加速他们的算法，并推测这种方法可以用来精确计算有根子树修剪和重新嫁接距离。
在本注释中，我们给出了一个反例来反驳 Hill 等人的猜想，随后表明他们的猜想的一个修改版本成立。
虽然 Hill 等人的猜想可能导致有根子树修剪和重新嫁接距离的高估，但他们方法的一个略微受限的版本给出了所需的结果，并可用于加速两个系统发育树之间这个距离的精确计算。
