gEMpicker: a highly parallel GPU-accelerated particle picking tool for cryo-electron microscopy

BMC Structural Biology

David W Ritchie¹  Patrick Schultz²  Xavier Cavin¹  Thai V Hoang¹ 

[1] Inria Nancy - Grand Est, 615 rue du Jardin Botanique, 54600 Villers-lès-Nancy, France;IGBMC, 1 rue Laurent Fries, 67404 Illkirch, France

关键词: Tree-based reduction;    Parallel computing;    Fast Fourier transform;    Normalised cross-correlation;    Graphics processor units;    Cryo-EM particle picking;   

Others  :  1090991
DOI  :  10.1186/1472-6807-13-25

 received in 2013-06-13, accepted in 2013-10-14,  发布年份 2013

【 摘 要 】

Background

Picking images of particles in cryo-electron micrographs is an important step in solving the 3D structures of large macromolecular assemblies. However, in order to achieve sub-nanometre resolution it is often necessary to capture and process many thousands or even several millions of 2D particle images. Thus, a computational bottleneck in reaching high resolution is the accurate and automatic picking of particles from raw cryo-electron micrographs.

Results

We have developed “gEMpicker”, a highly parallel correlation-based particle picking tool. To our knowledge, gEMpicker is the first particle picking program to use multiple graphics processor units (GPUs) to accelerate the calculation. When tested on the publicly available keyhole limpet hemocyanin dataset, we find that gEMpicker gives similar results to the FindEM program. However, compared to calculating correlations on one core of a contemporary central processor unit (CPU), running gEMpicker on a modern GPU gives a speed-up of about 27 ×. To achieve even higher processing speeds, the basic correlation calculations are accelerated considerably by using a hierarchy of parallel programming techniques to distribute the calculation over multiple GPUs and CPU cores attached to multiple nodes of a computer cluster. By using a theoretically optimal reduction algorithm to collect and combine the cluster calculation results, the speed of the overall calculation scales almost linearly with the number of cluster nodes available.

Conclusions

The very high picking throughput that is now possible using GPU-powered workstations or computer clusters will help experimentalists to achieve higher resolution 3D reconstructions more rapidly than before.

【 授权许可】

   
2013 Hoang et al.; licensee BioMed Central Ltd.

【 图 表 】

Figure 1.

Figure 2.

Figure 3.

Figure 4.

Figure 5.

Figure 6.

Figure 7.

Figure 8.

【 参考文献 】

