About
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.
Authors
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 @ inria.fr
Download
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.
Examples
GroEL example (input PDB files + cryo-EM map).
A standard fitting example on artificial data with automatically chosen parameters:
./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:
The history of the command with all the parameters:
A rapid coarse fitting:
./OffGridFit –iedm input/Groel.mrc –ipdb input/2c7c_H.pdb –nclusters 14 –odir ./fit_Groel-arti –dangle 100
Results can be visualised using PyMol:
To see all models in PyMol do:
To split the first 14 models in PyMol type (in the command prompt):
split_states Solution 1,14
