Gridding-based direct Fourier inversion of the three-dimensional ray transform

Unified fast reconstruction algorithm for conventional, phase-contrast, and diffraction tomography

A unified method for three-dimensional reconstruction of objects from transmission images collected at multiple illumination directions is described. The method may be applicable to experimental conditions relevant to absorption-based, phase-contrast, or diffraction imaging using x rays, electrons, and other forms of penetrating radiation or matter waves. Both the phase retrieval (also known as contrast transfer function correction) and the effect of Ewald sphere curvature (in the cases with a shallow depth of field and significant in-object diffraction) are incorporated in the proposed algorithm and can be taken into account. Multiple scattering is not treated explicitly but can be mitigated as a result of angular averaging that constitutes an essential feature of the method. The corresponding numerical algorithm is based on three-dimensional gridding which allows for fast computational implementation, including a straightforward parallelization. The algorithm can be used with any scanning geometry involving plane-wave illumination. A software code implementing the proposed algorithm has been developed, tested on simulated and experimental image data, and made publicly available.

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.

On bias, variance, overfitting, gold standard and consensus in single-particle analysis by cryo-electron microscopy

Cryo-electron microscopy (cryoEM) has become a well established technique to elucidate the 3D structures of biological macromolecules. Projection images from thousands of macromolecules that are assumed to be structurally identical are combined into a single 3D map representing the Coulomb potential of the macromolecule under study. This article discusses possible caveats along the image-processing path and how to avoid them to obtain a reliable 3D structure. Some of these problems are very well known in the community. These may be referred to as sample-related (such as specimen denaturation at interfaces or non-uniform projection geometry leading to underrepresented projection directions). The rest are related to the algorithms used. While some have been discussed in depth in the literature, such as the use of an incorrect initial volume, others have received much less attention. However, they are fundamental in any data-analysis approach. Chiefly among them, instabilities in estimating many of the key parameters that are required for a correct 3D reconstruction that occur all along the processing workflow are referred to, which may significantly affect the reliability of the whole process. In the field, the term overfitting has been coined to refer to some particular kinds of artifacts. It is argued that overfitting is a statistical bias in key parameter-estimation steps in the 3D reconstruction process, including intrinsic algorithmic bias. It is also shown that common tools (Fourier shell correlation) and strategies (gold standard) that are normally used to detect or prevent overfitting do not fully protect against it. Alternatively, it is proposed that detecting the bias that leads to overfitting is much easier when addressed at the level of parameter estimation, rather than detecting it once the particle images have been combined into a 3D map. Comparing the results from multiple algorithms (or at least, independent executions of the same algorithm) can detect parameter bias. These multiple executions could then be averaged to give a lower variance estimate of the underlying parameters.

NUDIM: A non-uniform fast Fourier transform based dual-space constraint iterative reconstruction method in biological electron tomography

Electron tomography, a powerful imaging tool for studying 3D structures of macromolecular assemblies, always suffers from imperfect reconstruction with limited resolution due to the intrinsic low signal-to-noise ratio (SNR) and inaccessibility to certain tilt angles induced by radiation damage or mechanical limitation. In order to compensate for such insufficient data with low SNR and further improve imaging resolution, prior knowledge constraints about the objects in both real space and reciprocal space are thus exploited during tomographic reconstruction. However, direct Fast Fourier transform (FFT) between real space and reciprocal space remains extraordinarily challenging owing to their inconsistent grid sampling modes, e.g. regular and uniform grid sampling in real space whereas radial or polar grid sampling in reciprocal space. In order to solve such problem, a technique of non-uniform fast Fourier transform (NFFT) has been developed to transform efficiently between non-uniformly sampled grids in real and reciprocal space with sufficient accuracy. In this work, a Non-Uniform fast Fourier transform based Dual-space constraint Iterative reconstruction Method (NUDIM) applicable to biological electron tomography is proposed with a combination of basic concepts from equally sloped tomography (EST) and NFFT based reconstruction. In NUDIM, the use of NFFT can circumvent such grid sampling inconsistency and thus alleviate the stringent equally-sloped sampling requirement in EST reconstruction, while the dual-space constraint iterative procedure can dramatically enhance reconstruction quality. In comparison with conventional reconstruction methods, NUDIM is numerically and experimentally demonstrated to produce superior reconstruction quality with higher contrast, less noise and reduced missing wedge artifacts. More importantly, it is also capable of retrieving part of missing information from a limited number of projections.

A novel constrained reconstruction model towards high-resolution subtomogram averaging

MOTIVATION

Electron tomography (ET) offers a unique capacity to image biological structures in situ. However, the resolution of ET reconstructed tomograms is not comparable to that of the single-particle cryo-EM. If many copies of the object of interest are present in the tomograms, their structures can be reconstructed in the tomogram, picked, aligned and averaged to increase the signal-to-noise ratio and improve the resolution, which is known as the subtomogram averaging. To date, the resolution improvement of the subtomogram averaging is still limited because each reconstructed subtomogram is of low reconstruction quality due to the missing wedge issue.

