Non-uniform inclusion potential cross-correlation score (NCCS).

Let 𝓟_s be a chosen subset of atoms of 𝓟, and let X_s be the union of spheres of the atoms of 𝓟_s. Then (2)

Similarly, let m ∈ ℝ be a chosen scalar intensity value. Then (3)

For these definitions of A_nu and B_nu, a reasonable definition for 𝓟_s is the set of backbone atoms of the 3D EM map, while m can be defined, following [13], as that intensity that results in an isocontour enclosing a volume equal to the volume enclosed by the molecular surface of 𝓟. Note that the envelope score in [13] is a uniform-grid-based version of the non-uniform inclusion potential CCS (hereafter the NCCS).

Gaussian cross-correlation score (GCCS).

A classical and widely-used way to represent the protein 𝓟 is by Gaussian blurring, in which Gaussians (4)

corresponding to atom centers x_i and radii r_i, are summed at each grid point x; the parameter β > 0 describes the width of the Gaussian at medium height, R is the resolution of the target 3D EM map [32], and (5)

A Gaussian blur is thus a representation that reproduces the electrostatic potential of an atom at points very close to it. This formulation indirectly includes atomic masses by modulating the decay of the Gaussian kernel based on the radii of the atoms.

Scattering potential cross-correlation score (SCCS).

An elastic scattering model of the electrostatic potential uses five parameters for each atom, thus yielding a more realistic reconstruction of the electrostatic potential. According to the elastic scattering model [33], the potential at each grid point x due to an atom at x_i is given by a sum of five Gaussians (6) and (7)

where 2πℏ = h is the Planck constant, m₀ and e are respectively the mass of and charge on the electron, a_j and b_j are empirical parameters [34] that depend on the element type of atom i, and R is the desired resolution of the representation A of the atomic structure 𝓟. Note the functions B_gc and B_sc are identical to the input cryo-EM density map 𝓜 or a suitably filtered version of 𝓜.

The scattering potential is well-known [35, 36]; and has been used for fitting of high- resolution structures to cryo-EM maps in conjunction with constrained geometric simulations [37] or molecular dynamics simulations [38]. The primary motivation behind implementing the scattering potential in PF² fit is to explore its value as an alternative to Gaussian blurring since EM reconstruction is based on phase shifts and phase contrast caused by the electrostatic potential. As we show in the Results section), there occur cases, in both acquired and synthesized density map fitting, in which the scattering CCS (hereafter the SCCS) performs better than Gaussian CCS (hereafter the GCCS).

Complementary space cross-correlation score (CCCS).

Existing work on rigid-body fitting focuses on representing and correlating the volumes V_𝓟 and V_𝓜 occupied by 𝓟 and 𝓜 respectively. We introduce an addition to the fitting score, the complementary space cross-correlation score (CCCS), that uses the volumes complementary to V_𝓟 and V_𝓜 respectively. We define the complementary volumes as follows.

Let V_𝓟 be the primal volume occupied by the Gaussian molecular surface of 𝓟, and V_𝓜 ⊂ R³ is the volume occupied by a suitably chosen molecular surface of 𝓜. Then the complementary volumes and , are extracted from respective pocket functions [39] that use outward and backward propagation from the primal volumes. Note that, we also use pocket and complementary space interchangeably in the rest of the article.

Given these representations, we can assign A_pp and B_pp in Eq (1) as follows: (8) (9)

Combining the affinity functions.

All the affinity functions we introduced will result in a high positive real CCS for large overlaps between target-target or complementary-complementary volumes. One can, in principle, combine all the scoring terms by taking a weighted linear combination where the weights can be either user-specified or optimized by well-known machine learning techniques [40–44]. However, we note that the first three affinity functions represent and the same quantity of interest in slightly different ways and a combination of the three may be redundant. The complementary space score, however, captures a different aspect and should be used in conjunction with any of the first three. Hence, in this work, we compare the predictive performace and speed for each of target-target scores independently and in conjunction with the complementary space score.

