A novel fast Fourier transform accelerated off-grid exhaustive search method for cryo-electron microscopy fitting

Alexandre Hoffmann 1 Valérie Perrier 2 Sergei Grudinin 1
1 NANO-D - Algorithms for Modeling and Simulation of Nanosystems
Inria Grenoble - Rhône-Alpes, LJK - Laboratoire Jean Kuntzmann, INPG - Institut National Polytechnique de Grenoble
2 CVGI - Calcul des Variations, Géométrie, Image
LJK - Laboratoire Jean Kuntzmann
Abstract : This paper presents a novel fast Fourier transform (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 of a system under study on a grid, with a local optimization technique that guarantees to find the nearest optimal off-grid conformation. The method is demonstrated on a fitting problem and can be readily applied to a docking problem. The algorithm first samples a scoring function on a six-dimensional grid of size N6 using the FFT. This operation has an asymptotic complexity of O(N6logN). Then, the method performs the off-grid search using a local quadratic approximation of the cost function and the trust-region optimization algorithm. The computation of the quadratic approximation is also accelerated by FFT at the same additional asymptotic cost of O(N6logN). The method is demonstrated by fitting atomic protein models into several simulated and experimental maps from cryo-electron microscopy. The method is available at https://team.inria.fr/nano-d/software/offgridfit.
Liste complète des métadonnées

Littérature citée [51 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01553293
Contributeur : Nano-D Equipe <>
Soumis le : mardi 1 août 2017 - 18:26:51
Dernière modification le : mercredi 11 avril 2018 - 01:58:50

Fichier

2017-Hoffmann-preprint-A novel...
Fichiers éditeurs autorisés sur une archive ouverte

Licence


Copyright (Tous droits réservés)

Identifiants

Citation

Alexandre Hoffmann, Valérie Perrier, Sergei Grudinin. A novel fast Fourier transform accelerated off-grid exhaustive search method for cryo-electron microscopy fitting. Journal of Applied Crystallography, International Union of Crystallography, 2017, 50 (4), pp.1036-1047. 〈10.1107/S1600576717008172〉. 〈hal-01553293〉

Partager

Métriques

Consultations de la notice

476

Téléchargements de fichiers

70