Viewing Direction Estimation in Cryo-EM Using Synchronization.

6.2.

Experimental data

A set of 1500 class averages of the 50S subunit of the E. coli ribosome was used to test the algorithm on experimental data. This data set is the same data set used in [ 16 ]. The 1500 class averages were generated from a set of 27121 particle images, which were classified using the MSA function of the IMAGIC software package [ 19 , 22 ] into 1500 classes. Each class average in the data set is of size 90 × 90 pixels. The raw images used to generate the class averages were phase-flipped to remove the phase-reversals in the contrast transfer function (CTF) and were bandpass filtered at 1/150 Å and 1/8.4 Å. They were also normalized and translationally aligned with the rotationally averaged total sum. Unlike the simulated projections from section 6.1, the resulting class averages are affected by the CTF of the microscope, are contaminated by non-Gaussian noise, and contain unknown two-dimensional shifts. These factors make the detection of common lines much more difficult and also introduce artifacts to the resulting reconstruction. However, the most severe problem with class averages generated from experimental data is that they do not necessarily correspond to actual projections of the molecule. Ideally, when generating class averages, the class averaging algorithm finds projections that correspond to exactly the same viewing direction, aligns them rotationally and translationally, and averages them. This results in an actual projection of the molecule at improved SNR. In practice, due to the high levels of noise, many times the class averaging algorithm incorrectly identifies completely different images as corresponding to the same viewing direction. The resulting class average thus consists of projections that correspond to completely different viewing directions, and therefore it does not correspond to any actual projection of the molecule. As a result, a set of class averages generated from experimental data is likely to contain some class averages which are inconsistent with the others, in the sense that they have no common lines with the other class averages. A weakness of the synchronization algorithm, as presented in this paper, is that it requires one to estimate the block S ij for each pair of images i and j (see (4.15) ). Thus, even if some of the class averages do not represent any actual projection of the molecule and are therefore inconsistent as explained above, the algorithm still tries to find the rotation matrices corresponding to these images, although no such rotations exist. This necessarily affects all other estimated rotations, introducing large errors in the estimation. Hence, before processing experimental class averages with the synchronization algorithm, we need to discard from the data set images that are unlikely to correspond to actual projections of the molecule. Although algorithms for that task are important in themselves, here we just want to demonstrate that the synchronization algorithm is relevant in the case of experimental class averages, and so we apply the following heuristic. We take the 1500 class averages and use the synchronization algorithm to estimate their rotations, denoted R 1 , . . . , R 1500 . Then, for each pair of common lines c ij and c ji , we compute the angle between R i c ij and R j c ji . Ideally, this angle should be zero. For each projection, we count the number of times this angle was above 20 degrees (this threshold was chosen arbitrarily, and its precise value was found to hardly affect the outcome). This counts the number of times the projection was inconsistent with the rest of the projections. Then we find the 100 projections with the largest number of inconsistencies and discard them from our data set. We repeat this process until we are left with only 500 class averages, which we use as an input to the synchronization algorithm. Four projections from this data set are shown in Figure 9 . We take the set of 500 class averages and apply to them the synchronization algorithm. Figure 10(a) shows the 10 largest eigenvalues of the matrix S . To see if the estimated rotations respect the common lines we have detected, we compute for each pair of common lines c ij and c ji the angle between R i c ij and R j c ji (as was done during the projections’ filtration process explained above). This gives the embedding error for the pair c ij and c ji . Figure 10(b) shows the histogram of the embedding errors (in degrees). We see that many of the errors are small, but there is a long tail of large errors. We postulate that common lines with large embedding errors correspond to misidentified common lines. We thus discard common lines whose embedding errors are larger than 20 degrees and run the synchronization algorithm again. Figures 11(a) and 11(b) show the spectrum of the synchronization matrix and the histogram of embedding errors, respectively, at the end of this run. As we see in Figure 11(b) , the embedding errors have been significantly reduced. Next, we use the common lines to estimate the two-dimensional shift in each projection as described in [ 18 ]. Finally, we take the 500 estimated rotations together with the 500 appropriately reshifted class averages and reconstruct a three-dimensional density map. A two-dimensional rendering of the reconstructed volume is shown in Figure 12 . Based on our tests with simulated data and following the results in Figure 8 , we speculate that the errors in the reconstruction of the density map are attributed mainly to the effects of the CTF as well as to errors in recentering the projections.