Viewing Direction Estimation in Cryo-EM Using Synchronization

A kinetic model for solving a combination optimization problem in ab-initio Cryo-EM 3D reconstruction

Cryo-Electron Microscopy (cryo-EM) is a widely used and effective method for determining the three-dimensional (3D) structure of biological molecules. For ab-initio Cryo-EM 3D reconstruction using single particle analysis (SPA), estimating the projection direction of the projection image is a crucial step. However, the existing SPA methods based on common lines are sensitive to noise. The error in common line detection will lead to a poor estimation of the projection directions and thus may greatly affect the final reconstruction results. To improve the reconstruction results, multiple candidate common lines are estimated for each pair of projection images. The key problem then becomes a combination optimization problem of selecting consistent common lines from multiple candidates. To solve the problem efficiently, a physics-inspired method based on a kinetic model is proposed in this work. More specifically, hypothetical attractive forces between each pair of candidate common lines are used to calculate a hypothetical torque exerted on each projection image in the 3D reconstruction space, and the rotation under the hypothetical torque is used to optimize the projection direction estimation of the projection image. This way, the consistent common lines along with the projection directions can be found directly without enumeration of all the combinations of the multiple candidate common lines. Compared with the traditional methods, the proposed method is shown to be able to produce more accurate 3D reconstruction results from high noise projection images. Besides the practical value, the proposed method also serves as a good reference for solving similar combinatorial optimization problems.

Efficient high-resolution refinement in cryo-EM with stochastic gradient descent

Electron cryomicroscopy (cryo-EM) is an imaging technique widely used in structural biology to determine the three-dimensional structure of biological molecules from noisy two-dimensional projections with unknown orientations. As the typical pipeline involves processing large amounts of data, efficient algorithms are crucial for fast and reliable results. The stochastic gradient descent (SGD) algorithm has been used to improve the speed of ab initio reconstruction, which results in a first, low-resolution estimation of the volume representing the molecule of interest, but has yet to be applied successfully in the high-resolution regime, where expectation-maximization algorithms achieve state-of-the-art results, at a high computational cost. In this article, we investigate the conditioning of the optimization problem and show that the large condition number prevents the successful application of gradient descent-based methods at high resolution. Our results include a theoretical analysis of the condition number of the optimization problem in a simplified setting where the individual projection directions are known, an algorithm based on computing a diagonal preconditioner using Hutchinson's diagonal estimator, and numerical experiments showing the improvement in the convergence speed when using the estimated preconditioner with SGD. The preconditioned SGD approach can potentially enable a simple and unified approach to ab initio reconstruction and high-resolution refinement with faster convergence speed and higher flexibility, and our results are a promising step in this direction.

Three-dimensional alignment of density maps in cryo-electron microscopy

A common task in cryo-electron microscopy data processing is to compare three-dimensional density maps of macromolecules. In this paper, we propose an algorithm for aligning three-dimensional density maps, which exploits common lines between projection images of the maps. The algorithm is fully automatic and handles rotations, reflections (handedness), and translations between the maps. In addition, the algorithm is applicable to any type of molecular symmetry without requiring any information regarding the symmetry of the maps. We evaluate our alignment algorithm on publicly available density maps, demonstrating its accuracy and efficiency. The algorithm is available at https://github.com/ShkolniskyLab/emalign.

Emerging Themes in CryoEM─Single Particle Analysis Image Processing

Cryo-electron microscopy (CryoEM) has become a vital technique in structural biology. It is an interdisciplinary field that takes advantage of advances in biochemistry, physics, and image processing, among other disciplines. Innovations in these three basic pillars have contributed to the boosting of CryoEM in the past decade. This work reviews the main contributions in image processing to the current reconstruction workflow of single particle analysis (SPA) by CryoEM. Our review emphasizes the time evolution of the algorithms across the different steps of the workflow differentiating between two groups of approaches: analytical methods and deep learning algorithms. We present an analysis of the current state of the art. Finally, we discuss the emerging problems and challenges still to be addressed in the evolution of CryoEM image processing methods in SPA.