Expected advantages of the non-uniform FFT-amenable affinity functions.

Classical, uniform FFT-based approaches require that affinity functions describing atomic structures or features are mapped onto a uniform grid. This mapping results in either (A) a grid-size much smaller than the average distance between atomic centers, and a resulting increase in time spent on redundant or uninteresting points far from the actual centre of the protein, or, (B) a grid-size much larger than the average distance between atomic centers, resulting in the opposite effect.

By contrast, a feature common to all the affinity functions in PF² fit is that they are grid-free, i.e., they do not necessarily require affinity functions to be computed on a uniform grid. This not only mitigates the disadvantage above but leads to ability to perform searches focused to a particular region. The Results section details this advantage of PF² fit.

Multi-basis framework.

PFcorr uses a framework in which scalar-valued functions A : ℝ³ ↦ ℂ are expressed in terms of basis-expansion coefficients . Let u = (θ, ϕ), θ ∈ [0, π], ϕ ∈ [0, 2π], and r ∈ ℝ⁺. A scalar valued function A(r, u):ℝ⁺ × 𝕊² → ℂ can be expanded as (10) where and are the radial and spherical basis functions respectively, and L is a finite expansion degree. We choose weighted Laguerre radial-basis functions for (see [29, 45] for the exact form of these functions), whereas are the well-known spherical harmonic functions.

PFcorr can also discard the radial-basis functions, following [3], and express each spherical slice A_r(u) in terms of the spherical harmonic basis coefficients : (11)

PFcorr, and hence the algorithm package PF² fit, thus support a multi-basis framework, in which a user can choose between either of the two most commonly used bases for rotational speedups. While convenient, the multi-basis framework is not central to our search scheme, and in the interests of brevity, we restrict our discussions below to situations in which the more general mixed bases are used.

All of our algorithms extend in a straightforward, if non-trivial way, to cases where the radial basis function is absent and Eq (11) instead of Eq (10) is evaluated at a chosen set of fixed radii r, as it is the case in [19] and even [7] where Eq (11) is evaluated for only one fixed r.

Rotational and Rigid-body Correlations; Non-Uniform SO(3) Fourier Transforms.

Let A(x) and B(x) be two scalar valued functions with basis coefficients and respectively. We are interested in the pure rotational correlation (12) and the rigid-body correlation (13)

where (R^A,R^B, z) is the factorization of the rigid-body transformation (R, t) into rotations of A and B and a single translation of A along the z-axis [29]. The effect of rotation is described by the Wigner-D functions that are a set of basis functions for L²(SO(3)). The effect of this translation is described by a translation tensor T(z) with elements , cf. [46].

This factorization of a motion into five rotational degrees of freedon and one remaining translational degree has been used in the field of protein matching by [19, 47] before. However, here it will be applied in a uniform setting and a fast evaluation algorithm for the first time.

PFcorr [29] provides a pair of recipes to compute each of the above sums. The technical content of these recipes can be found in our work on non-uniform multi-dimensional correlations [29]. For the purposes of this work, the most relevant fact is its use of the non-uniform fast SO(3) Fourier transform (NFSOFT) [21]: (14)

where are the input SO(3) Fourier coefficients of f ∈ L²(SO(3)). The Wigner-D functions form a orthogonal basis of L²(SO(3)), and i indexes N_R non-uniformly spaced z-y-z Euler Angles in SO(3).

This is a significant improvement over existing fitting tools. Due to the limitations of the uniform-FFT techniques that underly them, all current rotationally efficient methods [3, 7, 47] depend on a uniform discretization of Euler angular space. Unfortunately, because the space of Euler angles is a non-linear parametrization of the target space of rotations SO(3), this leads to a highly non-uniform set of samples in SO(3).

The expansion degree L embodies an aspect of the speed-accuracy tradeoff: higher degrees result in a greater ability to capture shape information in the 3D EM map, while causing an obvious degradation in performance. We find that setting L anywhere between 20 and 30 suffices for 3D EM map fitting exercises. The NFSOFT can be used to compute the above sum in 𝓞(L³logL + N_R) steps, in contrast to the generally far slower naive 𝓞(L³ N_R) approach.

