Global crystallographic algorithms

Bricogne, G.

doi:10.1107/97809553602060000551

International
Tables for
Crystallography
Volume B
Reciprocal space
Edited by U. Shmueli

pdf | chapter contents | chapter index | related articles

International Tables for Crystallography (2006). Vol. B. ch. 1.3, pp. 82-84 | 1 | 2 |

Section 1.3.4.3.6. Global crystallographic algorithms

G. Bricogne^a

^a MRC Laboratory of Molecular Biology, Hills Road, Cambridge CB2 2QH, England, and LURE, Bâtiment 209D, Université Paris-Sud, 91405 Orsay, France

1.3.4.3.6. Global crystallographic algorithms

| top | pdf |

All the necessary ingredients are now available for calculating the CDFT for any given space group.

1.3.4.3.6.1. Triclinic groups

| top | pdf |

Space group P1 is dealt with by the methods of Section 1.3.4.3.5.1 and $[P\bar{1}]$ by those of Section 1.3.4.3.5.4.

1.3.4.3.6.2. Monoclinic groups

| top | pdf |

A general monoclinic transformation is of the form $[S_{g}: {\bf x} \;\longmapsto\; {\bf R}_{g} {\bf x} + {\bf t}_{g}]$ with $[{\bf R}_{g}]$ a diagonal matrix whose entries are [+1] or [-1] , and $[{\bf t}_{g}]$ a vector whose entries are 0 or $[{1 \over 2}]$ . We may thus decompose both real and reciprocal space into a direct sum of a subspace $[{\bb Z}^{n_{+}}]$ where $[{\bf R}_{g}]$ acts as the identity, and a subspace $[{\bb Z}^{n_{-}}]$ where $[{\bf R}_{g}]$ acts as minus the identity, with $[n_{+} + n_{-} = n = 3]$ . All usual entities may be correspondingly written as direct sums, for instance: $[\matrix{\eqalign{{\bf R}_{g} &= {\bf R}_{g}^{+} \oplus {\bf R}_{g}^{-},\cr {\bf t}_{g} &= {\bi t}_{g}^{+} \oplus {\bf t}_{g}^{-},\cr {\bf m} &= {\bf m}^{+} \oplus {\bf m}^{-}, \cr{\bf h} &= {\bf h}^{+} \oplus {\bf h}^{-},} &\eqalign{{\bf N} &= {\bf N}^{+} \oplus {\bf N}^{-}, \cr {\bf t}_{g}^{(1)} &= {\bf t}_{g}^{(1) +} \oplus {\bf t}_{g}^{(1) -},\cr {\bf m}_{1} &= {\bf m}_{1}^{+} \oplus {\bf m}_{1}^{-},\cr{\bf h}_{1} &= {\bf h}_{1}^{+} \oplus {\bf h}_{1}^{-}, } &\eqalign{{\bf M} &= {\bf M}^{+} \oplus {\bf M}^{-},\cr {\bf t}_{g}^{(2)} &= {\bf t}_{g}^{(2) +} \oplus {\bf t}_{g}^{(2) -},\cr {\bf m}_{2} &= {\bf m}_{2}^{+} \oplus {\bf m}_{2}^{-},\cr {\bf h}_{2} &= {\bf h}_{2}^{+} \oplus {\bf h}_{2}^{-}.}}]$

