Fast rotational matching of single-particle images

The presence of noise and absence of contrast in electron micrographs lead to a reduced resolution of the final 3D reconstruction, due to the inherent limitations of single-particle image alignment. The fast rotational matching (FRM) algorithm was introduced recently for an accurate alignment of 2D images under such challenging conditions. Here, we implemented this algorithm for the first time in a standard 3D reconstruction package used in electron microscopy. This allowed us to carry out exhaustive tests of the robustness and reliability in iterative orientation determination, classification, and 3D reconstruction on simulated and experimental image data. A classification test on GroEL chaperonin images demonstrates that FRM assigns up to 13% more images to their correct reference orientation, compared to the classical self-correlation function method. Moreover, at sub-nanometer resolution, GroEL and rice dwarf virus reconstructions exhibit a remarkable resolution gain of 10-20% that is attributed to the novel image alignment kernel.     

High-throughput subtomogram alignment and classification by Fourier space constrained fast volumetric matching

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.     

Fast projection matching for cryo-electron microscopy image reconstruction

A new FFT-accelerated projection matching method is presented and tested. The electron microscopy images are represented by their Fourier-Bessel transforms and the 3D model by its expansion in spherical harmonics, or more specifically in terms of symmetry-adapted functions. The rotational and translational properties of these representations are used to quickly access all the possible 2D projections of the 3D model, which allow an exhaustive inspection of the whole five-dimensional domain of parameters associated to each particle.     

Accelerating and focusing protein-protein docking correlations using multi-dimensional rotational FFT generating functions

MOTIVATION: Predicting how proteins interact at the molecular level is a computationally intensive task. Many protein docking algorithms begin by using fast Fourier transform (FFT) correlation techniques to find putative rigid body docking orientations. Most such approaches use 3D Cartesian grids and are therefore limited to computing three dimensional (3D) translational correlations. However, translational FFTs can speed up the calculation in only three of the six rigid body degrees of freedom, and they cannot easily incorporate prior knowledge about a complex to focus and hence further accelerate the calculation. Furthemore, several groups have developed multi-term interaction potentials and others use multi-copy approaches to simulate protein flexibility, which both add to the computational cost of FFT-based docking algorithms. Hence there is a need to develop more powerful and more versatile FFT docking techniques. RESULTS: This article presents a closed-form 6D spherical polar Fourier correlation expression from which arbitrary multi-dimensional multi-property multi-resolution FFT correlations may be generated. The approach is demonstrated by calculating 1D, 3D and 5D rotational correlations of 3D shape and electrostatic expansions up to polynomial order L=30 on a 2 GB personal computer. As expected, 3D correlations are found to be considerably faster than 1D correlations but, surprisingly, 5D correlations are often slower than 3D correlations. Nonetheless, we show that 5D correlations will be advantageous when calculating multi-term knowledge-based interaction potentials. When docking the 84 complexes of the Protein Docking Benchmark, blind 3D shape plus electrostatic correlations take around 30 minutes on a contemporary personal computer and find acceptable solutions within the top 20 in 16 cases. Applying a simple angular constraint to focus the calculation around the receptor binding site produces acceptable solutions within the top 20 in 28 cases. Further constraining the search to the ligand binding site gives up to 48 solutions within the top 20, with calculation times of just a few minutes per complex. Hence the approach described provides a practical and fast tool for rigid body protein-protein docking, especially when prior knowledge about one or both binding sites is available.     

Estimating alignment errors in sets of 2-D images

We describe a robust and accurate method for the estimation of alignment errors for a set of two-dimensional images, in the case where the true pattern is unknown. The intended application of the proposed method is cryo-electron microscopy, where two-dimensional views of individual proteins in random orientations are observed in the electron microscope at low signal-to-noise ratio. By representing images in the basis of Fourier-harmonic coordinates and constructing averages and average intensities, we demonstrate that the variances of translation and rotational errors as well as of the Gaussian noise can be recovered. This machinery therefore allows one to isolate the various categories of errors that impede the quality of results in single particle reconstructions into constituent parts: translational errors, rotational errors, and additive noise.     

Multi-resolution contour-based fitting of macromolecular structures