RESULTS

In this article, we propose a novel computational model, the constrained reconstruction model (CRM), to better recover the information from the multiple subtomograms and compensate for the missing wedge issue in each of them. CRM is supposed to produce a refined reconstruction in the final turn of subtomogram averaging after alignment, instead of directly taking the average. We first formulate the averaging method and our CRM as linear systems, and prove that the solution space of CRM is no larger, and in practice much smaller, than that of the averaging method. We then propose a sparse Kaczmarz algorithm to solve the formulated CRM, and further extend the solution to the simultaneous algebraic reconstruction technique (SART). Experimental results demonstrate that CRM can significantly alleviate the missing wedge issue and improve the final reconstruction quality. In addition, our model is robust to the number of images in each tilt series, the tilt range and the noise level.

AVAILABILITY AND IMPLEMENTATION

The codes of CRM-SIRT and CRM-SART are available at https://github.com/icthrm/CRM.

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.

Algorithmic robustness to preferred orientations in single particle analysis by CryoEM

The presence of preferred orientations in single particle analysis (SPA) by cryo-Electron Microscopy (cryoEM) is currently one of the hurdles preventing many structural analyses from yielding high-resolution structures. Although the existence of preferred orientations is mostly related to the grid preparation, in this technical note, we show that some image processing algorithms used for angular assignment and three-dimensional (3D) reconstruction are more robust than others to these detrimental conditions. We exemplify this argument with three different data sets in which the presence of preferred orientations hindered achieving a 3D reconstruction without artifacts or, even worse, a 3D reconstruction could never be achieved.

Cellular Electron Cryo-Tomography to Study Virus-Host Interactions

Viruses are obligatory intracellular parasites that reprogram host cells upon infection to produce viral progeny. Here, we review recent structural insights into virus-host interactions in bacteria, archaea, and eukaryotes unveiled by cellular electron cryo-tomography (cryoET). This advanced three-dimensional imaging technique of vitreous samples in near-native state has matured over the past two decades and proven powerful in revealing molecular mechanisms underlying viral replication. Initial studies were restricted to cell peripheries and typically focused on early infection steps, analyzing surface proteins and viral entry. Recent developments including cryo-thinning techniques, phase-plate imaging, and correlative approaches have been instrumental in also targeting rare events inside infected cells. When combined with advances in dedicated image analyses and processing methods, details of virus assembly and egress at (sub)nanometer resolution were uncovered. Altogether, we provide a historical and technical perspective and discuss future directions and impacts of cryoET for integrative structural cell biology analyses of viruses.

Computational Methods for Single-Particle Electron Cryomicroscopy

Single-particle electron cryomicroscopy (cryo-EM) is an increasingly popular technique for elucidating the three-dimensional structure of proteins and other biologically significant complexes at near-atomic resolution. It is an imaging method that does not require crystallization and can capture molecules in their native states. In single-particle cryo-EM, the three-dimensional molecular structure needs to be determined from many noisy two-dimensional tomographic projections of individual molecules, whose orientations and positions are unknown. The high level of noise and the unknown pose parameters are two key elements that make reconstruction a challenging computational problem. Even more challenging is the inference of structural variability and flexible motions when the individual molecules being imaged are in different conformational states. This review discusses computational methods for structure determination by single-particle cryo-EM and their guiding principles from statistical inference, machine learning, and signal processing that also play a significant role in many other data science applications.

Joint Angular Refinement and Reconstruction for Single-Particle Cryo-EM

Single-particle cryo-electron microscopy (cryo-EM) reconstructs the three-dimensional (3D) structure of biomolecules from a large set of 2D projection images with random and unknown orientations. A crucial step in the single-particle cryo-EM pipeline is 3D refinement, which resolves a highresolution 3D structure from an initial approximate volume by refining the estimation of the orientation of each projection. In this work, we propose a new approach that refines the projection angles on the continuum. We formulate the optimization problem over the density map and the orientations jointly. The density map is updated using the efficient alternating-direction method of multipliers, while the orientations are updated through a semicoordinate- wise gradient descent for which we provide an explicit derivation of the gradient. Our method eliminates the requirement for a fine discretization of the orientation space and does away with the classical but computationally expensive templatematching step. Numerical results demonstrate the feasibility and performance of our approach compared to several baselines.

Single-particle cryo-electron microscopy: Mathematical theory, computational challenges, and opportunities