3D reconstruction from cryo-EM projection images using two spherical embeddings

Single-particle analysis (SPA) in cryo-electron microscopy has become a powerful tool for determining and studying the macromolecular structure at an atomic level. However, since the SPA problem is a non-convex optimization problem with enormous search space and there is high level of noise in the input images, the existing methods may produce biased or even wrong final models. In this work, to deal with the problem, consistent constraints from the input data are explored in an embedding space, a 3D spherical surface. More specifically, the orientation of a projection image is represented by two intersection points of the normal vector and the local X-axis vector of the projection image on the unit spherical surface. To determine the orientations of the projection images, the global consistency constraints of the relative orientations of all the projection images are satisfied by two spherical embeddings which estimate the normal vectors and the local X-axis vectors of the projection images respectively. Compared to the traditional methods, the proposed method is shown to be able to rectify the initial computation errors and produce a more accurate estimation of the projection angles, which results in a better final model reconstruction from the noisy image data.

A 3D reconstruction method using two spherical embeddings to resolve projection angles of the cryo-EM images is shown to improve the initial model reconstruction for single-particle analysis.

A Fast Image Alignment Approach for 2D Classification of Cryo-EM Images Using Spectral Clustering

Three-dimensional (3D) reconstruction in single-particle cryo-electron microscopy (cryo-EM) is a significant technique for recovering the 3D structure of proteins or other biological macromolecules from their two-dimensional (2D) noisy projection images taken from unknown random directions. Class averaging in single-particle cryo-EM is an important procedure for producing high-quality initial 3D structures, where image alignment is a fundamental step. In this paper, an efficient image alignment algorithm using 2D interpolation in the frequency domain of images is proposed to improve the estimation accuracy of alignment parameters of rotation angles and translational shifts between the two projection images, which can obtain subpixel and subangle accuracy. The proposed algorithm firstly uses the Fourier transform of two projection images to calculate a discrete cross-correlation matrix and then performs the 2D interpolation around the maximum value in the cross-correlation matrix. The alignment parameters are directly determined according to the position of the maximum value in the cross-correlation matrix after interpolation. Furthermore, the proposed image alignment algorithm and a spectral clustering algorithm are used to compute class averages for single-particle 3D reconstruction. The proposed image alignment algorithm is firstly tested on a Lena image and two cryo-EM datasets. Results show that the proposed image alignment algorithm can estimate the alignment parameters accurately and efficiently. The proposed method is also used to reconstruct preliminary 3D structures from a simulated cryo-EM dataset and a real cryo-EM dataset and to compare them with RELION. Experimental results show that the proposed method can obtain more high-quality class averages than RELION and can obtain higher reconstruction resolution than RELION even without iteration.

Plankton reconstruction through robust statistical optical tomography

Plankton interact with the environment according to their size and three-dimensional (3D) structure. To study them outdoors, these translucent specimens are imaged in situ. Light projects through a specimen in each image. The specimen has a random scale, drawn from the population's size distribution and random unknown pose. The specimen appears only once before drifting away. We achieve 3D tomography using such a random ensemble to statistically estimate an average volumetric distribution of the plankton type and specimen size. To counter errors due to non-rigid deformations, we weight the data, drawing from advanced models developed for cryo-electron microscopy. The weights convey the confidence in the quality of each datum. This confidence relies on a statistical error model. We demonstrate the approach on live plankton using an underwater field microscope.

Robust high dimensional factor models with applications to statistical machine learning

Factor models are a class of powerful statistical models that have been widely used to deal with dependent measurements that arise frequently from various applications from genomics and neuroscience to economics and finance. As data are collected at an ever-growing scale, statistical machine learning faces some new challenges: high dimensionality, strong dependence among observed variables, heavy-tailed variables and heterogeneity. High-dimensional robust factor analysis serves as a powerful toolkit to conquer these challenges. This paper gives a selective overview on recent advance on high-dimensional factor models and their applications to statistics including Factor-Adjusted Robust Model selection (FarmSelect) and Factor-Adjusted Robust Multiple testing (FarmTest). We show that classical methods, especially principal component analysis (PCA), can be tailored to many new problems and provide powerful tools for statistical estimation and inference. We highlight PCA and its connections to matrix perturbation theory, robust statistics, random projection, false discovery rate, etc., and illustrate through several applications how insights from these fields yield solutions to modern challenges. We also present far-reaching connections between factor models and popular statistical learning problems, including network analysis and low-rank matrix recovery.