Adapting PFcorr for Fitting.

We can see that the above recipes can be conveniently incorporated into a fitting search algorithm. As a preprocessing step, we compute the basis-expansion coefficients and of A(x) and B(x) respectively. Then based on the two recipes, one can choose either of the following search schemes.

1. Search choice 1: PF² fit—SE(3): Compute Eq (13) in 𝓞((L⁶ + L⁴ N_R^B + N_R^B N_R^A)T) steps over appropriate sample sets {R^A}, {R^B}, and {dz} where N_R^B and N_R^A are respectively the sizes of the sample sets {R^A} and {R^B}.
2. Search choice 2: PF² fit —SO(3). For each t over a set of samples in ℝ³, translate A by t and recompute ; then compute Eq (12) in 𝓞(L⁴) steps over a set of samples in SO(3).

While PF² fit —SE(3) can be used along with any sampling technique, we use the sets {R^A}, {R^B}, along with equispaced grid values for {dz} for the first fitting stage in order to avoid overseeing important regions of motions while oversampling others. This low dispersion and low discrepancy sampling of SO(3) [24, 29] is highly advantageous in the first stage of fitting as explained in the next paragraph.

PF² fit —SO(3) maximizes rotational scanning at the expense of translational scanning, an approach also adopted in [19] and [3]. Note that both these methods use a framework that excludes the radial basis function , e.g. due to the consideration of star-shaped molecules and discretizations of the radial parts respectively.

Expected advantages of the non-uniform SO(3) FFT-based search.

Like the NFSOFT, PF² fit scales gracefully under non-uniform discretizations of the space of z-y-z Euler Angles. This is a significant improvement over existing fitting tools [3, 7, 47] that depend on a uniform discretization of Euler angular space. Hence, for a given angular step size, these methods will always generate sample sets in SO(3) that examine parts of that space very finely while leaving others undiscovered. By contrast, an advantage of PF² fit is its ability to work efficiently with an arbitrary set of samples in Euler angular space, using a sampling technique such as in [24]. This is the primary advantage of PF² fit as a search algorithm. The consequences of this advantage extend naturally to all results obtained by PF² fit.

Skeleton-secondary structure score.

We introduce a reranking score that depends on the detection of secondary structural features from 𝓜. This has been a vigorous area of research in the past decade; for a recent review, see, for instance [48]. We use the skeletonization technique in [20, 48] to detect secondary structures from 𝓜, and the publicly available Stride [49] to detect the secondary structures of 𝓟. Let 𝓗_𝓜 and 𝓗_𝓟 respectively be the set of helices detected from 𝓜 and 𝓟. Each helix consists of an axis r, with ‖r‖_ℓ2 = 1, and a midpoint p. Let be a helix in 𝓗_𝓜, and let be a helix in 𝓗_𝓟. Let d(.,.) be the Euclidean distance function, ⟨.,.⟩ be the dot product, and w₁ ∈ ℝ⁻, w₂ ∈ ℝ⁺ be respectively negative and positive weights. Then the per-helix score and the secondary structural score are respectively given by (15) (16)

In this work, we set w₁ = −1, w₂ = 1, in which case the theoretical range of the per-helix score is (−∞,1]. The best possible per-helix score corresponds to the situation where the helices are perfectly aligned and have the same mid point, and . In most practical scenarios, is typically between 0.25 and 0.7.

Mutual information score.

The second reranking function we use is the mutual information score (see, for instance, [13, 30]), given by (17)

where p(x) and p(y) are the percentage of voxels in B and A that take on intensities equal to x and y respectively and p(x, y) is the percentage of voxels in B with intensity x that are aligned with voxels in A with intensity y. In PF² fit, A and B correspond respectively to the target volumes V_𝓟 and V_𝓜 respectively, with the former computed by the Gaussian blurring scheme.

Expected advantages of the reranking scheme.