A novel contour-based matching criterion is presented for the quantitative docking of high-resolution structures of components into low-resolution maps of macromolecular complexes. The proposed Laplacian filter is combined with a six-dimensional search using fast Fourier transforms to rapidly scan the rigid-body degrees of freedom of a probe molecule relative to a fixed target density map. A comparison of the docking performance with the standard cross-correlation criterion demonstrates that contour matching with the Laplacian filter significantly extends the viable resolution range of correlation-based fitting to resolutions as low as 30 A. The gain in docking precision at medium to low resolution (15-30 A) is critical for image reconstructions from electron microscopy (EM). The new algorithm enables for the first time the reliable docking of smaller molecular components into EM densities of large biomolecular assemblies at such low resolutions. As an example of the practical effectiveness of contour-based fitting, a new pseudo-atomic model of a microtubule was constructed from a 20 A resolution EM map and from atomic structures of alpha and beta tubulin subunits.     

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.     

Corrim-based alignment for improved speed in single-particle image processing

The technique of single-particle electron cryomicroscopy is currently making possible the 3D structure determination of large macromolecular complexes at constantly increasing levels of resolution. Work at resolution now attainable requires many thousands of individual images to be processed computationally. The most time-consuming step of the image-processing procedure is usually the iterative alignment of individual particle images against a set of reference images derived from a preliminary 3-D structure. We have developed an improved multireference alignment procedure based on interpolated cross-correlation images (corrims) that results in an approximately 8-fold acceleration of the iterative alignment steps. These corrims can be used to restrict the number of image-alignment calculations by narrowing down the set of reference images. Another improvement in alignment speed has been achieved by optimising the software and its implementation on many parallel processors. This new corrim-based refinement has been found to work well with two different alignment algorithms, the commonly used "fast alignment by separate translational/rotational searches" and "exhaustive alignment by polar coordinates."     

An approach to examining model dependence in EM reconstructions using cross-validation

Reference bias refers to a common problem in fitting experimental data to an initial model. Given enough free parameters, a good fit of any experimental data to the model can be obtained, even if the experimental data contain only noise. Reference-based alignment methods used in electron microscopy (EM) are subject to this type of bias, in that images containing pure noise can regenerate the reference. Cross-validation is based on the idea that the experimental data used to assess the validity of the fitting should not be the same data as were used to do the fitting. Here we present the application of cross-validation to one form of reference-based alignment: 3D-projection matching in single-particle reconstructions. Our results show that reference bias is indeed present in reconstructions, but that the effect is small for real data compared to that for random noise, and that this difference in behavior is magnified, rather than diminished, during iterative refinement.     

An automatic matching technique for patient alignment

An automatic system of patient alignment is required in order to monitor changes that occur in the period between magnetic resonance scans. For each scan of the patient a prime requisite is to register the images with respect to each other. The orthogonal relationship between the sagittal and transverse images should, in principle, identify a single common line at the intersection of the two image planes. The basis of the comparison requires spatial registration of the two images to correct for the probable translational and rotational tilts as well as for the geometrical and intensity distortions. This paper describes a number of automatic techniques which compare, pixel-by-pixel, first two synthetic images, and then their application to real images obtained separately from the same head and neck object field. The robustness, computational cost and effectiveness of the techniques presented are discussed, and computed results on real data for the most promising technique based on the Ratio Absolute Difference algorithm are presented.     

Transform-based backprojection for volume reconstruction of large format electron microscope tilt series

Alignment of the individual images of a tilt series is a critical step in obtaining high-quality electron microscope reconstructions. We report on general methods for producing good alignments, and utilizing the alignment data in subsequent reconstruction steps. Our alignment techniques utilize bundle adjustment. Bundle adjustment is the simultaneous calculation of the position of distinguished markers in the object space and the transforms of these markers to their positions in the observed images, along the bundle of particle trajectories along which the object is projected to each EM image. Bundle adjustment techniques are general enough to encompass the computation of linear, projective or nonlinear transforms for backprojection, and can compensate for curvilinear trajectories through the object, sample warping, and optical aberration. We will also report on new reconstruction codes and describe our results using these codes.     

Fourier methods for biosequence analysis.

