Biology Reference
In-Depth Information
If any of the alternative orderings has a better score, we adopt it and
continue with the new tree. There are 2
n
3 internal edges in an
unrooted tree with
n
leaves, where
n
of them are attached to leaves. This
leaves
n
−
3 internal edges on which we can apply the test. Once the
heuristic has been successful in at least one place, it is usual to retry it in
all branches.
5-optim and 6-optim operate on the following patterns, respectively:
−
C
D
C
A
D
A
E
F
B
B
E
While these patterns are more powerful in searching the tree space and
finding better trees, the coding required to analyze all of the alternatives
becomes the limiting factor. 5-optim requires 15 cases and can be
applied, in some cases, in three different ways on each internal node.
Complete analysis of 6-optim requires 105 cases.
3.2.2. Subtree pruning and regrafting (SPR)
This heuristic considers each subtree of the tree, removes it from the tree,
and attempts to insert it in a different position. The number of subtrees
in an unrooted tree is three times the number of internal nodes, so 3n
−
6. The total number of regrafting attempts is
O
(
n
2
).
3.2.3. Tree bisection reconnection (TBR)
TBR takes the basic idea of SPR further. An interior branch of the tree is
removed. The two resulting subtrees are then reconnected at a branch of
one and a branch of the other. There are
O
(
n
2
) possible reconnections.
Consequently, the total number of possible TBR rearrangements is
O
(
n
3
).