The reranking stage serves two purposes. The first is to identify spurious results. Any fitting method that depends purely on a set of correlation-amenable affinity functions has the potential to yield high-scoring results that are nevertheless obviously incorrect. The second, related, goal of the reranking stage is to bring the process of rigid-body fitting closer to automation. We see fitting as a single stage in the elucidation of structure from biological data. The elucidation process comprises several data processing stages, and it is critical that the output of each stage is as accurate as it can be. One very popular way to measure the accuracy of a fitting algorithm is to perform a simple visual check; however, it may be time-consuming or otherwise impractical to visually check every single fitting pose generated by an automated fitting algorithm such as the one presented here. In these situations, the reranking procedure will either provide additional guarantees that the top result is in fact the one that fits the best, or will flag results whose scores do not agree about the quality of the fit.

Dataset.

For experiments involving synthesized 3D EM maps, we used a variety of atomic structures from the PDB. Many of these atomic structures overlap with those in the docking benchmark [50]; they were chosen mainly for their diversity in size and shape (average TM-score [51] between the structures is 0.27165, which indicates very low structural similarity). The PDB IDs of the 53 atomic structures we used are: 1QG4a, 1OUNab, 1D6Oa, 1IASa, 2TGT, 1K9Ba, 1MH1, 1HH8a, 1FPZf, 1B39a, 2CGAb, 1EGL, 1AY1hl, 1CMWa, 1BJ1hl, 2VPFgh, 1A6Zab, 1C68ab, 1GJRa, 1CZPa, 1TNDc, 1FQIa, 1FGNlh, 1TFHa, 1HCL, 1DKSa, 1GJRa, 1CZPa, 2CLRde, 1CD8ab, 1FSKbc, 1BV1, 1IJJb, 3DNI, 1BVLba, 3LZT, 9RSAb, 2BNH, 1TRMa, 1ECZab, 1FSKbc, 1BV1, 1E1Na, 1CJEd, 4PEP, 1F32a, 1BDD, 1FC1ab, 1QHDa, 1OELg, 1AONa, 1CTS, 2CTS and 1Q3Qa. We generated synthesized 3D EM maps for each model 𝓟 of this benchmark, by first blurring it at a fixed resolution R to produce a synthesized map B which mimics an EM; and then a random transformation is applied to the original model 𝓟 to generate 𝓟′. Now, the task is to find the best fit between 𝓟′ and the map B.

For acquired 3D EM map experiments, we used a selection of datasets from the CryoEM Challenge [20]. The resolutions for these cryoEM 3D EM maps range between 3.8Å to 20Å and is hence lower than for the synthesized data.

Experiments.

We performed the following experiments to validate PF² fit. Each of the experiments inherently validates the search scheme introduced in this work. Additionally, they validate, compare and highlight aspects of one or more of our affinity functions and scores.

• Validating different scoring terms using synthesized 3D EM map and comparison with other software. We applied our PF² fit—SE(3) and PF² fit—SO(3) algorithms using each of our target-target scores GCCS, NCCS and SCCS, independently, to predict the orientation of 𝓟′ that produces a good fit to B. Examples of this experiment are visualized in Figs 3 and 4.
  We repeated the experiments with the complementary scoring term (CCCS) added in and compared our obtained results to the results reported in [3] on similar experiments carried out with colores [18] and ADP_EM [3]. We also compared the performance of PF² fit with other software in fitting electron microscope acquired data for subunit-subunit and subunit-assembly cases. Details are presented in the Discussions Section. See also [20].