In recent years, an abundance of new molecular structures have been elucidated using cryo-electron microscopy (cryo-EM), largely due to advances in hardware technology and data processing techniques. Owing to these new exciting developments, cryo-EM was selected by Nature Methods as Method of the Year 2015, and the Nobel Prize in Chemistry 2017 was awarded to three pioneers in the field. The main goal of this article is to introduce the challenging and exciting computational tasks involved in reconstructing 3-D molecular structures by cryo-EM. Determining molecular structures requires a wide range of computational tools in a variety of fields, including signal processing, estimation and detection theory, high-dimensional statistics, convex and non-convex optimization, spectral algorithms, dimensionality reduction, and machine learning. The tools from these fields must be adapted to work under exceptionally challenging conditions, including extreme noise levels, the presence of missing data, and massively large datasets as large as several Terabytes. In addition, we present two statistical models: multi-reference alignment and multi-target detection, that abstract away much of the intricacies of cryo-EM, while retaining some of its essential features. Based on these abstractions, we discuss some recent intriguing results in the mathematical theory of cryo-EM, and delineate relations with group theory, invariant theory, and information theory.

Non-uniformity of projection distributions attenuates resolution in Cryo-EM

Virtually all single-particle cryo-EM experiments currently suffer from specimen adherence to the air-water interface, leading to a non-uniform distribution in the set of projection views. Whereas it is well accepted that uniform projection distributions can lead to high-resolution reconstructions, non-uniform (anisotropic) distributions can negatively affect map quality, elongate structural features, and in some cases, prohibit interpretation altogether. Although some consequences of non-uniform sampling have been described qualitatively, we know little about how sampling quantitatively affects resolution in cryo-EM. Here, we show how inhomogeneity in any projection distribution scheme attenuates the global Fourier Shell Correlation (FSC) in relation to the number of particles and a single geometrical parameter, which we term the sampling compensation factor (SCF). The reciprocal of the SCF is defined as the average over Fourier shells of the reciprocal of the per-particle sampling and normalized to unity for uniform distributions. The SCF therefore ranges from one to zero, with values close to the latter implying large regions of poorly sampled or completely missing data in Fourier space. Using two synthetic test cases, influenza hemagglutinin and human apoferritin, we demonstrate how any amount of sampling inhomogeneity always attenuates the FSC compared to a uniform distribution. We advocate quantitative evaluation of the SCF criterion to approximate the effect of non-uniform sampling on resolution within experimental single-particle cryo-EM reconstructions.

MBIR: A cryo-ET 3D reconstruction method that effectively minimizes missing wedge artifacts and restores missing information

Cryo-Electron Tomography (cryo-ET) has become an essential technique in revealing cellular and macromolecular assembly structures in their native states. However, due to radiation damage and the limited tilt range, cryo-ET suffers from low contrast and missing wedge artifacts, which limits the tomograms to low resolution and hinders further biological interpretation. In this study, we applied the Model-Based Iterative Reconstruction (MBIR) method to obtain tomographic 3D reconstructions of experimental cryo-ET datasets and demonstrated the advantages of MBIR in contrast improvement, missing wedge artifacts reduction, missing information restoration, and subtomogram averaging compared with other reconstruction approaches. Considering the outstanding reconstruction quality, MBIR has a great potential in the determination of high resolution biological structures with cryo-ET.

Single-particle reconstruction statistics: a diagnostic tool in solving biomolecular structures by cryo-EM

In single-particle analysis (SPA), the aim is to obtain a 3D reconstruction of a biological molecule from 2D electron micrographs to the highest level of detail or resolution as possible. Current practice is to collect large volumes of data, hoping to reach high-resolution maps through sheer numbers. However, adding more particles from a specific data set eventually leads to diminishing improvements in resolution. Understanding what these resolution limits are and how to deal with them are important in optimization and automation of SPA. This study revisits the theory of 3D reconstruction and demonstrates how the associated statistics can provide a diagnostic tool to improve SPA. Small numbers of images already give sufficient information on micrograph quality and the amount of data required to reach high resolution. Such feedback allows the microscopist to improve sample-preparation and imaging parameters before committing to extensive data collection. Once a larger data set is available, a B factor can be determined describing the suppression of the signal owing to one or more causes, such as specimen movement, radiation damage, alignment inaccuracy and structural variation. Insight into the causes of signal suppression can then guide the user to consider appropriate actions to obtain better reconstructions.

Fast multiscale reconstruction for Cryo-EM

We present a multiscale reconstruction framework for single-particle analysis (SPA). The representation of three-dimensional (3D) objects with scaled basis functions permits the reconstruction of volumes at any desired scale in the real-space. This multiscale approach generates interesting opportunities in SPA for the stabilization of the initial volume problem or the 3D iterative refinement procedure. In particular, we show that reconstructions performed at coarse scale are more robust to angular errors and permit gains in computational speed. A key component of the proposed iterative scheme is its fast implementation. The costly step of reconstruction, which was previously hindering the use of advanced iterative methods in SPA, is formulated as a discrete convolution with a cost that does not depend on the number of projection directions. The inclusion of the contrast transfer function inside the imaging matrix is also done at no extra computational cost. By permitting full 3D regularization, the framework is by itself a robust alternative to direct methods for performing reconstruction in adverse imaging conditions (e.g., heavy noise, large angular misassignments, low number of projections). We present reconstructions obtained at different scales from a dataset of the 2015/2016 EMDataBank Map Challenge. The algorithm has been implemented in the Scipion package.

