Biology Reference
In-Depth Information
trade-off between the quality of the initial tree and the diversity (and
hence exploration of a large space of trees). Extensive simulations,
beyond the scope of this chapter, show that choosing
p
=
O
(1/ log(
n
))
gives a very good trade-off.
3.2. Heuristics
The heuristics we present in this section include four that have also been
described by Felsenstein
26
: nearest-neighbor interchange (NNI), subtree
pruning and regrafting (SPR), tree bisection reconnection (TBR), and
tree fusing. Additionally, we describe the heuristics
n
-optim (an exten-
sion of NNI) and reduce best-fitting subtree (RBFS). RBFS is new to the
best of our knowledge.
3.2.1. n-optim
This is a local heuristic that identifies a pattern subtree and attempts to
improve the quality by permuting it. We call it
n
-optim, or a pattern sub-
tree with
n
leaves. Felsenstein's NNI corresponds to 4-optim. For a given
quartet with the subtrees labeled by
A
,
B
,
C
and
D
A
C
B
D
4-optim operates by considering the two other rearrangements (symme-
tries are not relevant):
A
B
A
B
C
D
D
C