• Analyzing resolution robustness of scoring and search using synthesized 3D EM maps. In reality, the EM maps come in many different resolutions. To verify that our scoring models and search scheme preserves their applicability across a wide range of resolutions, while making fitting predictions with high accuracies, we progressively coarsened the resolution R of the target blurred 3D EM map B, and repeated the above experiments for each level of coarsening. Finally, the experiments were repeated with random Gaussian additive noise added to B.
• Analyzing the effect of reranking using synthesized 3D EM map. To measure the efficacy of the reranking metrics, we examined the 53 PDBs in our synthesized dataset with resolutions between 5 and 15Å, with a step size of two, thus conducting 318 fitting experiments.
• Analyzing the effect of various samplings using synthesized 3D EM map. To evaluate the speed-vs-accuracy tradeoff for PF² fit, we applied PF² fit on the synthesized dataset while varying the density of the sampling of SO(3) used in the search. For each of the structures, we used 1854, 4392, 8580, 14868, 29025, 68760, and 232020 samples on SO(3) corresponding to, respectively, rotational separations of 20, 15, 12, 10, 8, 6 and 4 degrees between samples. Additionally for the NCCS, we ran the same experiments while varying the expansion degree (L).
• Performance on acquired 3D EM map Fitting. We applied PF² fit to acquired cryoEM data, which is more challenging than synthesized map fitting since it may contain non-random noise, differences in conformations of the molecule, and possibly more than one molecule in a complex. We performed three types of fitting with acquired EM maps. First, we used PF² fit —SE(3) and—SO(3) to fit PDB subunits to subunits segmented from the 3D EM map (subunit-subunit). Segmentation was performed using the methods reported in [52, 53]. Second, we used PF² fit —SE(3) to fit a single PDB subunit into a larger 3D EM map (subunit-assembly). And third, we used PF² fit —SE(3) to fit multiple PDB subunits into a larger 3D EM map.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 3. Comparison of PF² fit with other software in synthesized EM fitting at 3Å.

A molecule is fitted into the synthetically generated EM map B with resolution 3Å(transparent green). The top-ranked result 𝓟₁ (red/yellow) is compared to the original PDB molecule 𝓟 (blue). (A) Top-ranked result using PF² fit —SE(3) with 8° uniform rotational sampling and 0.5Å translational step size. RMSD ≈ 0.88Å. (B) Top-ranked result using the Colores package; the ‘nopowell’ option is turned on. RMSD ≈ 3.2Å. (C) Top-ranked result using Colores with default options. RMSD ≈ 2.3Å. The fitted PDB 𝓟₁ is in yellow. (D) Top-ranked result using the ADP_EM package, with bandwidth L = 25. RMSD ≈ 0.94Å.

https://doi.org/10.1371/journal.pcbi.1004289.g003

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 4. Comparison of PF² fit with other software in synthesized EM fitting at 10Å.

(A) The synthetically generated 3D EM map is a Gaussian blurred version of the PDB 7CAT (chains A and B), with resolution R = 10Å, and random noise added to obtain a signal-to-noise ratio of unity. The PDB 𝓟 (inset) is chain B of the same protein. The top-ranked result 𝓟₁ (red/yellow) is compared to the original PDB molecule 𝓟 (blue). (B) Top-ranked result using PF² fit —SE(3) with 8° uniform rotational sampling and 0.5Å translational step size has RMSD = 0.73Å. (C) Top-ranked result using Colores with default options has RMSD = 1.096Å. (D) Top-ranked result using the ADP_EM package, with bandwidth L = 25 has RMSD = 0.814Å.

https://doi.org/10.1371/journal.pcbi.1004289.g004

Validation Metrics.

For the experiments involving synthesized maps, the true position or true fitting is simply the original position of the PDB model 𝓟. After a randomly oriented copy 𝓟′ of the model is fitted using PF² fit, it produces a new position and orientation, 𝓟′′. For perfectly accurate fitting, 𝓟′′ should perfectly coincide with 𝓟. We simply compute the root mean square distance (RMSD) based on the positions of the atoms in 𝓟′′ and 𝓟, as a measure of the accuracy such that lower RMSD indicates a better fitting prediction.

For both synthesized and acquired EM maps, we additionally use the external total ratio (ETR) as a metric of fitting quality. ETR is the ratio of the number of atoms outside a suitably picked isocontour of the 3D EM map to the total number of atoms in the PDB. We term this score the external-total ratio (ETR) [20]. ETR is a very subjective measure as it depends on the choice of the isocontour and hence should only be used when a better metric (e.g. RMSD) cannot be computed.