Rapid near-atomic resolution single-particle 3D reconstruction with SIMPLE

Cryogenic electron microscopy (cryo-EM) and single-particle analysis enables determination of near-atomic resolution structures of biological molecules. However, large computational requirements limit throughput and rapid testing of new image processing tools. We developed PRIME, an algorithm part of the SIMPLE software suite, for determination of the relative 3D orientations of single-particle projection images. PRIME has primarily found use for generation of an initial ab initio 3D reconstruction. Here we show that the strategy behind PRIME, iterative estimation of per-particle orientation distributions with stochastic hill climbing, provides a competitive approach to near-atomic resolution single-particle 3D reconstruction. A number of mathematical techniques for accelerating the convergence rate are introduced, leading to a speedup of nearly two orders of magnitude. We benchmarked our developments on numerous publicly available data sets and conclude that near-atomic resolution ab initio 3D reconstructions can be obtained with SIMPLE in a matter of hours, using standard over-the-counter CPU workstations.

A Survey of the Use of Iterative Reconstruction Algorithms in Electron Microscopy

One of the key steps in Electron Microscopy is the tomographic reconstruction of a three-dimensional (3D) map of the specimen being studied from a set of two-dimensional (2D) projections acquired at the microscope. This tomographic reconstruction may be performed with different reconstruction algorithms that can be grouped into several large families: direct Fourier inversion methods, back-projection methods, Radon methods, or iterative algorithms. In this review, we focus on the latter family of algorithms, explaining the mathematical rationale behind the different algorithms in this family as they have been introduced in the field of Electron Microscopy. We cover their use in Single Particle Analysis (SPA) as well as in Electron Tomography (ET).

The advent of structural biology in situ by single particle cryo-electron tomography

Single particle tomography (SPT), also known as subtomogram averaging, is a powerful technique uniquely poised to address questions in structural biology that are not amenable to more traditional approaches like X-ray crystallography, nuclear magnetic resonance, and conventional cryoEM single particle analysis. Owing to its potential for in situ structural biology at subnanometer resolution, SPT has been gaining enormous momentum in the last five years and is becoming a prominent, widely used technique. This method can be applied to unambiguously determine the structures of macromolecular complexes that exhibit compositional and conformational heterogeneity, both in vitro and in situ. Here we review the development of SPT, highlighting its applications and identifying areas of ongoing development.

Three-Dimensional Structures of Full-Length, Membrane-Embedded Human α(IIb)β(3) Integrin Complexes

Integrins are bidirectional, allosteric transmembrane receptors that play a central role in hemostasis and arterial thrombosis. Using cryo-electron microscopy, multireference single-particle reconstruction methods, and statistics-based computational fitting approaches, we determined three-dimensional structures of human integrin αIIbβ3 embedded in a lipid bilayer (nanodiscs) while bound to domains of the cytosolic regulator talin and to extracellular ligands. We also determined the conformations of integrin in solution by itself to localize the membrane and the talin-binding site. To our knowledge, our data provide unprecedented three-dimensional information about the conformational states of intact, full-length integrin within membrane bilayers under near-physiological conditions and in the presence of cytosolic activators and extracellular ligands. We show that αIIbβ3 integrins exist in a conformational equilibrium clustered around four main states. These conformations range from a compact bent nodule to two partially extended intermediate conformers and finally to a fully upright state. In the presence of nanodiscs and the two ligands, the equilibrium is significantly shifted toward the upright conformation. In this conformation, the receptor extends ∼20 nm upward from the membrane. There are no observable contacts between the two subunits other than those in the headpiece near the ligand-binding pocket, and the α- and β-subunits are well separated with their cytoplasmic tails ∼8 nm apart. Our results indicate that extension of the ectodomain is possible without separating the legs or extending the hybrid domain, and that the ligand-binding pocket is not occluded by the membrane in any conformations of the equilibrium. Further, they suggest that integrin activation may be influenced by equilibrium shifts.

Orthogonal Matrix Retrieval In Cryo-Electron Microscopy

In single particle reconstruction (SPR) from cryo-electron microscopy (EM), the 3D structure of a molecule needs to be determined from its 2D projection images taken at unknown viewing directions. Zvi Kam showed already in 1980 that the autocorrelation function of the 3D molecule over the rotation group SO(3) can be estimated from 2D projection images whose viewing directions are uniformly distributed over the sphere. The autocorrelation function determines the expansion coefficients of the 3D molecule in spherical harmonics up to an orthogonal matrix of size (2l + 1) × (2l + 1) for each l = 0,1,2,…. In this paper we show how techniques for solving the phase retrieval problem in X-ray crystallography can be modified for the cryo-EM setup for retrieving the missing orthogonal matrices. Specifically, we present two new approaches that we term Orthogonal Extension and Orthogonal Replacement, in which the main algorithmic components are the singular value decomposition and semidefinite programming. We demonstrate the utility of these approaches through numerical experiments on simulated data.