The structure of a triple complex of plant photosystem I with ferredoxin and plastocyanin

The ability of photosynthetic organisms to use sunlight as a sole source of energy is endowed by two large membrane complexes-photosystem I (PSI) and photosystem II (PSII). PSI and PSII are the fundamental components of oxygenic photosynthesis, providing oxygen, food and an energy source for most living organisms on Earth. Currently, high-resolution crystal structures of these complexes from various organisms are available. The crystal structures of megadalton complexes have revealed excitation transfer and electron-transport pathways within the various complexes. PSI is defined as plastocyanin-ferredoxin oxidoreductase but a high-resolution structure of the entire triple supercomplex is not available. Here, using a new cryo-electron microscopy technique, we solve the structure of native plant PSI in complex with its electron donor plastocyanin and the electron acceptor ferredoxin. We reveal all of the contact sites and the modes of interaction between the interacting electron carriers and PSI.

The structure of a triple complex of plant photosystem I with ferredoxin and plastocyanin

The ability of photosynthetic organisms to use sunlight as a sole source of energy is endowed by two large membrane complexes-photosystem I (PSI) and photosystem II (PSII). PSI and PSII are the fundamental components of oxygenic photosynthesis, providing oxygen, food and an energy source for most living organisms on Earth. Currently, high-resolution crystal structures of these complexes from various organisms are available. The crystal structures of megadalton complexes have revealed excitation transfer and electron-transport pathways within the various complexes. PSI is defined as plastocyanin-ferredoxin oxidoreductase but a high-resolution structure of the entire triple supercomplex is not available. Here, using a new cryo-electron microscopy technique, we solve the structure of native plant PSI in complex with its electron donor plastocyanin and the electron acceptor ferredoxin. We reveal all of the contact sites and the modes of interaction between the interacting electron carriers and PSI.

Validation of electron microscopy initial models via small angle X-ray scattering curves

MOTIVATION

Cryo electron microscopy (EM) is currently one of the main tools to reveal the structural information of biological macromolecules. The re-construction of three-dimensional (3D) maps is typically carried out following an iterative process that requires an initial estimation of the 3D map to be refined in subsequent steps. Therefore, its determination is key in the quality of the final results, and there are cases in which it is still an open issue in single particle analysis (SPA). Small angle X-ray scattering (SAXS) is a well-known technique applied to structural biology. It is useful from small nanostructures up to macromolecular ensembles for its ability to obtain low resolution information of the biological sample measuring its X-ray scattering curve. These curves, together with further analysis, are able to yield information on the sizes, shapes and structures of the analyzed particles.

RESULTS

In this paper, we show how the low resolution structural information revealed by SAXS is very useful for the validation of EM initial 3D models in SPA, helping the following refinement process to obtain more accurate 3D structures. For this purpose, we approximate the initial map by pseudo-atoms and predict the SAXS curve expected for this pseudo-atomic structure. The match between the predicted and experimental SAXS curves is considered as a good sign of the correctness of the EM initial map.

AVAILABILITY AND IMPLEMENTATION

The algorithm is freely available as part of the Scipion 1.2 software at http://scipion.i2pc.es/.

ENTRYWISE EIGENVECTOR ANALYSIS OF RANDOM MATRICES WITH LOW EXPECTED RANK