• [1]Orlova EV, Saibil HR: Structural analysis of macromolecular assemblies by electron microscopy. Chem Rev 2011, 111(12):7710-7748.
• [2]Lanzavecchia S, Bellon PL, Radermacher M: Fast and accurate three-dimensional reconstruction from projections with random orientations via Radon transforms. J Struct Biol 1999, 128(2):152-164.
• [3]Nicholson WV, Glaeser RM: Review: automatic particle detection in electron microscopy. J Struct Biol 2001, 133(2–3):90-101.
• [4]Zhu Y, Carragher B, Glaeser RM, Fellmann D, Bajaj C, Bern M, Mouche F, de Haas F, Hall RJ, Kriegman DJ, Ludtke SJ, Mallick SP, Penczek PA, Roseman AM, Sigworth FJ, Volkmann N, Potter CS: Automatic particle selection: results of a comparative study. J Struct Biol 2004, 145(1–2):3-14.
• [5]Voss NR, Yoshioka CK, Radermacher M, Potter CS, Carragher B: DoG Picker and TiltPicker: software tools to facilitate particle selection in single particle electron microscopy. J Struct Biol 2009, 166(2):205-213.
• [6]Langlois R, Pallesen J, Frank J: Reference-free particle selection enhanced with semi-supervised machine learning for cryo-electron microscopy. J Struct Biol 2011, 175(3):353-361.
• [7]Roseman AM: Particle finding in electron micrographs using a fast local correlation algorithm. Ultramicroscopy 2003, 94(3–4):225-236.
• [8]Roseman AM: FindEM – A fast, efficient program for automatic selection of particles from electron micrographs. J Struct Biol 2004, 145(1–2):91-99.
• [9]Rath BK, Frank J: Fast automatic particle picking from cryo-electron micrographs using a locally normalized cross-correlation function: a case study. J Struct Biol 2004, 145(1–2):84-90.
• [10]Chen JZ, Grigorieff N: SIGNATURE: A single-particle selection system for molecular electron microscopy. J Struct Biol 2007, 157:168-173.
• [11]Mallick SP, Zhu Y, Kriegman D: Detecting particles in cryo-EM micrographs using learned features. J Struct Biol 2004, 145(1–2):52-62.
• [12]Sorzano C, Recarte E, Alcorlo M, Bilbao-Castro J, San-Martín C, Marabini R, Carazo J: Automatic particle selection from electron micrographs using machine learning techniques. J Struct Biol 2009, 167(3):252-260.
• [13]Ogura T, Sato C: Automatic particle pickup method using a neural network has high accuracy by applying an initial weight derived from eigenimages: a new reference free method for single-particle analysis. J Struct Biol 2004, 145(1–2):63-75.
• [14]Arbeláez P, Han BG, Typke D, Lim J, Glaeser RM, Malik J: Experimental evaluation of support vector machine-based and correlation-based approaches to automatic particle selection. J Struct Biol 2011, 175(3):319-328.
• [15]Zhu Y, Carragher B, Mouche F, Potter CS: Automatic particle detection through efficient Hough transforms. IEEE Trans Med Imaging 2003, 22(9):1053-1062.
• [16]Adiga U, Baxter WT, Hall RJ, Rockel B, Rath BK, Frank J, Glaeser R: Particle picking by segmentation: A comparative study with SPIDER-based manual particle picking. J Struct Biol 2005, 152(3):211-220.
• [17]Owens JD, Luebke D, Govindaraju N, Harris M, Krüger J, Lefohn AE, Purcell TJ: A survey of general-purpose computation on graphics hardware. Comput Graph Forum 2007, 26:80-113.
• [18]Stone JE, Phillips JC, Freddolino PL, Hardy DJ, Trabuco LG, Schulten K: Accelerating molecular modeling applications with graphics processors. J Comput Chem 2007, 28:2618-2640.
• [19]Ufimtsev IS, Martínez TJ: Quantum chemistry on graphical processor units. 1. Strategies for two-electron integral evaluation. J Chem Theory Comput 2008, 4:222-231.
• [20]Manavski SA, Valle G: CUDA-compatible GPU cards as efficient hardware accelerators for Smith-Waterman sequence alignment. BMC Bioinformatics 2008, 9(2):S10.
• [21]Ritchie DW, Venkatraman V: Ultra-fast FFT protein docking on graphics processors. Bioinformatics 2010, 26(19):2398-2405.
• [22]Li X, Grigorieff N, Cheng Y: GPU-enabled FREALIGN: Accelerating single particle 3D reconstruction and refinement in Fourier space on graphics processors. J Struct Biol 2010, 172(3):407-412.
• [23]Zheng SQ, Branlund E, Kesthelyi B, Braunfeld MB, Cheng Y, Sedat JW, Agard DA: A distributed multi-GPU system for high speed electron microscopic tomographic reconstruction. Ultramicroscopy 2011, 111(8):1137-1143.
• [24]Castaño-Díez D, Kudryashev M, Arheit M, Stahlberg H: Dynamo: A flexible, user-friendly development tool for subtomogram averaging of cryo-EM data in high-performance computing environments. J Struct Biol 2012, 178(2):139-151.
• [25]Intel Corporation: The Intel Math Kernel Library. 2012. [http://software.intel.com/en-us/intel-mkl/ webcite]
• [26]Nvidia Corporation: The Nvidia CUDA Fast Fourier Transform library (CUFFT). 2012. [http://developer.nvidia.com/cuda/cufft/ webcite]
• [27]Frigo M, Johnson S: The design and implementation of FFTW3. Proc IEEE 2005, 93(2):216-231. [http://www.fftw.org/ webcite]
• [28]Cooley JW, Tukey JW: An algorithm for the machine calculation of complex Fourier series. Math Comput 1965, 19:297-301.
• [29]Rader CM: Discrete Fourier transforms when the number of data samples is prime. Proc IEEE 1968, 56(6):1107-1108.
• [30]Bluestein LI: A linear filtering approach to the computation of discrete Fourier transform. IEEE Trans Audio Electroacoustics 1970, 18(4):451-455.
• [31]Nvidia Corporation: The CUDA C Programming Guide. 2012. [http://docs.nvidia.com/cuda/index.html webcite]
• [32]Eckel B: Thinking in C++: Practical Programming, 2nd edition. Upper Saddle River, New Jersey 07458, USA: Prentice Hall; 2000.
• [33]Garg RP, Sharapov IA: Techniques for Optimizing Applications: High Performance Computing. Upper Saddle River, New Jersey, 07458, USA: Prentice Hall; 2001.
• [34]Schäling B: The Boost C++ Libraries. Suite O-175 Laguna Hills, CA 92637, USA: XML Press; 2011. [http://www.boost.org/ webcite]
• [35]Gropp W, Lusk E, Skjellum A: Using MPI: Portable Parallel Programming with the Message Passing Interface, 2nd edition. Cambridge, MA 02142-1493, USA: The MIT Press; 1999.
• [36]Chapman B, Jost G, van der Pas R: Using OpenMP: Portable Shared Memory Parallel Programming. Cambridge, MA 02142-1493, USA: The MIT Press; 2007.
• [37]Orlova EV, Dube P, Harris J, Beckman E, Zemlin F, Markl J, van Heel M: Structure of keyhole limpet hemocyanin type 1 (KLH1) at 15 Å resolution by electron cryomicroscopy and angular reconstitution. J Mol Biol 1997, 271(3):417-437.
• [38]Tang G, Peng L, Baldwin PR, Mann DS, Jiang W, Rees I, Ludtke SJ: EMAN2: An extensible image processing suite for electron microscopy. J Struct Biol 2007, 157:38-46.