Cryogenic electron microscopy and single-particle analysis

About 20 years ago, the first three-dimensional (3D) reconstructions at subnanometer (<10-Å) resolution of an icosahedral virus assembly were obtained by cryogenic electron microscopy (cryo-EM) and single-particle analysis. Since then, thousands of structures have been determined to resolutions ranging from 30 Å to near atomic (<4 Å). Almost overnight, the recent development of direct electron detectors and the attendant improvement in analysis software have advanced the technology considerably. Near-atomic-resolution reconstructions can now be obtained, not only for megadalton macromolecular complexes or highly symmetrical assemblies but also for proteins of only a few hundred kilodaltons. We discuss the developments that led to this breakthrough in high-resolution structure determination by cryo-EM and point to challenges that lie ahead.

Architecture of the RNA polymerase II-Mediator core initiation complex

The conserved co-activator complex Mediator enables regulated transcription initiation by RNA polymerase (Pol) II. Here we reconstitute an active 15-subunit core Mediator (cMed) comprising all essential Mediator subunits from Saccharomyces cerevisiae. The cryo-electron microscopic structure of cMed bound to a core initiation complex was determined at 9.7 Å resolution. cMed binds Pol II around the Rpb4-Rpb7 stalk near the carboxy-terminal domain (CTD). The Mediator head module binds the Pol II dock and the TFIIB ribbon and stabilizes the initiation complex. The Mediator middle module extends to the Pol II foot with a 'plank' that may influence polymerase conformation. The Mediator subunit Med14 forms a 'beam' between the head and middle modules and connects to the tail module that is predicted to bind transcription activators located on upstream DNA. The Mediator 'arm' and 'hook' domains contribute to a 'cradle' that may position the CTD and TFIIH kinase to stimulate Pol II phosphorylation.

Covariance Matrix Estimation for the Cryo-EM Heterogeneity Problem

In cryo-electron microscopy (cryo-EM), a microscope generates a top view of a sample of randomly oriented copies of a molecule. The problem of single particle reconstruction (SPR) from cryo-EM is to use the resulting set of noisy two-dimensional projection images taken at unknown directions to reconstruct the three-dimensional (3D) structure of the molecule. In some situations, the molecule under examination exhibits structural variability, which poses a fundamental challenge in SPR. The heterogeneity problem is the task of mapping the space of conformational states of a molecule. It has been previously suggested that the leading eigenvectors of the covariance matrix of the 3D molecules can be used to solve the heterogeneity problem. Estimating the covariance matrix is challenging, since only projections of the molecules are observed, but not the molecules themselves. In this paper, we formulate a general problem of covariance estimation from noisy projections of samples. This problem has intimate connections with matrix completion problems and high-dimensional principal component analysis. We propose an estimator and prove its consistency. When there are finitely many heterogeneity classes, the spectrum of the estimated covariance matrix reveals the number of classes. The estimator can be found as the solution to a certain linear system. In the cryo-EM case, the linear operator to be inverted, which we term the projection covariance transform, is an important object in covariance estimation for tomographic problems involving structural variation. Inverting it involves applying a filter akin to the ramp filter in tomography. We design a basis in which this linear operator is sparse and thus can be tractably inverted despite its large size. We demonstrate via numerical experiments on synthetic datasets the robustness of our algorithm to high levels of noise.

Iterative reconstruction of cryo-electron tomograms using nonuniform fast Fourier transforms

Algorithms for three-dimensional (3D) reconstruction of objects based on their projections are essential in various biological and medical imaging modalities. In cryo-electron tomography (CET) a major challenge for reconstruction is the limited range of projection angles, which manifests itself as a "missing wedge" of data in Fourier space making the reconstruction problem ill-posed. Here, we apply an iterative reconstruction method that makes use of nonuniform fast Fourier transform (NUFFT) to the reconstruction of cryo-electron tomograms. According to several measures the reconstructions are superior to those obtained using conventional methods, most notably weighted backprojection. Most importantly, we show that it is possible to fill in partially the unsampled region in Fourier space with meaningful information without making assumptions about the data or applying prior knowledge. As a consequence, particles of known structure can be localized with higher confidence in cryotomograms and subtomogram averaging yields higher resolution densities.

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.

RELION: implementation of a Bayesian approach to cryo-EM structure determination

RELION, for REgularized LIkelihood OptimizatioN, is an open-source computer program for the refinement of macromolecular structures by single-particle analysis of electron cryo-microscopy (cryo-EM) data. Whereas alternative approaches often rely on user expertise for the tuning of parameters, RELION uses a Bayesian approach to infer parameters of a statistical model from the data. This paper describes developments that reduce the computational costs of the underlying maximum a posteriori (MAP) algorithm, as well as statistical considerations that yield new insights into the accuracy with which the relative orientations of individual particles may be determined. A so-called gold-standard Fourier shell correlation (FSC) procedure to prevent overfitting is also described. The resulting implementation yields high-quality reconstructions and reliable resolution estimates with minimal user intervention and at acceptable computational costs.