Novel methods are discussed for using fast Fourier transforms for DNA or protein sequence comparison. These methods are also intended as a contribution to the more general computer science problem of text search. These methods extend the capabilities of previous FFT methods and show that these methods are capable of considerable refinement. In particular, novel methods are given which (1) enable the detection of clusters of matching letters, (2) facilitate the insertion of gaps to enhance sequence similarity, and (3) accommodate to varying densities of letters in the input sequences. These methods use Fourier analysis in two distinct ways. (1) Fast Fourier transforms are used to facilitate rapid computation. (2) Fourier expansions are used to form an 'image' of the sequence comparison.     

Rotational and translational swimming of human spermatozoa: a dynamic laser light scattering study

The rotational swimming motion of human spermatozoa is evaluated from measurements of depolarized dynamic laser light scattering at zero angle. The analysis is based on a Maxwellian angular velocity distribution and yields a rotational frequency of about 4 Hz that is ascribed to the rotation of the sperm head. From comparison with the translational swimming motion, a propelling efficiency of about 10 micron per turn is deduced. This parameter describes the linkage between the rotational and translational swimming motion and is likely to be discriminatory in the analysis of physiological and pathological sperm motions.     

Multiplexed Nanometric 3D Tracking of Microbeads Using an FFT-Phasor Algorithm

Many single-molecule biophysical techniques rely on nanometric tracking of microbeads to obtain quantitative information about the mechanical properties of biomolecules such as chromatin fibers. Their three-dimensional (3D) position can be resolved by holographic analysis of the diffraction pattern in wide-field imaging. Fitting this diffraction pattern to Lorenz-Mie scattering theory yields the bead’s position with nanometer accuracy in three dimensions but is computationally expensive. Real-time multiplexed bead tracking therefore requires a more efficient tracking method, such as comparison with previously measured diffraction patterns, known as look-up tables. Here, we introduce an alternative 3D phasor algorithm that provides robust bead tracking with nanometric localization accuracy in a z range of over 10 μm under nonoptimal imaging conditions. The algorithm is based on a two-dimensional cross correlation using fast Fourier transforms with computer-generated reference images, yielding a processing rate of up to 10,000 regions of interest per second. We implemented the technique in magnetic tweezers and tracked the 3D position of over 100 beads in real time on a generic CPU. The accuracy of 3D phasor tracking was extensively tested and compared to a look-up table approach using Lorenz-Mie simulations, avoiding experimental uncertainties. Its easy implementation, efficiency, and robustness can improve multiplexed biophysical bead-tracking applications, especially when high throughput is required and image artifacts are difficult to avoid.     

The structure of the V(1)-ATPase determined by three-dimensional electron microscopy of single particles

We determined the structure of the V(1)-ATPase from Manduca sexta to a resolution of 1.8 nm, which for the first time reveals internal features of the enzyme. The V(1)-ATPase consists of a headpiece of 13.5 nm in diameter, with six elongated subunits, A(3) and B(3), of approximately equal size, and a stalk of 6 nm in length that connects V(1) with the membrane-bound domain, V(O). At the center of the molecule is a cavity that extends throughout the length of the A(3)B(3) hexamer. Inside the cavity the central stalk can be seen connected to only two of the catalytic A subunits. The structure was obtained by a combination of the Random Conical Reconstruction Technique and angular refinements. Additional recently developed techniques that were used include methods for simultaneous translational rotational alignment of the 0 degrees images, contrast transfer function correction for tilt images, and the Two-Step Radon Inversion Algorithm.     

A maximum likelihood approach to two-dimensional crystals

Maximum likelihood (ML) processing of transmission electron microscopy images of protein particles can produce reconstructions of superior resolution due to a reduced reference bias. We have investigated a ML processing approach to images centered on the unit cells of two-dimensional (2D) crystal images. The implemented software makes use of the predictive lattice node tracking in the MRC software, which is used to window particle stacks. These are then noise-whitened and subjected to ML processing. Resulting ML maps are translated into amplitudes and phases for further processing within the 2dx software package. Compared with ML processing for randomly oriented single particles, the required computational costs are greatly reduced as the 2D crystals restrict the parameter search space. The software was applied to images of negatively stained or frozen hydrated 2D crystals of different crystal order. We find that the ML algorithm is not free from reference bias, even though its sensitivity to noise correlation is lower than for pure cross-correlation alignment. Compared with crystallographic processing, the newly developed software yields better resolution for 2D crystal images of lower crystal quality, and it performs equally well for well-ordered crystal images.     

