Biology Reference
In-Depth Information
and then compute
Ê
Á
ˆ
˜
d
-
l
d
-
l
2
,
AX
A
BX
B
d
=
+
s
RX
RX
2
2
s
s
AX
BX
where
-
1
Ê
Á
ˆ
˜
1
1
2
.
s
=
+
RX
2
2
s
s
AX
BX
The global strategy of LST is based on the following empirical
observations and facts:
(a)
The 4-optim heuristic is about four times less expensive to run than
5-optim or 6-optim. Consequently, it should be run first.
(b)
It is a bad idea to restart the iteration of a heuristic as soon as an
improvement is found. It is better to complete the iteration over all
edges and, if there was an improvement, redo it. (If there are too
many improvements, restarting after every improvement results in a
O ( n 2 ) behavior.)
(c)
We found it better to interleave 4-optim iterations with 5-optim and
6-optim iterations, i.e. run cyclically 4-, 5-, and 6-optim until three
in a row do not produce an improvement.
The kernel function has two convenient additional capabilities:
(a)
In a single call, a number of trees can be generated and optimized
and only the best is returned. This saves all of the checking and
setup times for internal structures.
(b)
An initial topology can be given, from which the optimization can
start.
Once a pass of 4-5-6-optim over all possible edges does not produce
any improvement, the NNI cannot be continued. In this case, the kernel
heuristic does not try other heuristics and returns. The standard procedure
Search WWH ::




Custom Search