Wu Yufeng
Department of Computer Science and Engineering, University of Connecticut, Storrs, CT 06269, USA.
Bioinformatics. 2009 Jan 15;25(2):190-6. doi: 10.1093/bioinformatics/btn606. Epub 2008 Nov 19.
Subtree prune and regraft (SPR) is one kind of tree rearrangements that has seen applications in solving several computational biology problems. The minimum number of rooted SPR ((r)SPR) operations needed to transform one rooted binary tree to another is called the (r)SPR distance between the two trees. Computing the (r)SPR distance has been actively studied in recent years. Currently, there is a lack of practical software tools for computing the (r)SPR distance for relatively large trees with large (r)SPR distance.
In this article, we present a simple and practical method that computes the exact (r)SPR distance with integer linear programming. By applying this new method on several simulated and real biological datasets, we show that our new method outperforms existing software tools in term of accuracy and efficiency. Our experimental results indicate that our method can compute the exact (r)SPR distance for many large trees with large (r)SPR distance.
子树剪接与重接（SPR）是一种树重排方式，已应用于解决多个计算生物学问题。将一棵有根二叉树转换为另一棵有根二叉树所需的最小有根SPR（(r)SPR）操作数称为这两棵树之间的(r)SPR距离。近年来，计算(r)SPR距离一直是研究热点。目前，缺乏实用的软件工具来计算具有较大(r)SPR距离的相对大树的(r)SPR距离。
在本文中，我们提出了一种简单实用的方法，通过整数线性规划来计算精确的(r)SPR距离。通过将这种新方法应用于多个模拟和真实生物数据集，我们表明，在准确性和效率方面，我们的新方法优于现有软件工具。我们的实验结果表明，我们的方法可以为许多具有较大(r)SPR距离的大树计算精确的(r)SPR距离。