Orientation variance as a quantifier of structure in texture

I consider how structure is derived from texture containing changes in orientation over space, and propose that multi-local orientation variance (the average orientation variance across a series of discrete images locales) is an estimate of the degree of organization that is useful both for spatial scale selection and for discriminating structure from noise. The oriented textures used in this paper are Glass patterns, which contain structure at a narrow range of scales. The effect of adding noise to Glass patterns, on a structure versus noise task (Maloney et al., 1987), is compared to discrimination based on orientation variance and template matching (i.e. having prior knowledge of the target's orientation structure). At all but very low densities, the variance model accounts well for human data. Next, both models' estimates of tolerable orientation variance are shown to be broadly consistent with human discrimination of texture from noise. However, neither model can account for subjects' lower tolerance to noise for translational patterns than other (e.g. rotational) patterns. Finally, to investigate how well these structural measures preserve local orientation discontinuities, I show that the presence of a patch of unstructured dots embedded in a Glass pattern produces a change in multi-local orientation variance that is sufficient to account for human detection (Hel Or and Zucker, 1989). Together, these data suggest that simple orientation statistics could drive a range of 'texture tasks', although the dependency of noise resistance on the pattern type (rotation, translation, etc.) remains to be accounted for.     

Structural Information, Resolution, and Noise in High-Resolution Atomic Force Microscopy Topographs

AFM has developed into a powerful tool in structural biology, providing topographs of proteins under close-to-native conditions and featuring an outstanding signal/noise ratio. However, the imaging mechanism exhibits particularities: fast and slow scan axis represent two independent image acquisition axes. Additionally, unknown tip geometry and tip-sample interaction render the contrast transfer function nondefinable. Hence, the interpretation of AFM topographs remained difficult. How can noise and distortions present in AFM images be quantified? How does the number of molecule topographs merged influence the structural information provided by averages? What is the resolution of topographs? Here, we find that in high-resolution AFM topographs, many molecule images are only slightly disturbed by noise, distortions, and tip-sample interactions. To identify these high-quality particles, we propose a selection criterion based on the internal symmetry of the imaged protein. We introduce a novel feature-based resolution analysis and show that AFM topographs of different proteins contain structural information beginning at different resolution thresholds: 10 Å (AqpZ), 12 Å (AQP0), 13 Å (AQP2), and 20 Å (light-harvesting-complex-2). Importantly, we highlight that the best single-molecule images are more accurate molecular representations than ensemble averages, because averaging downsizes the z-dimension and “blurs” structural details.Abbreviations: 2D, two-dimensional; 3D, three-dimensional; ACV, auto-correlation value; AFM, atomic force microscopy; AQP0, aquaporin-0; AQP2, aquaporin-2; AqpZ, aquaporin-Z; bR, bacteriorhodopsin; CCV, cross-correlation value; CTF, contrast transfer function; DPR, differential phase residual; EM, electron microscopy; FRC, Fourier ring correlation; FSC, Fourier shell correlation; IS, internal symmetry; LH2, light-harvesting-complex 2; RMSD, root mean-square deviation; SD, standard deviation; SNR, signal/noise ratio; SSNR, spectral signal/noise ratio     

A multiresolution approach to orientation assignment in 3D electron microscopy of single particles

Three-dimensional (3D) electron microscopy (3DEM) aims at the determination of the spatial distribution of the Coulomb potential of macromolecular complexes. The 3D reconstruction of a macromolecule using single-particle techniques involves thousands of 2D projections. One of the key parameters required to perform such a 3D reconstruction is the orientation of each projection image as well as its in-plane orientation. This information is unknown experimentally and must be determined using image-processing techniques. We propose the use of wavelets to match the experimental projections with those obtained from a reference 3D model. The wavelet decomposition of the projection images provides a framework for a multiscale matching algorithm in which speed and robustness to noise are gained. Furthermore, this multiresolution approach is combined with a novel orientation selection strategy. Results obtained from computer simulations as well as experimental data encourage the use of this approach.