Simplex
Introduction
A multiparticle refinement program is used to asses the
quality of the orientations by comparing the data from
different particles using the cross common lines residuals and to refine the orientations.
Several refinement runs are usually necessary. All five
orientation and origin parameters can be refined but usually
it is better to do these in seperate run. Obviously this is
the best point at which to gain an overview of the quality
of the data and to eliminate images which show poor correspondence
with the others. The simplex input format for each image entry
is identical to that for EMICOORG1 and EMICOMAT
This program refines image orientations against each
other. It has two modes: a gradient mode in which the
gradient of the change in residual for an individual
image compared to all the other images is used to change
the orientation of that image and a simplex mode in
which changes are made in the orientations of all images
at the same time by movements in the 4*(N_IMAGES) space
of conformations. Both modes are iterative and allow the
option of refining only some parameters and/or some images
and holding the rest constant. Both methods work on
the orientation angles and the origins. Frequently better
results will be found by refining the origin X,Y first and
then the orientations theta, phi, omega. And alternating
between these two modes. A third mode makes use of the NAG
library minimization routines and has found to be useful
only for the refinement of origins and has no significant
advantage over the other methods.
Recent additions to the method include the ability
to select the hand of the set of images during refinement
and the free residual .
Simplex method
The simplex method used is taken from
Numerical Methods for Unconstrained Optimization
ed W. Murray
Academic Press - 1972
The original method is
Spendly, Hext and Himsworth (1962)
Sequential application of simplex designs in
optimization and Evolutionary Operation,
Technometrics 4:441-461
and is the adaptation by
Nelder and Mead (1965)
A simplex method for function minimization
Comput. J. 7:308-313
The method begins with a starting value, here the
conformation or set of orientations for all images
(START) and adds N_VARY conformations to it so that
they all form a regular simplex, or set of equidistant
points in conformation space, of N_VARY+1 conformations.
This is the starting simplex. The residuals for each
member of the simplex are calculated and they are
so that the first has the lowest value and the
N_VARY+1'the has the highest. The first N_VARY are used
to generate a new point by reflecting the N_VARY+1'th
point through the center of mass of the N_VARY remaining
points. This is then tested and a new simplex point is
added based on the result.
if the resid of the test point is
- < resid(1)
the simplex is extended in that direction
- < resid(N)
the F(N+1)'th point is replaced and the iteration is complete
- >resid(N+1)
the simplex is too large and it
is contracted either by
contracting the value itself or,
if this produces a higher
residual again, by contracting
the entire simplex by motion
toward the best point.
Convergence is defined and the process of the
refinement are monitored on the basis of
the standard deviation of the residual
points.
> number of images to be correlated (I)
> range of radial scale factors SCLMIN,SCLMAX,DELSCL (3F)
allows variation of the radial sampling of the
each image transform independantly. To have no
variation use: 1.0,1.0,0.0 (the default)
> region of tranform to include RMIN,RMAX (2F)
This is in transform units so resolution =
Pixel_size*Transform_size/RMIN -> Pixel_size*Transform_size/RMIN
> INCR, NSAMPL (2I)
increment between bands and the number of
samples to take in each band
> DELTA_THETA, DELTA_PHI, DELTA_OMEGA, CYCLES,ERR_LIM,FMIN,
DELTA_X, DELTA_Y, NFLIP, NFREE
(3F,I,4F,2I)
DELTA_THETA...
Initial step size for orientation angles, to fix an
angle use 0.0 for step size.
CYCLES
Number of cycles of
refinement.
For the gradient method each step size is
tried for each image until there is no improvement in
residual or until N_SUB_CYCLES has been passed and
then the step size is decreased to 0.8 of the original.
This is one cycle. When one image continues to improve
but the others not at a given step size, the others are
held fixed while that one is refined. For the simplex
method a cycle is the testing of a new conformation of
images. When no new conformation is better at a given
step size, the whole simplex (or set of conformations)
is contracted by making delta for the generation of the
new simplex 0.8 of the original. Hence a simplex cycle
does not necessarily decrease the size of delta. Simplex
cycles are much faster than delta cycles but you need
more of them to accomplish the same movement of
particles.
The sign of cycles indicates which method to use.
- >0 - gradient method
- <0 - simplex method
- =-999 e04cgf method
in NAG13 this is e04jaf
- =0 - just calculate the error matrix for the
image comparisons.
ERROR_LIMIT (F)
To keep bad images from throwing off the entire
refinement, images with phase errors against another
image greater than this value are not included in the
refinement calculation. The are included in the final
error matrix calculation which is one reason that the
two values of residual disagree slightly. This should be
set high for the simplex method (180deg- this is now
done automatically if N_cycles <0) because the simplex fit
rapidly discovers that one way to improve the residual
over all images is to move the worst ones to to such bad
orientations that they exceed ERR_LIMIT and so make
no contribution. With the gradient method the value
allows the better images to be refined without
interference from the worst. The final residual
calculation is made without excluding the high error
values and so its residuals may not match those observed
during the refinement.
FMIN (F)
Cut off for tf values included and is used in
the same way as in EMICOFV
DELTA_X (F)
Initial step size for origin shift in X
DELTA_Y (F)
Initial step size for origin shift in Y
NFLIP (I)
indicates how often a hand selection is done. When
NFLIP =1, the hand is refined every cycle, when = 2 or N>1
it is done every second or N'th time. When =< 0 it it not selected
during refinement but rather is selected at the end before the
values are output. When <0, the hand is never selected. Hand
selection is SLOW for large numbers of images so you may want to
take advantage of the fact that the hand refinement can be turned
off.
If N_FLIP =< 0 no hand selection
will occur during refinement but the handedness residual
will be output at the end of the run. If N_FLIP > 0, the
best hand set will imposed during the 1st,N_FLIP+1'th,
2*N_FLIP+1'th, ... cycle of the refinement.
Setting N_FLIP to negative values causes no attempt to
calculate best hand even at the end of run
NFREE (I)
This controls the use of the free residual. If NFREE is set
greater than 0, the free residual is calculated. To do this
a random fraction of the common lines (25%) are removed from
each image. Refinement is performed for the remaining data. The
refined orientations and origins are then used to calculate the
residual for the refined data at the end of the refinement run
and then the residual is recalculated with the free data included.
The refinement is failing if the free residual is greater than the
residual calculated from only the refined data. This is based on the
idea that while minimization can low the residual of the data which
it is refining, it can only minimize the residual of the other data
if it is connnected to the refined data by icosahedral symmetry.
------- these parameters are followed by an entry for each image
>name of fft file
> particle origin ok? (0 or yes; 1 no)
> ORIGX, ORIGY (2F)
>orientation of particle THETA, PHI, OMEGA, SCALE (4F)
The orientation angles are in degrees and will be brought
back to the unit triangle if they are intially outside
it.The ANG_PER_PIXEL is the number of measurment units (A
for example) per pixel. It allows the program to refine
images taken at several different magnifications during the
same run. It will be useful for reasons of storage if the
highest magnifications are input first. If this is not the
case a warning will be issued
>TRIGGER_DELTA (F)
This values is compared to the sum of delta's for the
parameters and refinement of an image only occurs when it is
higher than the sum of deltas. This provides a means of allowing
only some images to refine at the coarser stages of refinement
while holding the rest fixed and then refining the rest at finer
values of delta. If an image is always to be held fixed, this
value should be set to -1.0. If or 0.0, TRIGGER_DELTA will
be set to 9999. so that the image will always be refined. The
handedness calculation will only change the hands on particles
with TRIGGER_DELTA lower than the current value of the delta for
refinement.
After refinement, the program outputs the refined positions
in the proper format for another simplex run and for
input to emicoorg1.
com file
corresponding log file
another com file
annotated com file
Modified by S.Fuller 24-sep-85 to calculate 10 common lines for
each view.
Modified to correlate multiple images
sdf 26-nov-1985
added options to refine up to 40 images at a time
added option for using all sixty common lines between images
TRMEET_EX
added option for enhanced refinement when only one delta is
non-zero
added option for getting resolution dependance of the
correlation
changed all image handling to the structure image and made
allocation of the image data arrays dynamic to speed up
the processing
sdf jan 9, 1987
added the simplex refinement method for refining all images
together rather than moving each seperately
sdf jan 20, 1987
fixed bug in return_to_unit_triangle so that it handles all
image orientations properly
sdf jan 26, 1987
last modifications 10-feb-88 sdf
Bug fix in print routine which gave wrong average errors for
N_IMAGES > 18
12-jan-1989 sdf
Implemented the origin shift refinement
30-jan-1989 sdf
Implemented the calculation of best handedness for whole
set of particles
7-feb-1989 sdf
include a variable MRC and a routine to allow use of
both TSB and MRC formats
26-june-89
Change average residual calculation so that, on output, the
top line of residuals is printed
Include hand calculation at each step of gradient refinement so
that the best hand is chosen at the beginning of each cycle
subroutine set_best_hand - this is controlled through
the logical ALLOW_FLIP - this is so far only in the
gradient refinement
sdf 26-june-89
Change the calculation of residuals in error matrix
(print_error_matrix) so that the top, bottom and best hand
choices are picked
sdf 27june-1989
Implemented the feild ACTIVE and changed the hand calculation
to allow flipping of only the ACTIVE images
sdf 28june-1989
Included the printing out of the changes in the orientations
as well as indications of flipping during refinement - subroutine
print_image_orientation_changes
sdf 29-june-1989
implement ability to input images with different magnifications
in the same simplex run - these are the variables SCALE and
ANG_PER_PIXEL This also allows the output to directly
calculate the resolution dependence of the residual in
physically meaningful units.
sdf 26-feb-90
loss of some components due to disk crash and reworking
installation of gradient version of tpoxy refinement so now all
angles can be refined this way
sdf 11-may-90
added FREE_RFACT
sdf 8apr93
added call to return_to_unit_triangle for initial orientations
sdf 13jul93
Author: Stephen Fuller
=======================>
Return to Top Virus Page