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 (the Lie group of 3-dimensional rotations) out of a large set of molecular orientations. The problem may be reduced to clustering in modulo a finite group, and solved efficiently by “factoring” into a clustering on the unit circle followed by clustering on the 2-sphere , 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 . For each sampled orientation , the diffraction data is rotated by and correlated with the unrotated data. This signal defines a scalar field on rotation space, with peaks where the rotated data correlates with the unrotated data . Symmetries will cause these peaks, and hence the peaks can be used to infer the NCS. For example, in symmetry we will see rotation peaks around a common axis (vector), spaced 72 degrees apart. Here, denotes the correlation function, and rotating the data by .
The cross-rotation function is similar. The scalar field computed is instead , where is the simulated diffraction from a homology putative model. denotes the rotation of by (similar to ).
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 -fold NCS is selecting the 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 be a set of peaks, such that is a member in the rotation group of the 3-dimensional Euclidean space. CRANS first computes rotation differences ( represents the inverse of ). Then, the algorithm performs a subgroup search to find all subsets of peaks such that the rotation difference set is a subset of the special orthogonal group of three-dimensional rotations , and the rotations in 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 is the number of cross-rotation peaks, the NCS is -fold, and the number of NCS-consistent subgroups is ().
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 containing only five rotations. Orientations corresponding to rotations (purple), (green), and (blue) form an NCS-consistent rotation set . For clarity, only a few rotation differences ( , , and ) are shown in the upper right overlapping-orientation figure. The rotation differences, , 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 ( , , and ) are contained in the cross-rotation peak list . The missing rotation is computed using defined by the axis of the three identified NCS-consistent rotations and the missing angle. The now complete NCS-consistent rotation set has a complete rotation difference set , which satisfies the subgroup properties.
| Step | Worst Case | Expected |
|---|---|---|
| 1. Compute all rotation differences | ||
| 2. Cluster those differences the symmetry angles (filter) | ||
| 3. Cluster rotation sets sharing a common axis | ||
| 4. Patch missing | ||
| Total |
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.