Recovering low-rank structures via eigenvector perturbation analysis is a common problem in statistical machine learning, such as in factor analysis, community detection, ranking, matrix completion, among others. While a large variety of bounds are available for average errors between empirical and population statistics of eigenvectors, few results are tight for entrywise analyses, which are critical for a number of problems such as community detection. This paper investigates entrywise behaviors of eigenvectors for a large class of random matrices whose expectations are low-rank, which helps settle the conjecture in Abbe et al. (2014b) that the spectral algorithm achieves exact recovery in the stochastic block model without any trimming or cleaning steps. The key is a first-order approximation of eigenvectors under the ℓ ∞ norm:u k ≈ A u k * λ k * , where {u k } and{ u k * } are eigenvectors of a random matrix A and its expectation E A , respectively. The fact that the approximation is both tight and linear in A facilitates sharp comparisons between u k andu k * . In particular, it allows for comparing the signs of u k andu k * even if‖ u k - u k * ‖ ∞ is large. The results are further extended to perturbations of eigenspaces, yielding new ℓ ∞-type bounds for synchronization (ℤ 2 -spiked Wigner model) and noisy matrix completion.

NON-UNIQUE GAMES OVER COMPACT GROUPS AND ORIENTATION ESTIMATION IN CRYO-EM

Let 𝒢 be a compact group and let f i j ∈ C ( 𝒢 ) . We define the Non-Unique Games (NUG) problem as finding g 1 , … , g n ∈ 𝒢 to minimize ∑ i , j = 1 n f i j g i g j - 1 . We introduce a convex relaxation of the NUG problem to a semidefinite program (SDP) by taking the Fourier transform of f i j over 𝒢 . The NUG framework can be seen as a generalization of the little Grothendieck problem over the orthogonal group and the Unique Games problem and includes many practically relevant problems, such as the maximum likelihood estimator to registering bandlimited functions over the unit sphere in d -dimensions and orientation estimation of noisy cryo-Electron Microscopy (cryo-EM) projection images. We implement a SDP solver for the NUG cryo-EM problem using the alternating direction method of multipliers (ADMM). Numerical study with synthetic datasets indicate that while our ADMM solver is slower than existing methods, it can estimate the rotations more accurately, especially at low signal-to-noise ratio (SNR).

Hyper-Molecules: on the Representation and Recovery of Dynamical Structures for Applications in Flexible Macro-Molecules in Cryo-EM

Cryo-electron microscopy (cryo-EM), the subject of the 2017 Nobel Prize in Chemistry, is a technology for obtaining 3-D reconstructions of macromolecules from many noisy 2-D projections of instances of these macromolecules, whose orientations and positions are unknown. These molecules are not rigid objects, but flexible objects involved in dynamical processes. The different conformations are exhibited by different instances of the macromolecule observed in a cryo-EM experiment, each of which is recorded as a particle image. The range of conformations and the conformation of each particle are not known a priori; one of the great promises of cryo-EM is to map this conformation space. Remarkable progress has been made in reconstructing rigid molecules based on homogeneous samples of molecules in spite of the unknown orientation of each particle image and significant progress has been made in recovering a few distinct states from mixtures of rather distinct conformations, but more complex heterogeneous samples remain a major challenge. We introduce the "hyper-molecule" theoretical framework for modeling structures across different states of heterogeneous molecules, including continuums of states. The key idea behind this framework is representing heterogeneous macromolecules as high-dimensional objects, with the additional dimensions representing the conformation space. This idea is then refined to model properties such as localized heterogeneity. In addition, we introduce an algorithmic framework for reconstructing such heterogeneous objects from experimental data using a Bayesian formulation of the problem and Markov chain Monte Carlo (MCMC) algorithms to address the computational challenges in recovering these high dimensional hyper-molecules. We demonstrate these ideas in a preliminary prototype implementation, applied to synthetic data.

Regularization with Metric Double Integrals of Functions with Values in a Set of Vectors

