Subtree Pruning And Regrafting is a tree topology search strategy
which attempts to improve the likelihood of a given tree by performing the
following operations on the tree.
First, select a subtree of the given tree. Next, we detach the
selected subtree and attempt to regraft it onto another branch of the remaining tree, in
such a way that a new tree is formed. For example, in the figures below, we select the subtree
with leaves 1 and 2 from the original six leaf tree. That leaves us with a 4 leaf tree which
has 5 branches. We regraft the (1,2) subtree to four of those (we omit one, because grafting
the (1,2) subtree to it would result in the same tree that we started with) to obtain new trees.
The procedure is usually repeated for each possible subtree and receiving branch, until no further likelihood
improvements can be obtained.
A single pass of the SPR algorithm examines $O(N^2)$ new trees, where
$N$ is the number of leaves in the original tree. This is because, for each subtree there are
$O(N)$ possible regraftings, and there are $O(N)$ possible subtrees to consider.
|
|
|
Figure 1.
Original Tree.
|
Figure 2.
Graft (1,2) onto 6.
|
Figure 3.
Graft (1,2) onto 5.
|
|
|
Figure 4.
Graft (1,2) onto
the internal branch
joining 5 and 6.
|
Figure 5.
Graft (1,2) onto 4.
|
|