Finally, as a measure of the confidence on the prediction, we use Z-score. The Z-score [54] of a fitting result is given by , where x is the score of the fitting result, and μ and σ are respectively the average and the standard deviation of the population. The Z-score measures the degree to which a scoring function can discriminate between two different candidate solutions, with higher scores indicating better discriminatory ability.

On synthetized EM data.

We compare the GCCS with the SCCS in Table 1, Figs 5 and 6. When compared to the GCCS, the SCCS produced results with lower RMSD for the same resolution, both in the presence and the absence of noise, cf. Figs 5 and 6. However, the average rank of the of the best RMSD result might be lower for SCCS than GCCS as can be seen in Table 1.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Table 1. Average rank, rounded to the nearest integer, of best RMSD result returned by PF² fit —SE(3) in the initial search stage for synthetic maps at different resolutions.

The figure in brackets in the second and third columns denotes the rank in the presence of noise at SNR = 1. See the section on “Datasets” for a list of PDBs used in this experiment. Note that even if the rank of the best RMSD is lower for SCCS in some cases, the actual RMSDs are generally lower, cf. Figs 5 and 6.

https://doi.org/10.1371/journal.pcbi.1004289.t001

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 5. Resolution robustness and comparison of scattering potential (SCCS) and Gaussian (GCCS) scores for synthesized data.

We plot the RMSD of the top-ranked result as a function of the resolution of the EM map used for the fit. See the section titled “Dataset” for a list of PDBs used in this experiment. (A) Average resolution-dependent RMSD of the top-ranked result returned by PF² fit —SE(3) in the absence and presence of noise for the GCCS and the SCCS. (B) Average Z-Score for the ten top results in the absence of noise. Z-Scores in the presence of noise follow the same trend.

https://doi.org/10.1371/journal.pcbi.1004289.g005

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 6. Effect of complementary space scoring for synthesized data.

Using the complementary space scores from (A) Eq (8) and (B) Eq (9), with w_comp = 1, w_target = 1 we plot the RMSD as a function of the resolution of the EM map. See the section titled “Dataset” for a list of PDBs used in this experiment.

https://doi.org/10.1371/journal.pcbi.1004289.g006

Another illuminating trend is the slope of each of the curves in Fig 5, which reveals that results returned by the GCCS degrade more sharply than those from the SCCS. Note that both the GCCS and the SCCS yielded better RMSDs on average than ADP_EM (see [3], Fig 1), yielding on average lower RMSD results at the same synthesized EM resolution.

Table 1 gives the the average rank of the best RMSD result returned by PF² fit —SE(3).

On acquired EM data from the cryoEM challenge.

We also compared results obtained from acquired cryo-EM 3D EM map fitting (Experiment 3) using both the GCCS and SCCS. In this experiment, the RMSD cannot be measured, as there is no atomic structure corresponding to 𝓜. Instead, we use the number of atoms excluded outside a given iso-contoured molecular surface to compare the performances of the rival CC scores. The results, in Table 2, show that for fitting with acquired 3D EM maps, the SC yielded on average results that exclude 2–4 fewer residues than the GCCS. This is in keeping with the expectation that the SCCS is closer to acquired 3D EM map reconstructions than the GCCS, and is thus able to yield a better correlation in situations where such 3D EM maps are involved.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Table 2. Results of applying PF² fit —SE(3) on a selection of datasets from the cryoEM modeling challenge (Experiment 3) using both the GCCS and SCCS.

An error measure similar to ETR is provided as the number of residues excluded outside a given iso-contoured molecular surface. The SCCS yielded on average results that exclude 2–4 fewer residues than the GCCS.

https://doi.org/10.1371/journal.pcbi.1004289.t002

