A simulated annealing approach for resolution guided homogeneous cryo-electron microscopy image selection

Abstract

Background: Cryo-electron microscopy (Cryo-EM) and tomography (Cryo-ET) have emerged as important imaging techniques for studying structures of macromolecular complexes. In 3D reconstruction of large macromolecular complexes, many 2D projection images of macromolecular complex particles are usually acquired with low signal-to-noise ratio. Therefore, it is meaningful to select multiple images containing the same structure with identical orientation. The selected images are averaged to produce a higher-quality representation of the underlying structure with improved resolution. Existing approaches of selecting such images have limited accuracy and speed.

Methods: We propose a simulated annealing-based algorithm (SA) to pick the homogeneous image set with best average. Its performance is compared with two baseline methods based on both 2D and 3D datasets. When tested on simulated and experimental 3D Cryo-ET images of Ribosome complex, SA sometimes stopped at a local optimal solution. Restarting is applied to settle this difficulty and significantly improved the performance of SA on 3D datasets.

Results: Experimented on simulated and experimental 2D Cryo-EM images of Ribosome complex datasets respectively with SNR=10 and SNR=0.5, our method achieved better accuracy in terms of F-measure, resolution score, and time cost than two baseline methods. Additionally, SA shows its superiority when the proportion of homogeneous images decreases.

Conclusions: SA is introduced for homogeneous image selection to realize higher accuracy with faster processing speed. Experiments on both simulated and real 2D Cryo-EM and 3D Cryo-ET images demonstrated that SA achieved expressively better performance. This approach serves as an important step for improving the resolution of structural recovery of macromolecular complexes captured by Cryo-EM and Cryo-ET.

Graphical abstract

Keywords

simulated annealing / image averaging / cryo-electron microscopy / cryo-electron tomography

References

[1] Frank, J. (2006) Three-dimensional Electron Microscopy of Macromolecular Assemblies. New York: Oxford University Press

[2] Lučić V., Rigort, A. and Baumeister, W. (2013) Cryo-electron tomography: the challenge of doing structural biology in situ. J. Cell Biol., 202, 407–419

[3] Sali, A., Glaeser, R., Earnest, T. and Baumeister, W. (2003) From words to literature in structural proteomics. Nature, 422, 216–225

[4] Liao, H. Y. and Frank, J. (2010) Definition and estimation of resolution in single-particle reconstructions. Structure, 18, 768–775

[5] Van Laarhoven, P. J. M. and Aarts, E. H. L. (1987) Simulated annealing. In: Simulated annealing: Theory and Applications, pp. 7–15. New York: Springer

[6] Xu, M., Tocheva, E.I., Chang, Y.-W.Jensen, G.J. and Alber, F. (2015) De novo visual proteomics in single cells through pattern mining. Structure, 27, 679–691.e14

[7] Xu, M., Beck, M. and Alber, F. (2012) High-throughput subtomogram alignment and classification by Fourier space constrained fast volumetric matching. J. Struct. Biol., 178, 152–164

[8] Powers D. M., (2011) Evaluation: from precision, recall and F-measure to roc, informedness, markedness and correlation. J. Mach. Learn. Tech. 2, 37–63

[9] Snyder, D. L., O’Sullivan, J. A., Murphy, R. J., Politte, D. G., Whiting, B. R. and Williamson, J. F. (2006) Image reconstruction for transmission tomography when projection data are incomplete. Phys. Med. Biol., 51, 5603–5619

[10] Wong, W., Bai, X., Brown, A., Fernandez, I.S., Hanssen, E., Condron, M., Tan, Y.H., Baum, J. and Scheres. S. (2014) Cryo-em structure of the Plasmodium falciparum 80s ribosome bound to the anti-protozoan drug emetine. eLife, 3, e03080

[11] Zhao, Y., Zeng, X., Guo, Q. and Xu, M. (2018) An integration of fast alignment and maximum-likelihood methods for electron subtomogram averaging and classification. Bioinformatics, 34, i227–i236

[12] Holland, J. (2012) Genetic algorithms. Scholarpedia, 7, 1482

[13] Yang, Z., Fang, J., Chittuluru, J., Asturias, F. J. and Penczek, P. A. (2012) Iterative stable alignment and clustering of 2D transmission electron microscope images. Structure, 20, 237–247

[14] Frank, J. (2009) Single-particle reconstruction of biological macromolecules in electron microscopy—30 years. Q. Rev. Biophys., 42, 139–158

[15] Tang, G., Peng, L., Baldwin, P. R., Mann, D. S., Jiang, W., Rees, I. and Ludtke, S. J. (2007) EMAN2: an extensible image processing suite for electron microscopy. J. Struct. Biol., 157, 38–46

[16] Scheres, S. H. (2012) RELION: implementation of a Bayesian approach to cryo-EM structure determination. J. Struct. Biol., 180, 519–530

[17] Elad, N., Clare, D. K., Saibil, H. R. and Orlova, E. V. (2008) Detection and separation of heterogeneity in molecular complexes by statistical analysis of their two-dimensional projections. J. Struct. Biol., 162, 108–120

[18] Sorzano, C. O. S., Bilbao-Castro, J. R., Shkolnisky, Y., Alcorlo, M., Melero, R., Caffarena-Fernández, G., Li, M., Xu, G., Marabini, R. and Carazo, J. M. (2010) A clustering approach to multireference alignment of single-particle projections in electron microscopy. J. Struct. Biol., 171, 197–206

[19] Heymann, J. B., Conway, J. F. and Steven, A. C. (2004) Molecular dynamics of protein complexes from four-dimensional cryo-electron microscopy. J. Struct. Biol., 147, 291–301

[20] Dubochet, J., Adrian, M., Chang, J. J., Homo, J. C., Lepault, J., Mcdowall, A. W. and Schultz, P. (1987) Cryoelectron microscopy of vitrified specimens. Springer Berlin Heidelberg

[21] Oikonomou, C. M., Chang, Y.-W. and Jensen, G. J.. (2016) A new view into prokaryotic cell biology from electron cryotomography. Nat. Rev. Microbiol., 14, 205–220

[22] Szeliski. R., (2007) Image alignment and stitching: A tutorial. In: Foundations Trends R in Computer Graphics Vision, 2, 1–104

[23] Lim, A., Rodrigues, B. and Zhang, X. (2007) A simulated annealing and hill-climbing algorithm for the traveling tournament problem. Eur. J. Oper. Res., 174, 1459–1478

[24] Hall, R. J. and Patwardhan, A. (2004) A two step approach for semi-automated particle selection from low contrast cryo-electron micrographs. J. Struct. Biol., 145, 19–28

[25] Mallick, S.P., Zhu, Y. and Kriegman, D. (2004) Detecting particles in cryo-em micrographs using learned features. J. Struct. Biol., 145, 52–62

[26] Sigworth, F. J. (2004) Classical detection theory and the cryo-EM particle selection problem. J. Struct. Biol., 145, 111–122

[27] Ouyang, J., Liang, Z., Chen, C., Fu, Z., Zhang, Y. and Liu, H. (2018) Cryo-electron microscope image denoising based on the geodesic distance. BMC Struct. Biol., 18, 18

[28] Sorzano, C. O. S., Recarte, E., Alcorlo, M., Bilbao-Castro, J. R., San-Martín, C., Marabini, R. and Carazo, J. M. (2009) Automatic particle selection from electron micrographs using machine learning techniques. J. Struct. Biol., 167, 252–260

[29] Larose, D. T. (2006) Data Mining: Methods and Models. Hoboken: Wiley

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag GmbH Germany, part of Springer Nature