OffGridFit is a novel FFT-based exhaustive search method extended to off-grid translational and rotational degrees of freedom. The method combines the advantages of the FFT-based exhaustive search, which samples all the conformations on a grid, with a local optimization technique that guarantees to find the nearest optimal off-grid solution. We demonstrated the method when applied to cryo-EM fitting. However, it can be readily applied to a docking problem.

The algorithm first samples a scoring function on a six dimensional grid of size N6 using a Fast Fourier Transform (FFT). This operation has the asymptotic complexity of O(N6log N). Then, the the off-grid search is performed using a local quadratic approximation of the cost function and a trust region optimization algorithm. The computation of the quadratic approximation is also accelerates by FFT, when computed exhaustively at an additional cost of O(N6log N). Alternatively, we can compute it only for the top M rigid solutions at an additional cost of O(MN3).

We tested our method on fitting atomistic protein models into several synthetic and experimental Cryo-EM maps. Our results demonstrate that spatially proximate rigid poses converge to a single off-grid solution. Overall, the method gives descent results for both synthetic and experimental maps.  The method is applicable to any cost function that can be expressed as a convolution or correlation of two other functions defined on a 3D grid.


Alexandre Hoffmann and Sergei Grudinin,

CNRS, UMR 5075, IBS, Grenoble, France.

Université Grenoble Alpes – Grenoble 1, IBS, Grenoble, France.

NANO-D, INRIA Grenoble — Rhone-Alpes, 38334 Saint Ismier Cedex, Montbonnot, France.

PreviewLaboratoire Jean Kuntzmann, B.P. 53, 38041 Grenoble Cedex 9, France.

E-mail: Sergei.Grudinin @


Linux executables verified on Mageia, x86-64 architecture, multi-threaded and single-threaded versions.  A GUI module for the SAMSON modeling platform is in preparation.

MacOS: coming soon.


GroEL example (input PDB files + cryo-EM map).

A standard fitting example on artificial data with automatically chosen parameters:

./OffGridFit –iedm input/2c7c_H.mrc –ipdb input/2c7c_H.pdb –odir ./fit_2c7c_H-arti
./OffGridFit –iedm input/Groel.mrc –ipdb input/2c7c_H.pdb –nclusters 14 –odir ./fit_Groel-arti

A standard fitting example on real high resolution data with automatically chosen parameters:

./Flex-p-exhaust –iedm input/artificial/ –ipdb input/2c7c_H.pdb –nclusters 14 –nthread 1 –odir ./fit_Groel-real

The history of the command with all the parameters:

cat log.txt

A rapid coarse fitting:

./OffGridFit –iedm input/2c7c_H.mrc –ipdb input/2c7c_H.pdb –odir ./fit_2c7c_H-arti –dangle 100
./OffGridFit –iedm input/Groel.mrc –ipdb input/2c7c_H.pdb –nclusters 14 –odir ./fit_Groel-arti –dangle 100

Results can be visualised using PyMol:

pymol Rigid_solution.pdb Solution.pdb

To see all models in PyMol do:

Movie -> Show All States

To split the first 14 models in PyMol type (in the command prompt):

split_states Rigid_solution, 1,14
split_states Solution 1,14

Comments are closed.