A Representation Theory Perspective on Simultaneous Alignment and Classification

Abstract

Single particle cryo-electron microscopy (EM) is a method for determining the 3-D structure of macromolecules from many noisy 2-D projection images of individual macromolecules whose orientations and positions are random and unknown. The problem of orientation assignment for the images motivated work on general multireference alignment. The recently introduced non-unique games framework provides a representation theoretic approach to alignment over compact groups, and offers a convex relaxation which is formulated as semidefinite programs with certificates of global optimality under certain circumstances. One of the great opportunities in cryo-EM is studying heterogeneous samples, containing two or more distinct classes or conformations of molecules. Taking advantage of this opportunity presents an algorithmic challenge: determining both the class and orientation of each particle. We generalize multireference alignment to a problem of alignment and classification, and we propose to extend non-unique games to the problem of simultaneous alignment and classification with the goal of simultaneously classifying cryo-EM images and aligning them within their respective classes.

Keywords: SDP; alignment; classification; cryo-em; graph-cut; heterogeneity; heterogeneous multireference alignment; rotation group; synchronization.

Figure 1:

Left: two raw experimental images of TRPV1, available via EMDB 5778 [21]. Right: computed projections of TRPV1 which are the closest to the images on their left.

Figure 2:

Common Lines in cryo-EM. The left most images $I_i$ and $I_j$ are examples of projections of a molecule density $𝒳$; each projection is obtained from a different direction. At the center, are the Fourier transforms ${\hat{I}}_i$ and ${\hat{I}}_j$ of those images, overlaid with radial lines. The lower right sub-figure is a visualization of the two slices of the 3-D Fourier transform of the 3-D density $𝒳$, corresponding to ${\hat{I}}_i$ and ${\hat{I}}_j$; the two slices intersect each other, so that there is a line in ${\hat{I}}_i$ that is identical to a line in ${\hat{I}}_j$ (assuming no noise). Indeed, the point $\left(x_{ij},y_{ij}\right)$ which lies along this common line in ${\hat{I}}_i$ is identical to the point $\left(x_{ji},y_{ji}\right)$ which lies along this common line in ${\hat{I}}_j$. A more detailed discussion of common lines is available, for example, in [8, 9, 10, 11]

Figure 3:

Classical (left) and hybrid (right) states of 70S E. Coli ribosome (image source: [27]).

Figure 4:

Shifted copies of a function over SO(2)

Figure 5:

Noisy shifted copies of a function over SO(2)

Figure 6:

Loss function for alignment of signals

Figure 7:

Classification and alignment over SO(2)

Figure 8:

Graph cut and label ambiguity. A graph and equivalent Max-3-cuts, where only the label assigned to each class is changed, without changing the cut.

Figure 9:

Classification error vs. noise level, 4 balanced clusters