Real-space processing of helical filaments in SPARX

We present a major revision of the iterative helical real-space refinement (IHRSR) procedure and its implementation in the SPARX single particle image processing environment. We built on over a decade of experience with IHRSR helical structure determination and we took advantage of the flexible SPARX infrastructure to arrive at an implementation that offers ease of use, flexibility in designing helical structure determination strategy, and high computational efficiency. We introduced the 3D projection matching code which now is able to work with non-cubic volumes, the geometry better suited for long helical filaments, we enhanced procedures for establishing helical symmetry parameters, and we parallelized the code using distributed memory paradigm. Additional features include a graphical user interface that facilitates entering and editing of parameters controlling the structure determination strategy of the program. In addition, we present a novel approach to detect and evaluate structural heterogeneity due to conformer mixtures that takes advantage of helical structure redundancy.

A practical method to determine the effective resolution in incoherent experimental electron tomography

It is not straightforward to determine resolution for a 3D reconstruction when performing an electron tomography experiment. Different contributions such as missing wedge and misalignment add up and often influence the final resolution in an anisotropic manner. The conventional resolution measures can not be used for all of the reconstruction techniques, especially for iterative techniques which are more commonly used for electron tomography in materials science. Here we define a quantitative resolution measure that determines the resolution in three orthogonal directions of the reconstruction. As an application we use this measure to determine the optimum number of simultaneous iterative reconstruction technique (SIRT) iterations to reconstruct the gold nanoparticles, based on a high angle annular dark field STEM (HAADF-STEM) tilt series.

Single molecule microscopy methods for the study of DNA origami structures

Single molecule microscopy techniques play an important role in the investigation of advanced DNA structures such as those created by the DNA origami method. Three single molecule microscopy techniques are particularly interesting for the investigation of complex self-assembled three-dimensional (3D) DNA nanostructures, namely single molecule fluorescence microscopy, atomic force microscopy (AFM), and cryogenic transmission electron microscopy (cryo-EM). Here we discuss the strengths of these three techniques and demonstrate how their interplay can yield very important and unique new insights into the structure and conformation of advanced biological nanostructures. The applications of the three single molecule microscopy techniques are illustrated by focusing on a self-assembled DNA origami 3D box nanostructure. Its size and structure were studied by AFM and cryo-EM, while the lid opening, which can be controlled by the addition of oligonucleotide keys, was recorded by Förster/fluorescence resonance energy transfer (FRET) spectroscopy.

Fundamentals of three-dimensional reconstruction from projections

Three-dimensional (3D) reconstruction of an object mass density from the set of its 2D line projections lies at a core of both single-particle reconstruction technique and electron tomography. Both techniques utilize electron microscope to collect a set of projections of either multiple objects representing in principle the same macromolecular complex in an isolated form, or a subcellular structure isolated in situ. Therefore, the goal of macromolecular electron microscopy is to invert the projection transformation to recover the distribution of the mass density of the original object. The problem is interesting in that in its discrete form it is ill-posed and not invertible. Various algorithms have been proposed to cope with the practical difficulties of this inversion problem and their differ widely in terms of their robustness with respect to noise in the data, completeness of the collected projection dataset, errors in projections orientation parameters, abilities to efficiently handle large datasets, and other obstacles typically encountered in molecular electron microscopy. Here, we review the theoretical foundations of 3D reconstruction from line projections followed by an overview of reconstruction algorithms routinely used in practice of electron microscopy.

Heterogeneity of large macromolecular complexes revealed by 3D cryo-EM variance analysis

Macromolecular structure determination by cryo-electron microscopy (EM) and single-particle analysis are based on the assumption that imaged molecules have identical structure. With the increased size of processed data sets, it becomes apparent that many complexes coexist in a mixture of conformational states or contain flexible regions. We describe an implementation of the bootstrap resampling technique that yields estimates of voxel-by-voxel variance of a structure reconstructed from the set of its projections. We introduce a highly efficient reconstruction algorithm that is based on direct Fourier inversion and that incorporates correction for the transfer function of the microscope, thus extending the resolution limits of variance estimation. We also describe a validation method to determine the number of resampled volumes required to achieve stable estimate of the variance. The proposed bootstrap method was applied to a data set of 70S ribosome complexed with tRNA and the elongation factor G. The proposed method of variance estimation opens new possibilities for single-particle analysis, by extending applicability of the technique to heterogeneous data sets of macromolecules and to complexes with significant conformational variability.

Radiation dose reduction and image enhancement in biological imaging through equally-sloped tomography

