Chapter 47Cross-Rotation Analysis Algorithm

Algorithms in structural biology and molecular biophysics are advancing our long-range goal of understanding biopolymer interactions in systems of significant biochemical as well as pharmacological interest. This chapter gives a particular example, an algorithm to analyze non-crystallographic symmetry in X-ray diffraction data of biopolymers, where one must “recognize” a finite subgroup of SO(3)SO(3) (the Lie group of 3-dimensional rotations) out of a large set of molecular orientations. The problem may be reduced to clustering in SO(3)SO(3) modulo a finite group, and solved efficiently by “factoring” into a clustering on the unit circle followed by clustering on the 2-sphere S2S^2 , plus some group-theoretic calculations. This yields a polynomial-time algorithm that is efficient in practice [2], and which recently enabled biological crystallographers to reveal the architecture of a parasite’s enzyme [6]. This will help researchers reduce the threat of certain diseases among those with weak immune systems. See chapter 17, section 17.6, for more details about this enzyme structure, and for a comparison of the rotation search algorithms in NMR (e.g., chapter 17, sections 17.2 and 17.3) and crystallography (this chapter and chapter 48).

More generally, many fascinating computational problems arise in the analysis of X-ray diffraction data. X-ray crystallography techniques (see section 40.1.1) yield high-resolution macromolecular structures of biomolecules, and therefore are very important to structural biologists. In this lecture, we introduce a quaternion-based algorithm to identify (and generate missing) cross-rotation peaks to model orientations consistent with proper noncrystallographic symmetry (NCS).

CRANS

Proper noncrystallographic symmetry (NCS) facilitates orienting and translating copies of the molecular-replacement (MR) model to use initial phases from an homologous model. Traditionally, the presence and degree of NCS is initially identified by a self-rotation function [4], while the orientations of each copy of the model are subsequently identified using the cross-rotation function [4].

The key observation behind MR using NCS is that symmetries in the protein structure yield symmetries in the data in the Fourier domain. This is because the operations of rotation and the Fourier transform commute.

The self-rotation function samples three-dimensional orientation space SO(3)SO(3) . For each sampled orientation q∈SO(3)q \in SO(3) , the diffraction data DD is rotated by qq and correlated with the unrotated data. This signal A(D,D(q))A(D, D(q)) defines a scalar field on rotation space, with peaks where the rotated data correlates with the unrotated data DD . Symmetries will cause these peaks, and hence the peaks can be used to infer the NCS. For example, in C5C_5 symmetry we will see rotation peaks around a common axis (vector), spaced 72 degrees apart. Here, AA denotes the correlation function, and D(q)D(q) rotating the data by qq .

The cross-rotation function is similar. The scalar field computed is instead A(D,H(q))A(D, H(q)) , where HH is the simulated diffraction from a homology putative model. H(q)H(q) denotes the rotation of HH by qq (similar to D(q)D(q)).

The term self-rotation encodes the notion that the data is correlated with itself (modulo rotation). The term cross-rotation encodes the notion that the correlation is “across” the raw data and the back-calculated structure factors, from a rotated putative homolog.

The correct peaks of the cross-rotation function should have rotation-function scores much higher than the incorrect ones, and they must be compatible with the NCS constraints. That is, they must correspond to the correct NCS-consistent orientations. Therefore, one method to identify the correct peaks of the cross-rotation function compatible with nn -fold NCS is selecting the nn peaks that have the highest rotation-function scores. However, if the model is partial [3], this method does not work well. Furthermore, it could be the case that some of the correct rotations are missing in the cross-rotation peak list. The CRANS (cross-rotation analysis) algorithm [2] was designed to overcome these problems. The advantage of CRANS is that it can identify the peaks that are consistent with the NCS constraints, and it can generate the missing peaks.

Methods

The key idea of CRANS is to identify a set of peaks (rotations) whose rotation differences are compatible with that of a point group with a single rotation axis. More precisely, let C={r1,…,rw}C = \{r_1, \dots, r_w\} be a set of ww peaks, such that rir_i is a member in the rotation group of the 3-dimensional Euclidean space. CRANS first computes w2w^2 rotation differences di,j=r−irjd_{i,j} = r^{-i} r^j (r−ir^{-i} represents the inverse of rir^i). Then, the algorithm performs a subgroup search to find all subsets of peaks RR such that the rotation difference set D(R)={r−irj:ri,rj∈R}D(R) = \{r^{-i} r^j : r^i, r^j \in R\} is a subset of the special orthogonal group of three-dimensional rotations SO(3)SO(3) , and the rotations in RR share a common axis. If some peaks are missing, CRANS then “completes” the partial set of identified NCS-consistent rotations by generating missing rotations using the group properties of quaternions [1, 5]. The algorithm is illustrated in figure 47.1 (plate 50).

Complexity

The time complexity of each step of CRANS is summarized in the following table, in which mm is the number of cross-rotation peaks, the NCS is nn -fold, and the number of NCS-consistent subgroups is gg (≪m\ll m).

Figure 47.1 (plate 50) Two-dimensional examples for threefold (a) and fourfold (b) NCS. (a) A model is shown with the results of a simplified cross-rotation search CC containing only five rotations. Orientations corresponding to rotations r1r_1 (purple), r3r_3 (green), and r4r_4 (blue) form an NCS-consistent rotation set RR . For clarity, only a few rotation differences ( d11d_{11} , d13d_{13} , and d14d_{14} ) are shown in the upper right overlapping-orientation figure. The rotation differences, D(R)D(R) , form a complete rotation difference set and satisfy the group properties of associativity (not shown), identity, inverse, and closure. (b) A fourfold NCS example is shown using similar notation to that in (a). In this example, only three of the four NCS-consistent rotations ( r1r_1 , r3r_3 , and r4r_4 ) are contained in the cross-rotation peak list CC . The missing rotation rα=d1αr1r_\alpha = d_{1\alpha}r_1 is computed using d1αd_{1\alpha} defined by the axis of the three identified NCS-consistent rotations and the missing angle. The now complete NCS-consistent rotation set RR has a complete rotation difference set D(R)D(R) , which satisfies the subgroup properties.

Step Worst Case Expected
1. Compute all rotation differences Δ={rs−1}\Delta = \{rs^{-1}\} O(m2)O(m^2)
2. Cluster those differences Δ=\Delta = the nn symmetry angles (filter) O(nm2)O(nm^2)
3. Cluster rotation Δ\Delta sets sharing a common axis O(m4)O(m^4) O(m2)O(m^2)
4. Patch missing O(g)O(g)
Total O(m4+g)O(m^4 + g) O(nm2+g)O(nm^2 + g)

Exercise Technically, the subgroup search should be called a coset search. Explain why.

References

  • [1] W. Hamilton. (1969). Elements of Quaternions, 3rd ed. New York: Chelsea Publishing Co.
  • [2] R. Lilien, C. Bailey-Kellogg, A. Anderson, and B. Donald. Acta Crystallographica D60 (2004):1057–1067.
  • [3] B.-H. Oh. (1995). Acta Crystallographica D51, 140–144.
  • [4] M. G. Rossmann, and D. M. Blow. Acta Crystallographica 15 (1962):24–31.
  • [5] E. Salamin. Applications of Quaternions to Computation with Rotations. Technical Report, Stanford University, AI Lab, Internal working paper, 1979.
  • [6] R. O’Neil, R. Lilien, B. Donald, R. Stroud, and A. Anderson. Phylogenetic classification of protozoa based on the structure of the linker domain in the bifunctional enzyme, dihydrofolate reductase-thymidylate synthase. Journal of Biological Chemistry 278 (2003):52980–52987.