ASOCEM: Automatic Segmentation Of Contaminations in cryo-EM.

Particle picking is currently a critical step in the cryo-electron microscopy single particle reconstruction pipeline. Contaminations in the acquired micrographs severely degrade the performance of particle pickers, resulting in many "non-particles" in the collected stack of particles. In this paper, we present ASOCEM (Automatic Segmentation Of Contaminations in cryo-EM), an automatic method to detect and segment contaminations, which requires as an input only the approximate particle size. In particular, it does not require any parameter tuning nor manual intervention. Our method is based on the observation that the statistical distribution of contaminated regions is different from that of the rest of the micrograph. This nonrestrictive assumption allows to automatically detect various types of contaminations, from the carbon edges of the supporting grid to high contrast blobs of different sizes. We demonstrate the efficiency of our algorithm using various experimental data sets containing various types of contaminations. ASOCEM is integrated as part of the KLT picker (Eldar et al., 2020) and is available at https://github.com/ShkolniskyLab/kltpicker2.

KLT picker: Particle picking using data-driven optimal templates.

Particle picking is currently a critical step in the cryo-EM single particle reconstruction pipeline. Despite extensive work on this problem, for many data sets it is still challenging, especially for low SNR micrographs. We present the KLT (Karhunen Loeve Transform) picker, which is fully automatic and requires as an input only the approximated particle size. In particular, it does not require any manual picking. Our method is designed especially to handle low SNR micrographs. It is based on learning a set of optimal templates through the use of multi-variate statistical analysis via the Karhunen Loeve Transform. We evaluate the KLT picker on publicly available data sets and present high-quality results with minimal manual effort.

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

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

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

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

Signal enhancement for two-dimensional cryo-EM data processing.

Different tasks in the computational pipeline of single-particle cryo-electron microscopy (cryo-EM) require enhancing the quality of the highly noisy raw images. To this end, we develop an efficient algorithm for signal enhancement of cryo-EM images. The enhanced images can be used for a variety of downstream tasks, such as two-dimensional classification, removing uninformative images, constructing ab initio models, generating templates for particle picking, providing a quick assessment of the data set, dimensionality reduction, and symmetry detection. The algorithm includes built-in quality measures to assess its performance and alleviate the risk of model bias. We demonstrate the effectiveness of the proposed algorithm on several experimental data sets. In particular, we show that the quality of the resulting images is high enough to produce ab initio models of Å resolution. The algorithm is accompanied by a publicly available, documented, and easy-to-use code.

Cryo-EM photosystem I structure reveals adaptation mechanisms to extreme high light in Chlorella ohadii.

Photosynthesis in deserts is challenging since it requires fast adaptation to rapid night-to-day changes, that is, from dawn's low light (LL) to extreme high light (HL) intensities during the daytime. To understand these adaptation mechanisms, we purified photosystem I (PSI) from Chlorella ohadii, a green alga that was isolated from a desert soil crust, and identified the essential functional and structural changes that enable the photosystem to perform photosynthesis under extreme high light conditions. The cryo-electron microscopy structures of PSI from cells grown under low light (PSILL) and high light (PSIHL), obtained at 2.70 and 2.71 Å, respectively, show that part of light-harvesting antenna complex I (LHCI) and the core complex subunit (PsaO) are eliminated from PSIHL to minimize the photodamage. An additional change is in the pigment composition and their number in LHCIHL; about 50% of chlorophyll b is replaced by chlorophyll a. This leads to higher electron transfer rates in PSIHL and might enable C. ohadii PSI to act as a natural photosynthesiser in photobiocatalytic systems. PSIHL or PSILL were attached to an electrode and their induced photocurrent was determined. To obtain photocurrents comparable with PSIHL, 25 times the amount of PSILL was required, demonstrating the high efficiency of PSIHL. Hence, we suggest that C. ohadii PSIHL is an ideal candidate for the design of desert artificial photobiocatalytic systems.

Detecting consistent common lines in cryo-EM by voting.

The single-particle reconstruction problem of electron cryo-microscopy (cryo-EM) is to find the three-dimensional structure of a macromolecule given its two-dimensional noisy projection images at unknown random directions. Ab initio estimates of the 3D structure are often obtained by the "Angular Reconstitution" method, in which a coordinate system is established from three projections, and the orientation of the particle giving rise to each image is deduced from common lines among the images. However, a reliable detection of common lines is difficult due to the low signal-to-noise ratio of the images. In this paper we describe a global self-correcting voting procedure in which all projection images participate to decide the identity of the consistent common lines. The algorithm determines which common line pairs were detected correctly and which are spurious. We show that the voting procedure succeeds at relatively low detection rates and that its performance improves as the number of projection images increases. We demonstrate the algorithm for both simulative and experimental images of the 50S ribosomal subunit.

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

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