Electron tomography is currently the highest resolution imaging modality available to study the 3D structures of pleomorphic macromolecular assemblies, viruses, organelles and cells. Unfortunately, the resolution is currently limited to 3-5nm by several factors including the dose tolerance of biological specimens and the inaccessibility of certain tilt angles. Here we report the first experimental demonstration of equally-sloped tomography (EST) to alleviate these problems. As a proof of principle, we applied EST to reconstructing frozen-hydrated keyhole limpet hemocyanin molecules from a tilt-series taken with constant slope increments. In comparison with weighted back-projection (WBP), the algebraic reconstruction technique (ART) and the simultaneous algebraic reconstruction technique (SART), EST reconstructions exhibited higher contrast, less peripheral noise, more easily detectable molecular boundaries and reduced missing wedge effects. More importantly, EST reconstructions including only two-thirds the original images appeared to have the same resolution as full WBP reconstructions, suggesting that EST can either reduce the dose required to reach a given resolution or allow higher resolutions to be achieved with a given dose. EST was also applied to reconstructing a frozen-hydrated bacterial cell from a tilt-series taken with constant angular increments. The results confirmed similar benefits when standard tilts are utilized.

Cryo-EM image alignment based on nonuniform fast Fourier transform

In single particle analysis, two-dimensional (2-D) alignment is a fundamental step intended to put into register various particle projections of biological macromolecules collected at the electron microscope. The efficiency and quality of three-dimensional (3-D) structure reconstruction largely depends on the computational speed and alignment accuracy of this crucial step. In order to improve the performance of alignment, we introduce a new method that takes advantage of the highly accurate interpolation scheme based on the gridding method, a version of the nonuniform fast Fourier transform, and utilizes a multi-dimensional optimization algorithm for the refinement of the orientation parameters. Using simulated data, we demonstrate that by using less than half of the sample points and taking twice the runtime, our new 2-D alignment method achieves dramatically better alignment accuracy than that based on quadratic interpolation. We also apply our method to image to volume registration, the key step in the single particle EM structure refinement protocol. We find that in this case the accuracy of the method not only surpasses the accuracy of the commonly used real-space implementation, but results are achieved in much shorter time, making gridding-based alignment a perfect candidate for efficient structure determination in single particle analysis.

Computational resources for cryo-electron tomography in Bsoft

The Bsoft package [Heymann, J.B., Belnap, D.M., 2007. Bsoft: image processing and molecular modeling for electron microscopy. J. Struct. Biol. 157, 3-18] has been enhanced by adding utilities for processing electron tomographic (ET) data; in particular, cryo-ET data characterized by low contrast and high noise. To handle the high computational load efficiently, a workflow was developed, based on the database-like parameter handling in Bsoft, aimed at minimizing user interaction and facilitating automation. To the same end, scripting elements distribute the processing among multiple processors on the same or different computers. The resolution of a tomogram depends on the precision of projection alignment, which is usually based on pinpointing fiducial markers (electron-dense gold particles). Alignment requires accurate specification of the tilt axis, and our protocol includes a procedure for determining it to adequate accuracy. Refinement of projection alignment provides information that allows assessment of its precision, as well as projection quality control. We implemented a reciprocal space algorithm that affords an alternative to back-projection or real space algorithms for calculating tomograms. Resources are also included that allow resolution assessment by cross-validation (NLOO2D); denoising and interpretation; and the extraction, mutual alignment, and averaging of tomographic sub-volumes.

A new cryo-EM single-particle ab initio reconstruction method visualizes secondary structure elements in an ATP-fueled AAA+ motor

The generation of ab initio three-dimensional (3D) models is a bottleneck in the studies of large macromolecular assemblies by single-particle cryo-electron microscopy. We describe here a novel method, in which established methods for two-dimensional image processing are combined with newly developed programs for joint rotational 3D alignment of a large number of class averages (RAD) and calculation of 3D volumes from aligned projections (VolRec). We demonstrate the power of the method by reconstructing an approximately 660-kDa ATP-fueled AAA+ motor to 7.5 A resolution, with secondary structure elements identified throughout the structure. We propose the method as a generally applicable automated strategy to obtain 3D reconstructions from unstained single particles imaged in vitreous ice.

SPARX, a new environment for Cryo-EM image processing

SPARX (single particle analysis for resolution extension) is a new image processing environment with a particular emphasis on transmission electron microscopy (TEM) structure determination. It includes a graphical user interface that provides a complete graphical programming environment with a novel data/process-flow infrastructure, an extensive library of Python scripts that perform specific TEM-related computational tasks, and a core library of fundamental C++ image processing functions. In addition, SPARX relies on the EMAN2 library and cctbx, the open-source computational crystallography library from PHENIX. The design of the system is such that future inclusion of other image processing libraries is a straightforward task. The SPARX infrastructure intelligently handles retention of intermediate values, even those inside programming structures such as loops and function calls. SPARX and all dependencies are free for academic use and available with complete source.

Cryo-electron microscopy of spliceosomal components