We will use factoring by 2, with decimation in frequency when computing structure factors, and decimation in time when computing electron densities; this corresponds to $[{\bf N} = {\bf N}_{1}{\bf N}_{2}]$ with $[{\bf N}_{1} = {\bf M}]$ , $[{\bf N}_{2} = 2{\bf I}]$ . The non-primitive translation vector $[{\bf Nt}_{g}]$ then belongs to $[{\bf M}{\bb Z}^{n}]$ , and thus $[{\bf t}_{g}^{(1)} = {\bf 0} \hbox{ mod } {\bf M}{\bb Z}^{n},\quad {\bf t}_{g}^{(2)} \in {\bb Z}^{n} / 2{\bb Z}^{n}.]$ The symmetry relations obeyed by $[\rho\llap{$-\!$}]$ and F are as follows: for electron densities $[\rho\llap{$-\!$} ({\bf m}^{+}, {\bf m}^{-}) = \rho\llap{$-\!$} ({\bf m}^{+} + {\bf N}^{+}{\bf t}_{g}^{+}, -{\bf m}^{-} - {\bf N}^{-}{\bf t}_{g}^{-})]$ or, after factoring by 2, $[\eqalign{ &\rho\llap{$-\!$} ({\bf m}_{1}^{+}, {\bf m}_{2}^{+}, {\bf m}_{1}^{-}, {\bf m}_{2}^{-}) \cr &\phantom{\rho\llap{$-\!$}} = \rho\llap{$-\!$} ({\bf m}_{1}^{+}, {\bf m}_{2}^{+} + {\bf t}_{g}^{(2) +}, {\bf M}^{-}{\boldzeta} ({\bf m}_{1}^{-}) - {\bf m}_{1}^{-} - {\bf m}_{2}^{-}, {\bf m}_{2}^{-} + {\bf t}_{g}^{(2) -})\hbox{;}}]$ while for structure factors $[F ({\bf h}^{+}, {\bf h}^{-}) = \exp [2 \pi i({\bf h}^{+} \cdot {\bf t}_{g}^{+} + {\bf h}^{-} \cdot {\bf t}_{g}^{-})] F ({\bf h}^{+}, -{\bf h}^{-})]$ with its Friedel counterpart $[F ({\bf h}^{+}, {\bf h}^{-}) = \exp [2 \pi i({\bf h}^{+} \cdot {\bf t}_{g}^{+} + {\bf h}^{-} \cdot {\bf t}_{g}^{-})] \overline{F (-{\bf h}^{+}, {\bf h}^{-})}]$ or, after factoring by 2, $[\eqalign{ F({\bf h}_{1}^{+}, {\bf h}_{2}^{+}, {\bf h}_{1}^{-}, {\bf h}_{2}^{-}) =\ &(-1)^{{\bf h}_{2}^{+} \cdot {\bf t}_{g}^{(2) +} + {\bf h}_{2}^{-} \cdot {\bf t}_{g}^{(2) -}}\cr &\times F({\bf h}_{1}^{+}, {\bf h}_{2}^{+}, {\bf M}^{-}{\boldzeta} ({\bf h}_{1}^{-}) - {\bf h}_{1}^{-} - {\bf h}_{2}^{-}, {\bf h}_{2}^{-})}]$ with Friedel counterpart $[\eqalign{&F({\bf h}_{1}^{+}, {\bf h}_{2}^{+}, {\bf h}_{1}^{-}, {\bf h}_{2}^{-})\cr &\quad= (-1)^{{\bf h}_{2}^{+} \cdot {\bf t}_{g}^{(2) +} + {\bf h}_{2}^{-} \cdot {\bf t}_{g}^{(2) -}} \overline{F [{\bf M}^{+}{\boldzeta} ({\bf h}_{1}^{+}) - {\bf h}_{1}^{+} - {\bf h}_{2}^{+}, {\bf h}_{2}^{+}, {\bf h}_{1}^{-}, {\bf h}_{2}^{-}].}}]$

When calculating electron densities, two methods may be used.

(i) Transform on $[{\bf h}^{-}]$ first.

The partial vectors defined by $[X_{{\bf h}^{+}, \, {\bf h}_{2}^{-}} = F({\bf h}^{+}, {\bf h}_{1}^{-}, {\bf h}_{2}^{-})]$ obey symmetry relations of the form $[X({\bf h}_{1}^{-} - {\bf h}_{2}^{-}) = \varepsilon X[{\bf M}^{-}{\boldzeta} ({\bf h}_{1}^{-}) - {\bf h}_{1}^{-}]]$ with $[\varepsilon = \pm 1]$ independent of $[{\bf h}_{1}^{-}]$ . This is the same relation as for the same parity class of data for a (complex or real) symmetric $[(\varepsilon = + 1)]$ or antisymmetric $[(\varepsilon = - 1)]$ transform. The same techniques can be used to decrease the number of $[F({\bf M}^{-})]$ by multiplexing pairs of such vectors and demultiplexing their transforms. Partial vectors with different values of ɛ may be mixed in this way (Section 1.3.4.3.5.6).

Once $[F({\bf N}^{-})]$ is completed, its results have Hermitian symmetry with respect to $[{\bf h}^{+}]$ , and the methods of Section 1.3.4.3.5.1 may be used to obtain the unique electron densities.
(ii) Transform on $[{\bf h}^{+}]$ first.

The partial vectors defined by $[X_{{\bf h}^{-}, \, {\bf h}_{2}^{+}} = F({\bf h}_{1}^{+}, {\bf h}_{2}^{+}, {\bf h}^{-})]$ obey symmetry relations of the form $[X({\bf h}_{1}^{+} - {\bf h}_{2}^{+}) = \overline{\varepsilon X[{\bf M}^{+}{\boldzeta} ({\bf h}_{1}^{+}) - {\bf h}_{1}^{+}]}]$ with $[\varepsilon = \pm 1]$ independent of $[{\bf h}_{1}^{+}]$ . This is the same relation as for the same parity class of data for a Hermitian symmetric $[(\varepsilon = + 1)]$ or antisymmetric $[(\varepsilon = - 1)]$ transform. The same techniques may be used to decrease the number of $[F({\bf M}^{+})]$ . This generalizes the procedure described by Ten Eyck (1973) for treating dyad axes, i.e. for the case $[n_{+} = 1, {\bf t}_{g}^{(2) -} = {\bf 0}]$ , and $[{\bf t}_{g}^{(2) +} = {\bf 0}]$ (simple dyad) or $[{\bf t}_{g}^{(2) +} {\ne {\bf 0}}]$ (screw dyad).