Angular super-resolution retrieval in small-angle X-ray scattering.

Small-angle X-ray scattering (SAXS) techniques enable convenient nanoscopic characterization for various systems and conditions. Unlike synchrotron-based setups, lab-based SAXS systems intrinsically suffer from lower X-ray flux and limited angular resolution. Here, we develop a two-step retrieval methodology to enhance the angular resolution for given experimental conditions. Using minute hardware additions, we show that translating the X-ray detector in subpixel steps and modifying the incoming beam shape results in a set of 2D scattering images, which is sufficient for super-resolution SAXS retrieval. The technique is verified experimentally to show superior resolution. Such advantages have a direct impact on the ability to resolve finer nanoscopic structures and can be implemented in most existing SAXS apparatuses both using synchrotron- and laboratory-based sources.

Structure and energy transfer pathways of the Dunaliella Salina photosystem I supercomplex.

Oxygenic photosynthesis evolved more than 3 billion years ago in cyanobacteria. The increased complexity of photosystem I (PSI) became apparent from the high-resolution structures that were obtained for the complexes that were isolated from various organisms, ranging from cyanobacteria to plants. These complexes are all evolutionarily linked. In this paper, the researchers have uncovered the increased complexity of PSI in a single organism demonstrated by the coexistance of two distinct PSI compositions. The Large Dunaliella PSI contains eight additional subunits, six in PSI core and two light harvesting complexes. Two additional chlorophyll a molecules pertinent for efficient excitation energy transfer in state II transition were identified in PsaL and PsaO. Short distances between these newly identified chlorophylls correspond with fast excitation transfer rates previously reported during state II transition. The apparent PSI conformations could be a coping mechanism for the high salinity.

Structural basis for SARM1 inhibition and activation under energetic stress.

SARM1, an executor of axonal degeneration, displays NADase activity that depletes the key cellular metabolite, NAD+, in response to nerve injury. The basis of SARM1 inhibition and its activation under stress conditions are still unknown. Here, we present cryo-EM maps of SARM1 at 2.9 and 2.7 Å resolutions. These indicate that SARM1 homo-octamer avoids premature activation by assuming a packed conformation, with ordered inner and peripheral rings, that prevents dimerization and activation of the catalytic domains. This inactive conformation is stabilized by binding of SARM1's own substrate NAD+ in an allosteric location, away from the catalytic sites. This model was validated by mutagenesis of the allosteric site, which led to constitutively active SARM1. We propose that the reduction of cellular NAD+ concentration contributes to the disassembly of SARM1's peripheral ring, which allows formation of active NADase domain dimers, thereby further depleting NAD+ to cause an energetic catastrophe and cell death.

Graph Laplacian tomography from unknown random projections.

We introduce a graph Laplacian-based algorithm for the tomographic reconstruction of a planar object from its projections taken at random unknown directions. A Laplace-type operator is constructed on the data set of projections, and the eigenvectors of this operator reveal the projection orientations. The algorithm is shown to successfully reconstruct the Shepp-Logan phantom from its noisy projections. Such a reconstruction algorithm is desirable for the structuring of certain biological proteins using cryo-electron microscopy.

Steerable Principal Components for Space-Frequency Localized Images.

As modern scientific image datasets typically consist of a large number of images of high resolution, devising methods for their accurate and efficient processing is a central research task. In this paper, we consider the problem of obtaining the steerable principal components of a dataset, a procedure termed "steerable PCA" (steerable principal component analysis). The output of the procedure is the set of orthonormal basis functions which best approximate the images in the dataset and all of their planar rotations. To derive such basis functions, we first expand the images in an appropriate basis, for which the steerable PCA reduces to the eigen-decomposition of a block-diagonal matrix. If we assume that the images are well localized in space and frequency, then such an appropriate basis is the prolate spheroidal wave functions (PSWFs). We derive a fast method for computing the PSWFs expansion coefficients from the images' equally spaced samples, via a specialized quadrature integration scheme, and show that the number of required quadrature nodes is similar to the number of pixels in each image. We then establish that our PSWF-based steerable PCA is both faster and more accurate then existing methods, and more importantly, provides us with rigorous error bounds on the entire procedure.