Splicing is an essential step of gene expression in which introns are removed from pre-mRNA to generate mature mRNA that can be translated by the ribosome. This reaction is catalyzed by a large and dynamic macromolecular RNP complex called the spliceosome. The spliceosome is formed by the stepwise integration of five snRNPs composed of U1, U2, U4, U5, and U6 snRNAs and more than 150 proteins binding sequentially to pre-mRNA. To study the structure of this particularly dynamic RNP machine that undergoes many changes in composition and conformation, single-particle cryo-electron microscopy (cryo-EM) is currently the method of choice. In this review, we present the results of these cryo-EM studies along with some new perspectives on structural and functional aspects of splicing, and we outline the perspectives and limitations of the cryo-EM technique in obtaining structural information about macromolecular complexes, such as the spliceosome, involved in splicing.

Fourier-based reconstruction for fully 3-D PET: optimization of interpolation parameters

Fourier-based approaches for three-dimensional (3-D) reconstruction are based on the relationship between the 3-D Fourier transform (FT) of the volume and the two-dimensional (2-D) FT of a parallel-ray projection of the volume. The critical step in the Fourier-based methods is the estimation of the samples of the 3-D transform of the image from the samples of the 2-D transforms of the projections on the planes through the origin of Fourier space, and vice versa for forward-projection (reprojection). The Fourier-based approaches have the potential for very fast reconstruction, but their straightforward implementation might lead to unsatisfactory results if careful attention is not paid to interpolation and weighting functions. In our previous work, we have investigated optimal interpolation parameters for the Fourier-based forward and back-projectors for iterative image reconstruction. The optimized interpolation kernels were shown to provide excellent quality comparable to the ideal sinc interpolator. This work presents an optimization of interpolation parameters of the 3-D direct Fourier method with Fourier reprojection (3D-FRP) for fully 3-D positron emission tomography (PET) data with incomplete oblique projections. The reprojection step is needed for the estimation (from an initial image) of the missing portions of the oblique data. In the 3D-FRP implementation, we use the gridding interpolation strategy, combined with proper weighting approaches in the transform and image domains. We have found that while the 3-D reprojection step requires similar optimal interpolation parameters as found in our previous studies on Fourier-based iterative approaches, the optimal interpolation parameters for the main 3D-FRP reconstruction stage are quite different. Our experimental results confirm that for the optimal interpolation parameters a very good image accuracy can be achieved even without any extra spectral oversampling, which is a common practice to decrease errors caused by interpolation in Fourier reconstruction.

The parallelization of SPIDER on distributed-memory computers using MPI

We describe the strategies and implementation details we employed to parallelize the SPIDER software package on distributed-memory parallel computers using the message passing interface (MPI). The MPI-enabled SPIDER preserves the interactive command line and batch interface used in the sequential version of SPIDER, thus does not require users to modify their existing batch programs. We show the excellent performance of the MPI-enabled SPIDER when it is used to perform multi-reference alignment and 3-D reconstruction operations on a number of different computing platforms. We point out some performance issues when the MPI-enabled SPIDER is used for a complete 3-D projection matching refinement run, and propose several ways to further improve the parallel performance of SPIDER on distributed-memory machines.

Estimation of variance in single-particle reconstruction using the bootstrap technique

Density maps of a molecule obtained by single-particle reconstruction from thousands of molecule projections exhibit strong changes in local definition and reproducibility, as a consequence of conformational variability of the molecule and non-stoichiometry of ligand binding. These changes complicate the interpretation of density maps in terms of molecular structure. A three-dimensional (3-D) variance map provides an effective tool to assess the structural definition in each volume element. In this work, the different contributions to the 3-D variance in a single-particle reconstruction are discussed, and an effective method for the estimation of the 3-D variance map is proposed, using a bootstrap technique of sampling. Computations with test data confirm the viability, computational efficiency, and accuracy of the method under conditions encountered in practical circumstances.

Unified 3-D structure and projection orientation refinement using quasi-Newton algorithm

We describe an algorithm for simultaneous refinement of a three-dimensional (3-D) density map and of the orientation parameters of two-dimensional (2-D) projections that are used to reconstruct this map. The application is in electron microscopy, where the 3-D structure of a protein has to be determined from a set of 2-D projections collected at random but initially unknown angles. The design of the algorithm is based on the assumption that initial low resolution approximation of the density map and reasonable guesses for orientation parameters are available. Thus, the algorithm is applicable in final stages of the structure refinement, when the quality of the results is of main concern. We define the objective function to be minimized in real space and solve the resulting nonlinear optimization problem using a Quasi-Newton algorithm. We calculate analytical derivatives with respect to density distribution and the finite difference approximations of derivatives with respect to orientation parameters. We demonstrate that calculation of derivatives is robust with respect to noise in the data. This is due to the fact that noise is annihilated by the back-projection operations. Our algorithm is distinguished from other orientation refinement methods (i) by the simultaneous update of the density map and orientation parameters resulting in a highly efficient computational scheme and (ii) by the high quality of the results produced by a direct minimization of the discrepancy between the 2-D data and the projected views of the reconstructed 3-D structure. We demonstrate the speed and accuracy of our method by using simulated data.