Once $[F({\bf N}^{+})]$ is completed, its results have Hermitian symmetry properties with respect to $[{\bf h}^{-}]$ which can be used to obtain the unique electron densities.

Structure factors may be computed by applying the reverse procedures in the reverse order.

1.3.4.3.6.3. Orthorhombic groups

| top | pdf |

Almost all orthorhombic space groups are generated by two monoclinic transformations $[g_{1}]$ and $[g_{2}]$ of the type described in Section 1.3.4.3.6.2, with the addition of a centre of inversion [-e] for centrosymmetric groups. The only exceptions are Fdd2 and Fddd which contain diamond glides, in which some non-primitive translations are `square roots' not of primitive lattice translations, but of centring translations. The generic case will be examined first.

To calculate electron densities, the unique octant of data may first be transformed on $[{\bf h}^{+}]$ (respectively $[{\bf h}^{-}]$ ) as in Section 1.3.4.3.6.2 using the symmetry pertaining to generator $[g_{1}]$ . These intermediate results may then be expanded by generator $[g_{2}]$ by the formula of Section 1.3.4.3.3 prior to the final transform on $[{\bf h}^{-}]$ (respectively $[{\bf h}^{+}]$ ). To calculate structure factors, the reverse operations are applied in the reverse order.

The two exceptional groups Fdd2 and Fddd only require a small modification. The F-centring causes the systematic absence of parity classes with mixed parities, leaving only (000) and (111). For the former, the phase factors $[\exp [2 \pi i ({\bf h}^{+} \cdot {\bf t}_{g}^{+} + {\bf h}^{-} \cdot {\bf t}_{g}^{-})]]$ in the symmetry relations of Section 1.3.4.3.6.2 become powers of (−1) so that one is back to the generic case. For the latter, these phase factors are odd powers of i which it is a simple matter to incorporate into a modified multiplexing/demultiplexing procedure.

1.3.4.3.6.4. Trigonal, tetragonal and hexagonal groups

| top | pdf |

All the symmetries in this class of groups can be handled by the generalized Rader/Winograd algorithms of Section 1.3.4.3.4.3, but no implementation of these is yet available.

In groups containing axes of the form $[n_{m}]$ with g.c.d. $[(m, n) = 1\ (i.e.\ 3_{1}, 3_{2}, 4_{1}, 4_{3}, 6_{1}, 6_{5})]$ along the c direction, the following procedure may be used (Ten Eyck, 1973):

(i) to calculate electron densities, the unique structure factors indexed by $[[\hbox{unique } (h, k)] \times (\hbox{all } l)]$ are transformed on l; the results are rearranged by the transposition formula of Section 1.3.4.3.3 so as to be indexed by $[[\hbox{all } (h, k)] \times \left[\hbox{unique } \left({1 \over n}\right){\rm th} \hbox{ of } z\right]]$ and are finally transformed on (h, k) to produce an asymmetric unit. For a dihedral group, the extra twofold axis may be used in the transposition to produce a unique th of z.
(ii) to calculate structure factors, the unique densities in th of z [or th for a dihedral group] are first transformed on x and y, then transposed by the formula of Section 1.3.4.3.3 to reindex the intermediate results by $[[\hbox{unique } (h, k)] \times (\hbox{all } z)\hbox{;}]$ the last transform on z is then carried out.

1.3.4.3.6.5. Cubic groups

| top | pdf |

These are usually treated as their orthorhombic or tetragonal subgroups, as the body-diagonal threefold axis cannot be handled by ordinary methods of decomposition.

The three-dimensional factorization technique of Section 1.3.4.3.4.1 allows a complete treatment of cubic symmetry. Factoring by 2 along all three dimensions gives four types (i.e. orbits) of parity classes: $[\eqalign{&(000) \qquad \qquad \qquad \hbox{ with residual threefold symmetry,}\cr &(100), (010), (001) \quad \hbox{related by threefold axis,}\cr &(110), (101), (011) \quad \hbox{related by threefold axis,}\cr &(111) \qquad \qquad \qquad \hbox{ with residual threefold symmetry.} }]$ Orbit exchange using the threefold axis thus allows one to reduce the number of partial transforms from 8 to 4 (one per orbit). Factoring by 3 leads to a reduction from 27 to 11 (in this case, further reduction to 9 can be gained by multiplexing the three diagonal classes with residual threefold symmetry into a single class; see Section 1.3.4.3.5.6). More generally, factoring by q leads to a reduction from $[q^{3}]$ to $[{1 \over 3}(q^{3} - q) - q]$ . Each of the remaining transforms then has a symmetry induced from the orthorhombic or tetragonal subgroup, which can be treated as above.

No implementation of this procedure is yet available.

1.3.4.3.6.6. Treatment of centred lattices

| top | pdf |

Lattice centring is an instance of the duality between periodization and decimation: the extra translational periodicity of ρ induces a decimation of $[{\bf F} = \{F_{{\bf h}}\}]$ described by the `reflection conditions' on h. As was pointed out in Section 1.3.4.2.2.3, non-primitive lattices are introduced in order to retain the same matrix representation for a given geometric symmetry operation in all the arithmetic classes in which it occurs. From the computational point of view, therefore, the main advantage in using centred lattices is that it maximizes decomposability (Section 1.3.4.2.2.4); reindexing to a primitive lattice would for instance often destroy the diagonal character of the matrix representing a dyad.