A signal processing approach to symmetry detection.

We present an algorithm that detects rotational and reflectional symmetries of two-dimensional objects. Both symmetry types are effectively detected and analyzed using the angular correlation (AC), which measures the correlation between images in the angular direction. The AC is accurately computed using the pseudopolar Fourier transform, which rapidly computes the Fourier transform of an image on a near-polar grid. We prove that the AC of symmetric images is a periodic signal whose frequency is related to the order of the symmetry. This frequency is recovered via spectrum estimation, which is a proven technique in signal processing with a variety of efficient solutions. We also provide a novel approach for finding the center of symmetry and demonstrate the applicability of our scheme to the analysis of real images.

Fast Steerable Principal Component Analysis.

Cryo-electron microscopy nowadays often requires the analysis of hundreds of thousands of 2-D images as large as a few hundred pixels in each direction. Here, we introduce an algorithm that efficiently and accurately performs principal component analysis (PCA) for a large set of 2-D images, and, for each image, the set of its uniform rotations in the plane and their reflections. For a dataset consisting of n images of size L × L pixels, the computational complexity of our algorithm is O(nL3 + L4), while existing algorithms take O(nL4). The new algorithm computes the expansion coefficients of the images in a Fourier-Bessel basis efficiently using the nonuniform fast Fourier transform. We compare the accuracy and efficiency of the new algorithm with traditional PCA and existing algorithms for steerable PCA.

A Graph Partitioning Approach to Simultaneous Angular Reconstitution.

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

An Algorithm for Improving Non-Local Means Operators via Low-Rank Approximation.

We present a method for improving a non-local means (NLM) operator by computing its low-rank approximation. The low-rank operator is constructed by applying a filter to the spectrum of the original NLM operator. This results in an operator, which is less sensitive to noise while preserving important properties of the original operator. The method is efficiently implemented based on Chebyshev polynomials and is demonstrated on the application of natural images denoising. For this application, we provide a comparison of our method with other denoising methods.

The angular difference function and its application to image registration.

The estimation of large motions without prior knowledge is an important problem in image registration. In this paper, we present the angular difference function (ADF) and demonstrate its applicability to rotation estimation. The ADF of two functions is defined as the integral of their spectral difference along the radial direction. It is efficiently computed using the pseudopolar Fourier transform, which computes the discrete Fourier transform of an image on a near spherical grid. Unlike other Fourier-based registration schemes, the suggested approach does not require any interpolation. Thus, it is more accurate and significantly faster.

Viewing Direction Estimation in Cryo-EM Using Synchronization.

A central task in recovering the structure of a macromolecule from cryo-electron microscopy (cryo-EM) images is to determine a three-dimensional model of the macromolecule given many of its two-dimensional projection images. The direction from each image taken the images which was is unknown, and are small and extremely noisy. The goal is to determine the direction from which each image was taken and then to combine the images into a three-dimensional model of the molecule. We present an algorithm for determining the viewing direction of all cryo-EM images at once, which is robust to high levels of noise. The algorithm is based on formulating the problem as a synchronization problem; that is, we estimate the relative spatial configuration of pairs of images and then estimate a global assignment of orientations that maximizes the number of satisfied pairwise relations. Information about the spatial relation between pairs of images is extracted from common lines between triplets of images. These noisy pairwise relations are combined into a single consistent assignment of orientations by constructing a matrix whose entries encode the pairwise relations. This matrix is shown to have rank 3, and its nontrivial eigenspace is shown to reveal the projection orientation of each image. In particular, we show that the nontrivial eigenvectors encode the rotation matrix that corresponds to each image.

CT reconstruction from parallel and fan-beam projections by a 2-D discrete Radon transform.

The discrete Radon transform (DRT) was defined by Abervuch as an analog of the continuous Radon transform for discrete data. Both the DRT and its inverse are computable in O(n(2) log n) operations for images of size n × n. In this paper, we demonstrate the applicability of the inverse DRT for the reconstruction of a 2-D object from its continuous projections. The DRT and its inverse are shown to model accurately the continuum as the number of samples increases. Numerical results for the reconstruction from parallel projections are presented. We also show that the inverse DRT can be used for reconstruction from fan-beam projections with equispaced detectors.