Put together, these observations imply that the SCCS is an effective alternative to the GCCS in microscope acquired density-map fitting scenarios, since it is a more realistic representation of a 3D EM map. This conclusion applies not just to the problem of rigid-body fitting, considered in this work, but to the harder problem of flexible fitting, where it is critical that the representation of 𝓟 be as close to the target 3D EM map as possible. We note that there is a tiny overhead in computing the SCCS relative to the GCCS due to the former being a sum of five Gaussians.

Fig 5 suggests that for lower resolutions (< 20Å), it might be sensible to use more resolution robust scoring functions like the cross-correlation score normalized with respect to mean value and standard deviation as proposed in [9]. These normalized scoring function could be used in a straightforward manner in our PF² fit software either as a preprocessing step for the EM maps or as an additional FFT-amenable scoring function.

On synthetized EM data.

We tested the described set of 53 models in our synthesized EM dataset for 6 different resolutions and then counted the instances in which the reranking replaced the top-ranked result of the initial stage with a previously lower ranked one, that has a better RMSD and is hence a better fit.

In Table 3, we report the average rank of the lowest RMSD prediction, after applying the reranker in absence and presence of noise dependend on the resolution. We see that MIS is more resolution robust than the SSS and both perform better at higher resolutions.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Table 3. Average rank of best RMSD result returned by PF² fit—SE(3) after reranking.

In the initial stage GCCS was used. The figures in brackets denote the rank in the presence of noise at SNR = 1. We see a strong decrease in rank for the skeleton-secondary structure score with and without noise while the mutual information score remains predictable across the range of resolutions. See the section on “Datasets” for a list of PDBs used to generate the synthetic maps used in this experiment. Note that even if the ranks of the best RMSD solution, on average across all experments, show no improvement over Table 1 (mostly because GCCS already does an excellent job of ranking them)- the ranks actually improved for several of the experiments (73/318 for MIS, and 5/318 for MIS). Please see Section ‘The performance of reranking increases with resolution’ for details.

https://doi.org/10.1371/journal.pcbi.1004289.t003

The MIS replaced the top-ranked result of the initial stage with one that has a better RMSD 73 times, predominantly at resolutions below 10Å. These cases occured for all the PDBs listed in the section on datasets, except 1BVLba, 1AY1hl and 2BNH.

On the other hand, we notice that the usefulness of the SSS degraded sharply with decreasing resolution. There were only five cases out of the 318 experiments in which the SSS replaced the top-ranked result with a result that has better RMSD; all of these cases occured at resolutions < 10Å, and for the PDBs 1FSKbc, 1BVLba, 1BDD, 2CTS and 1OELg. However, we expect the SSS to become a more effective gauge of fitting quality as the quality of density maps obtained from cryo-EM increases, and more density maps at resolutions between 3–5 Å are isolated.

On acquired EM data from the cryoEM challenge.

For finer resolution 3D EM maps, such the one corresponding to GroEL at 4.4Å, mm-cpn at 4.3Å, Rotavirus at 3.8Å, or GroEL at 7.7Å, SSS correlates with the MIS, as well as the FFT-amenable fitting metrics, about the quality of the fitted result, generating scores that range between 0.3 and 0.8 for the top ten fitting results. However, for 3D EM maps such as those of GroEL at 11Å or SIV at 20Å it diverges sharply from the MIS and the other measures introduced in this work, and yields results that are clearly, i.e., visually, incorrect, due simply to the quality of skeleton obtained.

We expect the SSS to become a more effective gauge of fitting quality as the quality of 3D EM maps obtained from cryo-EM increases, and more 3D EM maps at resolutions between 4–8Å are isolated.

Accuracy on synthetized data.

