High precision alignment of cryo-electron subtomograms through gradient-based parallel optimization.
ABSTRACT: Cryo-electron tomography emerges as an important component for structural system biology. It not only allows the structural characterization of macromolecular complexes, but also the detection of their cellular localizations in near living conditions. However, the method is hampered by low resolution, missing data and low signal-to-noise ratio (SNR). To overcome some of these difficulties and enhance the nominal resolution one can align and average a large set of subtomograms. Existing methods for obtaining the optimal alignments are mostly based on an exhaustive scanning of all but discrete relative rigid transformations (i.e. rotations and translations) of one subtomogram with respect to the other.In this paper, we propose gradient-guided alignment methods based on two popular subtomogram similarity measures, a real space as well as a Fourier-space constrained score. We also propose a stochastic parallel refinement method that increases significantly the efficiency for the simultaneous refinement of a set of alignment candidates. We estimate that our stochastic parallel refinement is on average about 20 to 40 fold faster in comparison to the standard independent refinement approach. Results on simulated data of model complexes and experimental structures of protein complexes show that even for highly distorted subtomograms and with only a small number of very sparsely distributed initial alignment seeds, our combined methods can accurately recover true transformations with a substantially higher precision than the scanning based alignment methods.Our methods increase significantly the efficiency and accuracy for subtomogram alignments, which is a key factor for the systematic classification of macromolecular complexes in cryo-electron tomograms of whole cells.
Project description:Whole cell cryo-electron tomography emerges as an important component for structural system biology approaches. It allows the localization and structural characterization of macromolecular complexes in near living conditions. However, the method is hampered by low resolution, missing data and low signal-to-noise ratio (SNR). To overcome some of these difficulties one can align and average a large set of subtomograms. Existing alignment methods are mostly based on an exhaustive scanning and sampling of all but discrete relative rotations and translations of one subtomogram with respect to the other. In this paper, we propose a gradient-guided alignment method based on two subtomogram similarity measures. We also propose a stochastic parallel optimization that increases significantly the efficiency for the simultaneous refinement of a set of alignment candidates. Results on simulated data of model complexes and experimental structures of protein complexes show that even for highly distorted subtomograms and with only a small number of very sparsely distributed initial alignment seeds, our method can accurately recover true transformations with a significantly higher precision than scanning based alignment methods.
Project description:Cryo-electron tomography allows the imaging of macromolecular complexes in near living conditions. To enhance the nominal resolution of a structure it is necessary to align and average individual subtomograms each containing identical complexes. However, if the sample of complexes is heterogeneous, it is necessary to first classify subtomograms into groups of identical complexes. This task becomes challenging when tomograms contain mixtures of unknown complexes extracted from a crowded environment. Two main challenges must be overcomed: First, classification of subtomograms must be performed without knowledge of template structures. However, most alignment methods are too slow to perform reference-free classification of a large number of (e.g. tens of thousands) of subtomograms. Second, subtomograms extracted from crowded cellular environments, contain often fragments of other structures besides the target complex. However, alignment methods generally assume that each subtomogram only contains one complex. Automatic methods are needed to identify the target complexes in a subtomogram even when its shape is unknown.In this article, we propose an automatic and systematic method for the isolation and masking of target complexes in subtomograms extracted from crowded environments. Moreover, we also propose a fast alignment method using fast rotational matching in real space. Our experiments show that, compared with our previously proposed fast alignment method in reciprocal space, our new method significantly improves the alignment accuracy for highly distorted and especially crowded subtomograms. Such improvements are important for achieving successful and unbiased high-throughput reference-free structural classification of complexes inside whole-cell tomograms.Supplementary data are available at Bioinformatics online.
Project description:Cryo-electron tomography (cryo-ET) captures the 3D electron density distribution of macromolecular complexes in close to native state. With the rapid advance of cryo-ET acquisition technologies, it is possible to generate large numbers (>100,000) of subtomograms, each containing a macromolecular complex. Often, these subtomograms represent a heterogeneous sample due to variations in the structure and composition of a complex in situ form or because particles are a mixture of different complexes. In this case subtomograms must be classified. However, classification of large numbers of subtomograms is a time-intensive task and often a limiting bottleneck. This paper introduces an open source software platform, TomoMiner, for large-scale subtomogram classification, template matching, subtomogram averaging, and alignment. Its scalable and robust parallel processing allows efficient classification of tens to hundreds of thousands of subtomograms. In addition, TomoMiner provides a pre-configured TomoMinerCloud computing service permitting users without sufficient computing resources instant access to TomoMiners high-performance features.
Project description:Macromolecular complexes are intrinsically flexible and often challenging to purify for structure determination by single-particle cryo-electron microscopy (cryo-EM). Such complexes can be studied by cryo-electron tomography (cryo-ET) combined with subtomogram alignment and classification, which in exceptional cases achieves subnanometer resolution, yielding insight into structure-function relationships. However, it remains challenging to apply this approach to specimens that exhibit conformational or compositional heterogeneity or are present in low abundance. To address this, we developed emClarity ( https://github.com/bHimes/emClarity/wiki ), a GPU-accelerated image-processing package featuring an iterative tomographic tilt-series refinement algorithm that uses subtomograms as fiducial markers and a 3D-sampling-function-compensated, multi-scale principal component analysis classification method. We demonstrate that our approach offers substantial improvement in the resolution of maps and in the separation of different functional states of macromolecular complexes compared with current state-of-the-art software.
Project description:BACKGROUND:Cryo-electron tomography (Cryo-ET) is an imaging technique used to generate three-dimensional structures of cellular macromolecule complexes in their native environment. Due to developing cryo-electron microscopy technology, the image quality of three-dimensional reconstruction of cryo-electron tomography has greatly improved. However, cryo-ET images are characterized by low resolution, partial data loss and low signal-to-noise ratio (SNR). In order to tackle these challenges and improve resolution, a large number of subtomograms containing the same structure needs to be aligned and averaged. Existing methods for refining and aligning subtomograms are still highly time-consuming, requiring many computationally intensive processing steps (i.e. the rotations and translations of subtomograms in three-dimensional space). RESULTS:In this article, we propose a Stochastic Average Gradient (SAG) fine-grained alignment method for optimizing the sum of dissimilarity measure in real space. We introduce a Message Passing Interface (MPI) parallel programming model in order to explore further speedup. CONCLUSIONS:We compare our stochastic average gradient fine-grained alignment algorithm with two baseline methods, high-precision alignment and fast alignment. Our SAG fine-grained alignment algorithm is much faster than the two baseline methods. Results on simulated data of GroEL from the Protein Data Bank (PDB ID:1KP8) showed that our parallel SAG-based fine-grained alignment method could achieve close-to-optimal rigid transformations with higher precision than both high-precision alignment and fast alignment at a low SNR (SNR=0.003) with tilt angle range ±60? or ±40?. For the experimental subtomograms data structures of GroEL and GroEL/GroES complexes, our parallel SAG-based fine-grained alignment can achieve higher precision and fewer iterations to converge than the two baseline methods.
Project description:Motivation:Cellular Electron CryoTomography (CECT) is an emerging 3D imaging technique that visualizes subcellular organization of single cells at sub-molecular resolution and in near-native state. CECT captures large numbers of macromolecular complexes of highly diverse structures and abundances. However, the structural complexity and imaging limits complicate the systematic de novo structural recovery and recognition of these macromolecular complexes. Efficient and accurate reference-free subtomogram averaging and classification represent the most critical tasks for such analysis. Existing subtomogram alignment based methods are prone to the missing wedge effects and low signal-to-noise ratio (SNR). Moreover, existing maximum-likelihood based methods rely on integration operations, which are in principle computationally infeasible for accurate calculation. Results:Built on existing works, we propose an integrated method, Fast Alignment Maximum Likelihood method (FAML), which uses fast subtomogram alignment to sample sub-optimal rigid transformations. The transformations are then used to approximate integrals for maximum-likelihood update of subtomogram averages through expectation-maximization algorithm. Our tests on simulated and experimental subtomograms showed that, compared to our previously developed fast alignment method (FA), FAML is significantly more robust to noise and missing wedge effects with moderate increases of computation cost. Besides, FAML performs well with significantly fewer input subtomograms when the FA method fails. Therefore, FAML can serve as a key component for improved construction of initial structural models from macromolecules captured by CECT. Availability and implementation:http://www.cs.cmu.edu/mxu1.
Project description:Cryo-electron tomography allows the visualization of macromolecular complexes in their cellular environments in close-to-live conditions. The nominal resolution of subtomograms can be significantly increased when individual subtomograms of the same kind are aligned and averaged. A vital step for such a procedure are algorithms that speedup subtomogram alignment and improve its accuracy to allow reference-free subtomogram classifications. Such methods will facilitate automation of tomography analysis and overall high throughput in the data processing. Building on previous work, here we propose a fast rotational alignment method that uses the Fourier equivalent form of a popular constrained correlation measure that considers missing wedge corrections and density variances in the subtomograms. The fast rotational search is based on 3D volumetric matching, which improves the rotational alignment accuracy in particular for highly distorted subtomograms with low SNR and tilt angle ranges in comparison to fast rotational matching of projected 2D spherical images. We further integrate our fast rotational alignment method in a reference-free iterative subtomogram classification scheme, and propose a local feature enhancement strategy in the classification process. As a proof of principle, we can demonstrate that the automatic method can successfully classify a large number of experimental subtomograms without the need of a reference structure.
Project description:The resolution of subtomogram averages calculated from cryo-electron tomograms (cryo-ET) of crowded cellular environments is often limited owing to signal loss in, and misalignment of, the subtomograms. By contrast, single-particle cryo-electron microscopy (SP-cryo-EM) routinely reaches near-atomic resolution of isolated complexes. We report a method called 'tomography-guided 3D reconstruction of subcellular structures' (TYGRESS) that is a hybrid of cryo-ET and SP-cryo-EM, and is able to achieve close-to-nanometer resolution of complexes inside crowded cellular environments. TYGRESS combines the advantages of SP-cryo-EM (images with good signal-to-noise ratio and contrast, as well as minimal radiation damage) and subtomogram averaging (three-dimensional alignment of macromolecules in a complex sample). Using TYGRESS, we determined the structure of the intact ciliary axoneme with up to resolution of 12?Å. These results reveal many structural details that were not visible by cryo-ET alone. TYGRESS is generally applicable to cellular complexes that are amenable to subtomogram averaging.
Project description:Electron cryo-tomography (cryo-ET) is a technique that is used to produce 3D pictures (tomograms) of complex objects such as asymmetric viruses, cellular organelles or whole cells from a series of tilted electron cryo-microscopy (cryo-EM) images. Averaging of macromolecular complexes found within tomograms is known as subtomogram averaging, and this technique allows structure determination of macromolecular complexes in situ. Subtomogram averaging is also gaining in popularity for the calculation of initial models for single-particle analysis. We describe herein a protocol for subtomogram averaging from cryo-ET data using the RELION software (http://www2.mrc-lmb.cam.ac.uk/relion). RELION was originally developed for cryo-EM single-particle analysis, and the subtomogram averaging approach presented in this protocol has been implemented in the existing workflow for single-particle analysis so that users may conveniently tap into existing capabilities of the RELION software. We describe how to calculate 3D models for the contrast transfer function (CTF) that describe the transfer of information in the imaging process, and we illustrate the results of classification and subtomogram averaging refinement for cryo-ET data of purified hepatitis B capsid particles and Saccharomyces cerevisiae 80S ribosomes. Using the steps described in this protocol, along with the troubleshooting and optimization guidelines, high-resolution maps can be obtained in which secondary structure elements are resolved subtomogram.
Project description:The reference-free averaging of three-dimensional electron microscopy (3D-EM) reconstructions with empty regions in Fourier space represents a pressing problem in electron tomography and single-particle analysis. We present a maximum likelihood algorithm for the simultaneous alignment and classification of subtomograms or random conical tilt (RCT) reconstructions, where the Fourier components in the missing data regions are treated as hidden variables. The behavior of this algorithm was explored using tests on simulated data, while application to experimental data was shown to yield unsupervised class averages for subtomograms of groEL/groES complexes and RCT reconstructions of p53. The latter application served to obtain a reliable de novo structure for p53 that may resolve uncertainties about its quaternary structure.