We present an approach for variational regularization of inverse and imaging problems for recovering functions with values in a set of vectors. We introduce regularization functionals, which are derivative-free double integrals of such functions. These regularization functionals are motivated from double integrals, which approximate Sobolev semi-norms of intensity functions. These were introduced in Bourgain et al. (Another look at Sobolev spaces. In: Menaldi, Rofman, Sulem (eds) Optimal control and partial differential equations-innovations and applications: in honor of professor Alain Bensoussan's 60th anniversary, IOS Press, Amsterdam, pp 439-455, 2001). For the proposed regularization functionals, we prove existence of minimizers as well as a stability and convergence result for functions with values in a set of vectors.

Advances in image processing for single-particle analysis by electron cryomicroscopy and challenges ahead

Electron cryomicroscopy (cryoEM) is essential for the study and functional understanding of non-crystalline macromolecules such as proteins. These molecules cannot be imaged using X-ray crystallography or other popular methods. CryoEM has been successfully used to visualize macromolecular complexes such as ribosomes, viruses, and ion channels. Determination of structural models of these at various conformational states leads to insight on how these molecules function. Recent advances in imaging technology have given cryoEM a scientific rebirth. As a result of these technological advances image processing and analysis have yielded molecular structures at atomic resolution. Nevertheless there continue to be challenges in image processing, and in this article we will touch on the most essential in order to derive an accurate three-dimensional model from noisy projection images. Traditional approaches, such as k-means clustering for class averaging, will be provided as background. We will then highlight new approaches for each image processing subproblem, including a 3D reconstruction method for asymmetric molecules using just two projection images and deep learning algorithms for automated particle picking.

Structural Variability from Noisy Tomographic Projections

In cryo-electron microscopy, the three-dimensional (3D) electric potentials of an ensemble of molecules are projected along arbitrary viewing directions to yield noisy two-dimensional images. The volume maps representing these potentials typically exhibit a great deal of structural variability, which is described by their 3D covariance matrix. Typically, this covariance matrix is approximately low rank and can be used to cluster the volumes or estimate the intrinsic geometry of the conformation space. We formulate the estimation of this covariance matrix as a linear inverse problem, yielding a consistent least-squares estimator. For n images of size N-by-N pixels, we propose an algorithm for calculating this covariance estimator with computational complexity O ( n N 4 + κ N 6 log N ) , where the condition number κ is empirically in the range 10-200. Its efficiency relies on the observation that the normal equations are equivalent to a deconvolution problem in six dimensions. This is then solved by the conjugate gradient method with an appropriate circulant preconditioner. The result is the first computationally efficient algorithm for consistent estimation of the 3D covariance from noisy projections. It also compares favorably in runtime with respect to previously proposed nonconsistent estimators. Motivated by the recent success of eigenvalue shrinkage procedures for high-dimensional covariance matrix estimation, we incorporate a shrinkage procedure that improves accuracy at lower signal-to-noise ratios. We evaluate our methods on simulated datasets and achieve classification results comparable to state-of-the-art methods in shorter running time. We also present results on clustering volumes in an experimental dataset, illustrating the power of the proposed algorithm for practical determination of structural variability.

Bispectrum Inversion with Application to Multireference Alignment

We consider the problem of estimating a signal from noisy circularly-translated versions of itself, called multireference alignment (MRA). One natural approach to MRA could be to estimate the shifts of the observations first, and infer the signal by aligning and averaging the data. In contrast, we consider a method based on estimating the signal directly, using features of the signal that are invariant under translations. Specifically, we estimate the power spectrum and the bispectrum of the signal from the observations. Under mild assumptions, these invariant features contain enough information to infer the signal. In particular, the bispectrum can be used to estimate the Fourier phases. To this end, we propose and analyze a few algorithms. Our main methods consist of non-convex optimization over the smooth manifold of phases. Empirically, in the absence of noise, these non-convex algorithms appear to converge to the target signal with random initialization. The algorithms are also robust to noise. We then suggest three additional methods. These methods are based on frequency marching, semidefinite relaxation and integer programming. The first two methods provably recover the phases exactly in the absence of noise. In the high noise level regime, the invariant features approach for MRA results in stable estimation if the number of measurements scales like the cube of the noise variance, which is the information-theoretic rate. Additionally, it requires only one pass over the data which is important at low signal-to-noise ratio when the number of observations must be large.

Common lines modeling for reference free Ab-initio reconstruction in cryo-EM

We consider the problem of estimating an unbiased and reference-free ab initio model for non-symmetric molecules from images generated by single-particle cryo-electron microscopy. The proposed algorithm finds the globally optimal assignment of orientations that simultaneously respects all common lines between all images. The contribution of each common line to the estimated orientations is weighted according to a statistical model for common lines' detection errors. The key property of the proposed algorithm is that it finds the global optimum for the orientations given the common lines. In particular, any local optima in the common lines energy landscape do not affect the proposed algorithm. As a result, it is applicable to thousands of images at once, very robust to noise, completely reference free, and not biased towards any initial model. A byproduct of the algorithm is a set of measures that allow to asses the reliability of the obtained ab initio model. We demonstrate the algorithm using class averages from two experimental data sets, resulting in ab initio models with resolutions of 20Å or better, even from class averages consisting of as few as three raw images per class.

Cross-Validation of Data Compatibility Between Small Angle X-ray Scattering and Cryo-Electron Microscopy

Cryo-electron microscopy (EM) and small angle X-ray scattering (SAXS) are two different data acquisition modalities often used to glean information about the structure of large biomolecular complexes in their native states. A SAXS experiment is generally considered fast and easy but unveils the structure at very low resolution, whereas a cryo-EM experiment needs more extensive preparation and postacquisition computation to yield a three-dimensional (3D) density map at higher resolution. In certain applications, we may need to verify whether the data acquired in the SAXS and cryo-EM experiments correspond to the same structure (e.g., before reconstructing the 3D density map in EM). In this article, a simple and fast method is proposed to verify the compatibility of the SAXS and EM experimental data. The method is based on averaging the two-dimensional correlation of EM images and the Abel transform of the SAXS data. Orientational preferences are known to exist in cryo-EM experiments, and we also consider these effects on our method. The results are verified on simulations of conformational states of large biomolecular complexes.

A Graph Partitioning Approach to Simultaneous Angular Reconstitution

One of the primary challenges in single particle reconstruction with cryo-electron microscopy is to find a three-dimensional model of a molecule using its noisy two-dimensional projection-images. As the imaging orientations of the projection-images are unknown, we suggest a common-lines-based method to simultaneously estimate the imaging orientations of all images that is independent of the distribution of the orientations. Since the relative orientation of each pair of images may only be estimated up to a two-way handedness ambiguity, we suggest an efficient procedure to consistently assign the same handedness to all relative orientations. This is achieved by casting the handedness assignment problem as a graph-partitioning problem. Once a consistent handedness of all relative orientations is determined, the orientations corresponding to all projection-images are determined simultaneously, thus rendering the method robust to noise. Our proposed method has also the advantage of allowing one to incorporate confidence information regarding the trustworthiness of each relative orientation in a natural manner. We demonstrate the efficacy of our approach using simulated clean and noisy data.

Orientation Determination of Cryo-EM Images Using Least Unsquared Deviations

A major challenge in single particle reconstruction from cryo-electron microscopy is to establish a reliable ab initio three-dimensional model using two-dimensional projection images with unknown orientations. Common-lines-based methods estimate the orientations without additional geometric information. However, such methods fail when the detection rate of common-lines is too low due to the high level of noise in the images. An approximation to the least squares global self-consistency error was obtained in [A. Singer and Y. Shkolnisky, SIAM J. Imaging Sci., 4 (2011), pp. 543-572] using convex relaxation by semidefinite programming. In this paper we introduce a more robust global self-consistency error and show that the corresponding optimization problem can be solved via semidefinite relaxation. In order to prevent artificial clustering of the estimated viewing directions, we further introduce a spectral norm term that is added as a constraint or as a regularization term to the relaxed minimization problem. The resulting problems are solved using either the alternating direction method of multipliers or an iteratively reweighted least squares procedure. Numerical experiments with both simulated and real images demonstrate that the proposed methods significantly reduce the orientation estimation error when the detection rate of common-lines is low.