In Fig 5 we report the average RMSD of the top-ranked fitting predictions made by PF² fit over the set of 53 PDBs mentioned in the Validation and dataset section. As the PDBs were blurred, the accuracy (RMSD) of the prediction gradually got worse, as expected. We compared these to the plot in Fig 1 of [3], where performance of ADP_EM and Colores is reported in the same manner (i.e. RMSD vs. resolution) for a smaller dataset. According to the data reported in [3], the average RMSD of three variants of ADP_EM and Colores+Powell is above 1Å when the blurring is greater than 20Å, which is very similar to PF² fit using GCCS. However, PF² fit with SCCS achieved average RMSDs which are less than 1Å, even when the model is blurred upto 40Å, and is hence much more robust for fitting to low resolution maps. The lowest blurring resolution reported in [3] is 10Å. At that resolution, the approximate average errors for Colores+Powell, the best variant of ADP_EM, PF² fit with GCCS and PF² fit with SCCS are respectively 0.25, 0.7, 0.4 and 0.3 respectively, indicating that PF² fit performs comparatively well when better maps are available as well.

For PF² fit, the top-ranking or second-ranking pose was observed to be usually the one with the least RMSD (Fig 5). This feature should be common to all global-optimisation-based fitting routines in which atomic structures are rigidly fit to blurred versions of themselves. However, we observed in our experiments that while the top ranked fitting result in Colores is usually also the one with the least RMSD, the ones ranked 2–10 have RMSDs that can range anywhere between 1.1 and 10 times the RMSD of the top-ranked result. We surmise that this spuriousness is an artifact of its Powell maximization step.

An example of how PF² fit performs relative to Colores and ADP_EM [3] can be seen in Fig 3. This is an instance of Experiment 1 applied to a single chain atomic structure. The fitted result using PF² fit results in an RMSD of 0.88Å, the least of the three programs, while Colores and ADP_EM respectively return 3.2 and 0.94Å.

Another example, a variant of Experiment 1, can be seen in Fig 4. Here a random rigid-body transformation (R, t) is applied to a single chain 𝓟_a of a two-chain atomic structure 𝓟_ab. 𝓟_a is then fitted to a synthesized EM density map generated from 𝓟_ab to generate , using one of PF² fit, Colores, or ADP_EM. The RMSD between and 𝓟_ab is then measured. Fig 4 shows that PF² fit obtains an RMSD of 0.73Å, while ADP_EM and Colores obtain an RMSD, respectively, of 0.814Å and 1.096Å.

All in all, our experiments showed that PF² fit can be considered as a viable alternate with features and tradeoffs that complements those available in ADP_EM and Colores.

Performance on acquired EM data from the cryoEM challenge.

An example of acquired EM data subunit-assembly fitting is provided in Fig 8. Here a single subunit of an atomic structure is fit to a larger density map which contains three repetitions of the subunit. An ideal fitting routine should be able to rank each of the symmetric positions of the fitted atomic structure above all other hypothetical positions. While PF² fit and ADP_EM achieve this, Colores is unable to find one of the three symmetric positions in its top ten results. Additionally, PF² fit attains the lowest ETR of the three fitting routines. The ETRs for PF² fit, Colores, and ADP_EM are, respectively, 0.03, 0.1, and 0.8.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Fig 8. Comparison of PF² fit with other software in subunit-assembly fitting.

Fitting the PDB molecule 𝓟 (1GC1) to the EM map 𝓜 of SIV 20Å(EMD5020), using the GCCS. Two different views of the molecules are given: (A) Results from PF² fit. The ETR is 0.03. (B) Results from colores with default options. The ETR is 0.1. (C) Results from ADP_EM with L = 25. The ETR is 0.08.

https://doi.org/10.1371/journal.pcbi.1004289.g008

Timing.

As previously mentioned, the parameters in PF² fit were set up to yield comparable runtimes to ADP_EM [3] and Colores. An average PF² fit fitting exercise with L = 25 and angular sampling of 10° per rotational degree of freedom takes is around twice as much time as ADP_EM [3] with default settings, and less time than Colores (even when Powell optimization is not done). For example, fitting the Beef Liver Catalase (PDBID: 7CAT) on a single-threaded 2.5GhZ processor with 8 GB main memory takes about 2.5 minutes for PF² fit, 65 seconds for [3] (with the same value of L), and about 3.5 minutes for Colores. These reported times are averaged over 25 executions of each. Note that, for PF² fit most of the performance overhead is due to the non-uniform nature of the search algorithm, and in particular the NFFT.