Biology Reference
In-Depth Information
points. As a simple rule of thumb, start n optimizations for a tree with
n
leaves. As mentioned above, the optimization starting at different ran-
dom points can easily be done in parallel.
f
We close this section with an important observation. When the
objective function can be computed bottom-up, the NNI and
k
-optim
heuristics offer an interesting alternative. Let us assume that what is
meant by bottom-up computation is that the objective function infor-
mation of every subtree can be stored in the subtree in constant space
and that it can be recomputed in constant time from the information
from its two descendant nodes.
g
This is the case for parsimony and ML.
To take advantage of this, we will store in every internal node the three
records/values
h
of each of its subtrees. Once this is done, the objective
function for each NNI rearrangement can be computed in constant time.
When the tree is improved, some of these records/values have to be
recomputed. The strategy pays off because the number of times we evaluate
the optimality for heuristics vastly exceeds the times that we are successful
with an interchange.
4. Least Squares Tree Construction
In this section, we present the WLS tree building program Least
Squares Tree (LST) developed by our research group. The first subsec-
tion gives a high-level description of the program. In the second sub-
section, we compare the running times of our implementation with the
times of the corresponding program in PAUP*. The last subsection is
a “specialist” section where we describe in detail the application of the
RBFS heuristic.
4.1. Least Squares Tree Function in Darwin
Our function LST is implemented in Darwin.
27
Darwin is a programming
environment with its own interpreted language and a growing library of
f
In the jargon of parallel computing, this is called “embarrassingly parallel”.
g
Constant size and space are in relation to the size of the tree.
h
In an unrooted tree, every internal node can be grown bottom-up from three directions.