In the usual procedure involving three successive one-dimensional transforms, the loss of efficiency caused by the duplication of densities or the systematic vanishing of certain classes of structure factors may be avoided by using a multiplexing/demultiplexing technique (Ten Eyck, 1973):

(i) for base-centred or body-centred lattices, two successive planes of structure factors may be overlaid into a single plane; after transformation, the results belonging to each plane may be separated by parity considerations;
(ii) for face-centred lattices the same method applies, using four successive planes (the third and fourth with an origin translation);
(iii) for rhombohedral lattices in hexagonal coordinates, three successive planes may be overlaid, and the results may be separated by linear combinations involving cube roots of unity.

The three-dimensional factorization technique of Section 1.3.4.3.4.1 is particularly well suited to the treatment of centred lattices: if the decimation matrix of N contains as a factor $[{\bf N}_{1}]$ a matrix which `integerizes' all the non-primitive lattice vectors, then centring is reflected by the systematic vanishing of certain classes of vectors of decimated data or results, which can simply be omitted from the calculation. An alternative possibly is to reindex on a primitive lattice and use different representative matrices for the symmetry operations: the loss of decomposability is of little consequence in this three-dimensional scheme, although it substantially complicates the definition of the cocycles $[{\boldmu}_{2}]$ and $[{\boldeta}_{1}]$ .

1.3.4.3.6.7. Programming considerations

| top | pdf |

The preceding sections have been devoted to showing how the raw computational efficiency of a crystallographic Fourier transform algorithm can be maximized. This section will briefly discuss another characteristic (besides speed) which a crystallographic Fourier transform program may be required to possess if it is to be useful in various applications: a convenient and versatile mode of presentation of input data or output results.

The standard crystallographic FFT programs (Ten Eyck, 1973, 1985) are rather rigid in this respect, and use rather rudimentary data structures (lists of structure-factor values, and two-dimensional arrays containing successive sections of electron-density maps). It is frequently the case that considerable reformatting of these data or results must be carried out before they can be used in other computations; for instance, maps have to be converted from 2D sections to 3D `bricks' before they can be inspected on a computer graphics display.

The explicitly three-dimensional approach to the factorization of the DFT and the use of symmetry offers the possibility of richer and more versatile data structures. For instance, the use of `decimation in frequency' in real space and of `decimation in time' in reciprocal space leads to data structures in which real-space coordinates are handled by blocks (thus preserving, at least locally, the three-dimensional topological connectivity of the maps) while reciprocal-space indices are handled by parity classes or their generalizations for factors other than 2 (thus making the treatment of centred lattices extremely easy). This global three-dimensional indexing also makes it possible to carry symmetry and multiplicity characteristics for each subvector of intermediate results for the purpose of automating the use of the orbit exchange mechanism.

Brünger (1989) has described the use of a similar three-dimensional factoring technique in the context of structure-factor calculations for the refinement of macromolecular structures.

References

Brünger, A. T. (1989). A memory-efficient fast Fourier transformation algorithm for crystallographic refinement on supercomputers. Acta Cryst. A45, 42–50.Google Scholar

Ten Eyck, L. F. (1973). Crystallographic fast Fourier transforms. Acta Cryst. A29, 183–191.Google Scholar

Ten Eyck, L. F. (1985). Fast Fourier transform calculation of electron density maps. In Diffraction methods for biological macromolecules (Methods in enzymology, Vol. 115), edited by H. Wyckoff, C. H. W. Hirs & S. N. Timasheff, pp. 324–337. New York: Academic Press.Google Scholar

International Tables for Crystallography (2006). Vol. B. ch. 1.3, pp. 82-84