Tables for
Volume B
Reciprocal space
Edited by U. Shmueli

International Tables for Crystallography (2010). Vol. B, ch. 1.3, pp. 95-100   | 1 | 2 |

Section Derivatives for model refinement

G. Bricognea

aGlobal Phasing Ltd, Sheraton House, Suites 14–16, Castle Park, Cambridge CB3 0AX, England, and LURE, Bâtiment 209D, Université Paris-Sud, 91405 Orsay, France Derivatives for model refinement

| top | pdf |

Since the origins of X-ray crystal structure analysis, the calculation of crystallographic Fourier series has been closely associated with the process of refinement. Fourier coefficients with phases were obtained for all or part of the measured reflections in the basis of some trial model for all or part of the structure, and Fourier syntheses were then used to complete and improve this initial model. This approach is clearly described in the classic paper by Bragg & West (1929)[link], and was put into practice in the determination of the structures of topaz (Alston & West, 1929[link]) and diopside (Warren & Bragg, 1929[link]). Later, more systematic methods of arriving at a trial model were provided by the Patterson synthesis (Patterson, 1934[link], 1935a[link],b[link]; Harker, 1936[link]) and by isomorphous replacement (Robertson, 1935[link], 1936c[link]). The role of Fourier syntheses, however, remained essentially unchanged [see Robertson (1937)[link] for a review] until more systematic methods of structure refinement were introduced in the 1940s. A particularly good account of the processes of structure completion and refinement may be found in Chapters 15 and 16 of Stout & Jensen (1968)[link].

It is beyond the scope of this section to review the vast topic of refinement methods: rather, it will give an account of those aspects of their development which have sought improved power by exploiting properties of the Fourier transformation. It is of more than historical interest that some recent advances in the crystallographic refinement of macromolecular structures had been anticipated by Cochran and Cruickshank in the early 1950s. The method of least squares

| top | pdf |

Hughes (1941)[link] was the first to use the already well established multivariate least-squares method (Whittaker & Robinson, 1944[link]) to refine initial estimates of the parameters describing a model structure. The method gained general acceptance through the programming efforts of Friedlander et al. (1955)[link], Sparks et al. (1956)[link], Busing & Levy (1961)[link] and others.

The Fourier relations between [\rho\llap{$-\!$}] and F (Section[link]) are used to derive the `observational equations' connecting the structure parameters [\{u_{p}\}_{p = 1, \ldots, n}] to the observations [\{|F_{{\bf h}}|^{\rm obs}, (\sigma_{{\bf h}}^{2})^{\rm obs}\}_{{\bf h} \in {\scr H}}] comprising the amplitudes and their experimental variances for a set [{\scr H}] of unique reflections.

The normal equations giving the corrections δu to the parameters are then[({\bf A}^{T}{\bf WA})\delta {\bf u} = - {\bf A}^{T}{\bf W}\Delta,]where[\eqalign{A_{{\bf h}p} &= {\partial | F_{{\bf h}}^{\,\rm calc}| \over \partial u_{p}}\cr \Delta_{{\bf h}} &= |F_{{\bf h}}^{\,\rm calc}| - |F_{{\bf h}}|^{\rm obs}\cr {\bf W} &= \hbox{diag } (W_{{\bf h}}) \quad \hbox{with} \quad W_{{\bf h}} = {1 \over (\sigma_{{\bf h}}^{2})^{\rm obs}}.}]To calculate the elements of A, write:[F = |F| \exp (i\varphi) = \alpha + i\beta\hbox{\semi}]hence[\eqalign{ {\partial |F| \over \partial u} &= {\partial \alpha \over \partial u} \cos \varphi + {\partial \beta \over \partial u} \sin \varphi\cr &= {\scr Re} \left[{\partial F \over \partial u} \overline{\exp (i\varphi)}\right] = {\scr Re} \left[{\overline{\partial F} \over \partial u} \exp (i\varphi)\right].}]

In the simple case of atoms with real-valued form factors and isotropic thermal agitation in space group P1,[F_{{\bf h}}^{\,\rm calc} = {\textstyle\sum\limits_{j \in J}}\, g_{j} ({\bf h}) \exp (2\pi i{\bf h}\cdot {\bf x}_{j}),]where[g_{j} ({\bf h}) = Z_{j}\,f_{j} ({\bf h}) \exp [-{\textstyle{1 \over 4}} B_{j} (d_{{\bf h}}^{*})^{2}],][Z_{j}] being a fractional occupancy.

Positional derivatives with respect to [{\bf x}_{j}] are given by[\eqalign{ {\partial F_{{\bf h}}^{\,\rm calc} \over \partial {\bf x}_{j}} &= (2\pi i{\bf h}) g_{j} ({\bf h}) \exp (2\pi i{\bf h}\cdot {\bf x}_{j})\cr {\partial |F_{{\bf h}}^{\,\rm calc}| \over \partial {\bf x}_{j}} &= {\scr Re} [(- 2\pi i{\bf h}) g_{j} ({\bf h}) \exp (-2 \pi i{\bf h}\cdot {\bf x}_{j}) \exp (i\varphi_{{\bf h}}^{\rm calc})]}]so that the corresponding [3 \times 1] subvector of the right-hand side of the normal equations reads:[\eqalign{&- \sum\limits_{{\bf h}\in {\scr H}} W_{{\bf h}} {\partial |F_{{\bf h}}^{\,\rm calc}| \over \partial {\bf x}_{j}} (|F_{{\bf h}}^{\,\rm calc}| - |F_{{\bf h}}|^{\rm obs})\cr &\quad= - {\scr Re} \left [\sum\limits_{{\bf h}\in {\scr H}} g_{j} ({\bf h}) (-2\pi i{\bf h}) W_{{\bf h}} (|F_{{\bf h}}^{\rm calc}| - |F_{{\bf h}}|^{\rm obs})\right.\cr &\qquad \times \left.\exp (i\varphi_{{\bf h}}^{\rm calc}) \exp (-2\pi i{\bf h}\cdot {\bf x}_{j})\right ].}]

The setting up and solution of the normal equations lends itself well to computer programming and has the advantage of providing a thorough analysis of the accuracy of its results (Cruickshank, 1965b[link], 1970[link]; Rollett, 1970[link]). It is, however, an expensive task, of complexity [\propto n \times |{\scr H}|^{2}], which is unaffordable for macromolecules. Booth's differential Fourier syntheses

| top | pdf |

It was the use of Fourier syntheses in the completion of trial structures which provided the incentive to find methods for computing 2D and 3D syntheses efficiently, and led to the Beevers–Lipson strips. The limited accuracy of the latter caused the estimated positions of atoms (identified as peaks in the maps) to be somewhat in error. Methods were therefore sought to improve the accuracy with which the coordinates of the electron-density maxima could be determined. The naive method of peak-shape analysis from densities recalculated on a [3 \times 3 \times 3] grid using high-accuracy trigonometric tables entailed 27 summations per atom.

Booth (1946a)[link] suggested examining the rapidly varying derivatives of the electron density rather than its slowly varying values. If[\rho\llap{$-\!$} ({\bf x}) = {\textstyle\sum\limits_{{\bf h}}} F_{{\bf h}} \exp (-2\pi i{\bf h}\cdot {\bf x})]then the gradient vector [\nabla_{{\bf x}}\rho\llap{$-\!$}] of [\rho\llap{$-\!$}] at [{\bf x}^{0}][(\nabla_{{\bf x}}\rho\llap{$-\!$}) ({\bf x}^{0}) = {\textstyle\sum\limits_{{\bf h}}} \,F_{{\bf h}} (-2\pi i{\bf h}) \exp (-2\pi i{\bf h}\cdot {\bf x}^{0})]can be calculated by means of three Fourier summations from the [3 \times 1] vector of Fourier coefficients[(-2\pi i{\bf h}) F_{{\bf h}}.]Similarly, the Hessian matrix of [\rho\llap{$-\!$}] at [{\bf x}^{0}][[(\nabla_{{\bf x}} \nabla_{{\bf x}}^{T}){\rho\llap{$-\!$}}] ({\bf x}^{0}) = {\textstyle\sum\limits_{{\bf h}}} \,F_{{\bf h}} (-4\pi^{2} {\bf hh}^{T}) \exp (-2\pi i{\bf h}\cdot {\bf x}^{0})]can be calculated by six Fourier summations from the unique elements of the symmetric matrix of Fourier coefficients:[-4\pi^{2} \pmatrix{h^{2} &hk &hl\cr hk &k^{2} &kl\cr hl &kl &l^{2}\cr} F_{{\bf h}}.]

The scalar maps giving the components of the gradient and Hessian matrix of [\rho\llap{$-\!$}] will be called differential syntheses of 1st order and 2nd order respectively. If [{\bf x}^{0}] is approximately but not exactly a maximum of [\rho\llap{$-\!$}], then the Newton–Raphson estimate of the true maximum [{\bf x}^{*}] is given by:[{\bf x}^{*} = {\bf x}^{0} - [[(\nabla_{{\bf x}} \nabla_{{\bf x}}^{T}){\rho\llap{$-\!$}}] ({\bf x}^{0})]^{-1} [\nabla_{\bf x}\rho\llap{$-\!$} ({\bf x}^{0})].]This calculation requires only nine accurate Fourier summations (instead of 27), and this number is further reduced to four if the peak is assumed to be spherically symmetrical.

The resulting positions are affected by series-termination errors in the differential syntheses. Booth (1945c[link], 1946c)[link] proposed a `back-shift correction' to eliminate them, and extended this treatment to the acentric case (Booth, 1946b[link]). He cautioned against the use of an artificial temperature factor to fight series-termination errors (Brill et al., 1939[link]), as this could be shown to introduce coordinate errors by causing overlap between atoms (Booth, 1946c[link], 1947a[link],b[link]).

Cruickshank was able to derive estimates for the standard uncertainties of the atomic coordinates obtained in this way (Cox & Cruickshank, 1948[link]; Cruickshank, 1949a[link],b[link]) and to show that they agreed with those provided by the least-squares method.

The calculation of differential Fourier syntheses was incorporated into the crystallographic programs of Ahmed & Cruickshank (1953b)[link] and of Sparks et al. (1956)[link]. Booth's method of steepest descents

| top | pdf |

Having defined the now universally adopted R factors (Booth, 1945b[link]) as criteria of agreement between observed and calculated amplitudes or intensities, Booth proposed that R should be minimized with respect to the set of atomic coordinates [\{{\bf x}_{j}\}_{j\in J}] by descending along the gradient of R in parameter space (Booth, 1947c[link],d[link]). This `steepest descents' procedure was compared with Patterson methods by Cochran (1948d)[link].

When calculating the necessary derivatives, Booth (1948a[link], 1949[link]) used the formulae given above in connection with least squares. This method was implemented by Qurashi (1949)[link] and by Vand (1948[link], 1951[link]) with parameter-rescaling modifications which made it very close to the least-squares method (Cruickshank, 1950[link]; Qurashi & Vand, 1953[link]; Qurashi, 1953[link]). Cochran's Fourier method

| top | pdf |

Cochran (1948b[link],c[link], 1951a[link]) undertook to exploit an algebraic similarity between the right-hand side of the normal equations in the least-squares method on the one hand, and the expression for the coefficients used in Booth's differential syntheses on the other hand (see also Booth, 1948a[link]). In doing so he initiated a remarkable sequence of formal and computational developments which are still actively pursued today.

Let [\rho\llap{$-\!$}_{\rm C} ({\bf x})] be the electron-density map corresponding to the current atomic model, with structure factors [|F_{{\bf h}}^{\,\rm calc}| \exp (i\varphi_{{\bf h}}^{\rm calc})]; and let [\rho\llap{$-\!$}_{\rm O} ({\bf x})] be the map calculated from observed moduli and calculated phases, i.e. with coefficients [\{|F_{{\bf h}}|^{\rm obs} \exp (i\varphi_{{\bf h}}^{\rm calc})\}_{{\bf h}\in {\scr H}}]. If there are enough data for [\rho\llap{$-\!$}_{\rm C}] to have a resolved peak at each model atomic position [{\bf x}_{j}], then[(\nabla_{{\bf x}} \rho\llap{$-\!$}_{\rm C})({\bf x}_{j}) = {\bf 0} \quad \hbox{for each } j \in J\hbox{\semi}]while if the calculated phases [\varphi_{\bf h}^{\rm calc}] are good enough, [\rho\llap{$-\!$}_{\rm O}] will also have peaks at each [{\bf x}_{j}]:[(\nabla_{{\bf x}} \rho\llap{$-\!$}_{\rm O})({\bf x}_{j}) = {\bf 0} \quad \hbox{for each } j \in J.]It follows that[\eqalign{[\nabla_{{\bf x}} (\rho\llap{$-\!$}_{\rm C} - \rho\llap{$-\!$}_{\rm O})] ({\bf x}_{j}) &= {\textstyle\sum\limits_{{\bf h}}} (-2 \pi i{\bf h}) [(|F_{{\bf h}}^{\,\rm calc}| - |F_{{\bf h}}|^{\rm obs}) \exp (i\varphi_{\bf h}^{\rm calc})]\cr &\quad \times \exp (-2 \pi i{\bf h} \cdot {\bf x}_{j})\cr &= {\bf 0} \hbox{ for each } j \in J,}]where the summation is over all reflections in [{\scr H}] or related to [{\scr H}] by space-group and Friedel symmetry (overlooking multiplicity factors!). This relation is less sensitive to series-termination errors than either of the previous two, since the spectrum of [\rho\llap{$-\!$}_{\rm O}] could have been extrapolated beyond the data in [{\scr H}] by using that of [\rho\llap{$-\!$}_{\rm C}] [as in van Reijen (1942)[link]] without changing its right-hand side.

Cochran then used the identity[{\partial F_{{\bf h}}^{\,\rm calc} \over \partial {\bf x}_{j}} = (2 \pi i{\bf h}) g_{j} ({\bf h}) \exp (2 \pi i{\bf h} \cdot {\bf x}_{j})]in the form[(-2 \pi i{\bf h}) \exp (-2 \pi i{\bf h} \cdot {\bf x}_{j}) = {1 \over g_{j} ({\bf h})} {\overline{\partial F_{{\bf h}}^{\,\rm calc}} \over \partial {\bf x}_{j}}]to rewrite the previous relation as[\eqalign{&[\nabla_{{\bf x}} (\rho\llap{$-\!$}_{\rm C} - \rho\llap{$-\!$}_{\rm O})] ({\bf x}_{j})\cr &\quad= \sum\limits_{{\bf h}} {1 \over g_{j} ({\bf h})} (|F_{{\bf h}}^{\,\rm calc}| - |F_{{\bf h}}|^{\rm obs}) {\scr R}{e} \left[{\overline{\partial F_{{\bf h}}^{\,\rm calc}} \over \partial {\bf x}_{j}} \exp (i \varphi_{{\bf h}}^{\rm calc})\right]\cr &\quad= \sum\limits_{{\bf h}} {1 \over g_{j} ({\bf h})} (|F_{{\bf h}}^{\,\rm calc}| - |F_{{\bf h}}|^{\rm obs}) {\partial |F_{{\bf h}}^{\,\rm calc}| \over \partial {\bf x}_{j}}\cr &\quad= {\bf 0} \quad \hbox{for each } j \in J}](the operation [{\scr Re}][] on the first line being neutral because of Friedel symmetry). This is equivalent to the vanishing of the [3 \times 1] subvector of the right-hand side of the normal equations associated to a least-squares refinement in which the weights would be[W_{{\bf h}} = {1 \over g_{j} ({\bf h})}.]Cochran concluded that, for equal-atom structures with [g_{j} ({\bf h}) = g ({\bf h})] for all j, the positions [{\bf x}_{j}] obtained by Booth's method applied to the difference map [\rho\llap{$-\!$}_{\rm O} - \rho\llap{$-\!$}_{\rm C}] are such that they minimize the residual[{\textstyle{1 \over 2} }\sum\limits_{{\bf h}} {1 \over g({\bf h})} (|F_{{\bf h}}^{\,\rm calc}| - |F_{{\bf h}}|^{\rm obs})^{2}]with respect to the atomic positions. If it is desired to minimize the residual of the ordinary least-squares method, then the differential synthesis method should be applied to the weighted difference map[\sum\limits_{{\bf h}} {W_{{\bf h}} \over g({\bf h})} (|F_{{\bf h}}^{\,\rm calc}| - |F_{{\bf h}}|^{\rm obs}) \exp (i \varphi_{{\bf h}}^{\rm calc}).]He went on to show (Cochran, 1951b[link]) that the refinement of temperature factors could also be carried out by inspecting appropriate derivatives of the weighted difference map.

This Fourier method was used by Freer et al. (1976)[link] in conjunction with a stereochemical regularization procedure to refine protein structures. Cruickshank's modified Fourier method

| top | pdf |

Cruickshank consolidated and extended Cochran's derivations in a series of classic papers (Cruickshank, 1949b[link], 1950[link], 1952[link], 1956[link]). He was able to show that all the coefficients involved in the right-hand side and normal matrix of the least-squares method could be calculated by means of suitable differential Fourier syntheses even when the atoms overlap. This remarkable achievement lay essentially dormant until its independent rediscovery by Agarwal in 1978 (Section[link]).

To ensure rigorous equivalence between the summations over [{\bf h} \in {\scr H}] (in the expressions of least-squares right-hand side and normal matrix elements) and genuine Fourier summations, multiplicity-corrected weights were introduced by:[\eqalign{ w_{{\bf h}} &= {1 \over |G_{{\bf h}}|} W_{{\bf h}}\quad \hbox{ if } {\bf h} \in G{\bf h}\quad \hbox{ with } {\bf h} \in {\scr H},\cr w_{\bf h} &= 0\phantom{{241 \over |G_{{\bf h}}{12 \over 1}|}}\quad \hbox{otherwise},}]where Gh denotes the orbit of h and [G_{{\bf h}}] its isotropy subgroup (Section[link]). Similarly, derivatives with respect to parameters of symmetry-unique atoms were expressed, via the chain rule, as sums over the orbits of these atoms.

Let [p = 1, \ldots, n] be the label of a parameter [u_{p}] belonging to atoms with label j. Then Cruickshank showed that the pth element of the right-hand side of the normal equations can be obtained as [D_{p, \, j} ({\bf x}_{j})], where [D_{p, \, j}] is a differential synthesis of the form[\eqalign{ D_{p, \, j} ({\bf x}) &= {\textstyle\sum\limits_{{\bf h}}} P_{p} ({\bf h}) g_{j} ({\bf h}) w_{{\bf h}} (|F_{{\bf h}}^{\,\rm calc}| - |F_{{\bf h}}|^{\rm obs})\cr &\quad \times \exp (i\varphi_{{\bf h}}^{\rm calc}) \exp (-2 \pi i{\bf h} \cdot {\bf x})}]with [P_{p}({\bf h})] a polynomial in (h, k, l) depending on the type of parameter p. The correspondence between parameter type and the associated polynomial extends Booth's original range of differential syntheses, and is recapitulated in the following table.[\eqalign{ &\quad\hbox{Parameter type}\qquad P (h, k, l)\cr &\overline{\hskip13pc}\cr &\quad x \hbox{ coordinate} \quad \qquad - 2 \pi ih\cr &\quad y \hbox{ coordinate} \quad \qquad - 2 \pi ik\cr &\quad z \hbox{ coordinate} \quad \qquad - 2 \pi il\cr &\quad B \hbox{ isotropic} \quad \qquad \,- {\textstyle{1 \over 4}} (d_{{\bf h}}^{*})^{2}\cr &\quad B^{11} \hbox{ anisotropic} \qquad - h^{2}\cr &\quad B^{12} \hbox{ anisotropic} \qquad - hk\cr &\quad B^{13} \hbox{ anisotropic} \qquad - hl\cr &\quad B^{22} \hbox{ anisotropic} \qquad - k^{2}\cr &\quad B^{23} \hbox{ anisotropic} \qquad - kl\cr &\quad B^{33} \hbox{ anisotropic} \qquad - l^{2}.}]Unlike Cochran's original heuristic argument, this result does not depend on the atoms being resolved.

Cruickshank (1952)[link] also considered the elements of the normal matrix, of the form[\sum\limits_{{\bf h}} w_{{\bf h}} {\partial |F_{{\bf h}}^{\,\rm calc}| \over \partial u_{p}} {\partial |F_{{\bf h}}^{\,\rm calc}| \over \partial u_{q}}]associated with positional parameters. The [3 \times 3] block for parameters [{\bf x}_{j}] and [{\bf x}_{k}] may be written[\eqalign{&{\textstyle\sum\limits_{{\bf h}}} w_{{\bf h}} ({\bf hh}^{T}) {\scr Re} [(-2 \pi i) g_{j} ({\bf h}) \exp (-2 \pi i{\bf h} \cdot {\bf x}_{j}) \exp (i \varphi_{{\bf h}}^{\rm calc})]\cr &\quad \times {\scr Re} [(-2 \pi i) g_{k} ({\bf h}) \exp (-2 \pi i{\bf h} \cdot {\bf x}_{k}) \exp (i \varphi_{{\bf h}}^{\rm calc})]}]which, using the identity[{\scr Re}(z_{1}) {\scr Re}(z_{2}) = {\textstyle{1 \over 2}}[{\scr Re} (z_{1} z_{2}) + {\scr Re} (z_{1} \overline{z_{2}})],]becomes[\eqalign{&2\pi^{2} {\textstyle\sum\limits_{{\bf h}}} w_{{\bf h}} ({\bf hh}^{T}) g_{j}({\bf h})g_{k}({\bf h})\cr &\quad \times \{\exp [-2\pi i{\bf h} \cdot ({\bf x}_{j} - {\bf x}_{k})]\cr &\quad - \exp (2i\varphi_{{\bf h}}^{\rm calc}) \exp [ - 2\pi i{\bf h} \cdot ({\bf x}_{j} + {\bf x}_{k})]\}}](Friedel's symmetry makes [{\scr Re}] redundant on the last line). Cruickshank argued that the first term would give a good approximation to the diagonal blocks of the normal matrix and to those off-diagonal blocks for which [{\bf x}_{j}] and [{\bf x}_{k}] are close. On this basis he was able to justify the `n-shift rule' of Shoemaker et al. (1950)[link]. Cruickshank gave this derivation in a general space group, but using a very terse notation which somewhat obscures it. Using the symmetrized trigonometric structure-factor kernel [\Xi^{-}] of Section[link] and its multiplication formula, the above expression is seen to involve the values of a Fourier synthesis at points of the form [{\bf x}_{j} \pm S_{g} ({\bf x}_{k})].

Cruickshank (1956)[link] showed that this analysis could also be applied to the refinement of temperature factors.

These two results made it possible to obtain all coefficients involved in the normal equations by looking up the values of certain differential Fourier syntheses at [{\bf x}_{j}] or at [{\bf x}_{j} \pm S_{g} ({\bf x}_{k})]. At the time this did not confer any superiority over the standard form of the least-squares procedure, because the accurate computation of Fourier syntheses was an expensive operation. The modified Fourier method was used by Truter (1954)[link] and by Ahmed & Cruickshank (1953a)[link], and was incorporated into the program system described by Cruickshank et al. (1961)[link]. A more recent comparison with the least-squares method was made by Dietrich (1972)[link].

There persisted, however, some confusion about the nature of the relationship between Fourier and least-squares methods, caused by the extra factors [g_{j} ({\bf h})] which make it necessary to compute a differential synthesis for each type of atom. This led Cruickshank to conclude that `in spite of their remarkable similarities the least-squares and modified-Fourier methods are fundamentally distinct'. Agarwal's FFT implementation of the Fourier method

| top | pdf |

Agarwal (1978)[link] rederived and completed Cruickshank's results at a time when the availability of the FFT algorithm made the Fourier method of calculating the coefficients of the normal equations much more economical than the standard method, especially for macromolecules.

As obtained by Cruickshank, the modified Fourier method required a full 3D Fourier synthesis

  • – for each type of parameter, since this determines [via the polynomial [P_{p} ({\bf h})]] the type of differential synthesis to be computed;

  • – for each type of atom [j \in J], since the coefficients of the differential synthesis must be multiplied by [g_{j}({\bf h})].

Agarwal disposed of the latter dependence by pointing out that the multiplication involved is equivalent to a real-space convolution between the differential synthesis and [\sigma\llap{$-$}_{j} ({\bf x})], the standard electron density [\rho\llap{$-\!$}_{j}] for atom type j (Section[link]) smeared by the isotropic thermal agitation of that atom. Since [\sigma\llap{$-$}_{j}] is localized, this convolution involves only a small number of grid points. The requirement of a distinct differential synthesis for each parameter type, however, continued to hold, and created some difficulties at the FFT level because the symmetries of differential syntheses are more complex than ordinary space-group symmetries. Jack & Levitt (1978)[link] sought to avoid the calculation of difference syntheses by using instead finite differences calculated from ordinary Fourier or difference Fourier maps.

In spite of its complication, this return to the Fourier implementation of the least-squares method led to spectacular increases in speed (Isaacs & Agarwal, 1978[link]; Agarwal, 1980[link]; Baker & Dodson, 1980[link]) and quickly gained general acceptance (Dodson, 1981[link]; Isaacs, 1982a[link],b[link], 1984[link]). Lifchitz's reformulation

| top | pdf |

Lifchitz [see Agarwal et al. (1981)[link], Agarwal (1981)[link]] proposed that the idea of treating certain multipliers in Cruickshank's modified differential Fourier syntheses by means of a convolution in real space should be applied not only to [g_{j} ({\bf h})], but also to the polynomials [P_{p} ({\bf h})] which determine the type of differential synthesis being calculated. This leads to convoluting [\partial \sigma\llap{$-$}_{j}/\partial u_{p}] with the same ordinary weighted difference Fourier synthesis, rather than [\sigma\llap{$-$}_{j}] with the differential synthesis of type p. In this way, a single Fourier synthesis, with ordinary (scalar) symmetry properties, needs be computed; the parameter type and atom type both intervene through the function [\partial \sigma\llap{$-$}_{j}/\partial u_{p}] with which it is convoluted. This approach has been used as the basis of an efficient general-purpose least-squares refinement program for macromolecular structures (Tronrud et al., 1987[link]).

This rearrangement amounts to using the fact (Section[link]) that convolution commutes with differentiation. Let[D({\bf x}) = {\textstyle\sum\limits_{{\bf h}}} w_{{\bf h}}(|F_{{\bf h}}^{\,\rm calc}| - |F_{{\bf h}}|^{\rm obs}) \exp (i\varphi_{{\bf h}}^{\rm calc}) \exp (-2\pi i {\bf h} \cdot {\bf x})]be the inverse-variance weighted difference map, and let us assume that parameter [u_{p}] belongs to atom j. Then the Agarwal form for the pth component of the right-hand side of the normal equations is[\left({\partial D \over \partial u_{p}} * \sigma\llap{$-$}_{j}\right)(x_{j}),]while the Lifchitz form is[\left(D * {\partial \sigma\llap{$-$}_{j} \over \partial u_{p}}\right)({\bf x}_{j}).] A simplified derivation

| top | pdf |

A very simple derivation of the previous results will now be given, which suggests the possibility of many generalizations.

The weighted difference map [D({\bf x})] has coefficients [D_{{\bf h}}] which are the gradients of the global residual with respect to each [F_{{\bf h}}^{\,\rm calc}]:[D_{{\bf h}} = {\partial R \over \partial A_{{\bf h}}^{\rm calc}} + i {\partial R \over \partial B_{{\bf h}}^{\rm calc}}.]By the chain rule, a variation of each [F_{{\bf h}}^{\,\rm calc}] by [\delta F_{{\bf h}}^{\,\rm calc}] will result in a variation of R by [\delta R] with[\delta R = \sum\limits_{{\bf h}} \left[{\partial R \over \partial A_{{\bf h}}^{\rm calc}} \delta A_{{\bf h}}^{\rm calc} + {\partial R \over \partial B_{{\bf h}}^{\rm calc}} \delta B_{{\bf h}}^{\rm calc}\right] = {\scr Re} \sum\limits_{{\bf h}} [\overline{D_{{\bf h}}} \delta F_{{\bf h}}^{\,\rm calc}].]The [{\scr Re}] operation is superfluous because of Friedel symmetry, so that [\delta R] may be simply written in terms of the Hermitian scalar product in [\ell^{2}({\bb Z}^{3})]:[\delta R = ({\bf D}, \delta {\bf F}^{\rm calc}).]If [\rho\llap{$-\!$}^{\rm calc}] is the transform of [\delta {\bf F}^{\rm calc}], we have also by Parseval's theorem[\delta R = (D, \delta \rho\llap{$-\!$}^{\rm calc}).]We may therefore write[D ({\bf x}) = {\partial R \over \partial \rho\llap{$-\!$}^{\,\rm calc} ({\bf x})},]which states that [D({\bf x})] is the functional derivative of R with respect to [\rho\llap{$-\!$}^{\rm calc}].

The right-hand side of the normal equations has [\partial R/\partial u_{p}] for its pth element, and this may be written[{\partial R \over \partial u_{p}} = \int_{{\bb R}^{3}/{\bb Z}^{3}} {\partial R \over \partial \rho\llap{$-\!$}^{\,\rm calc}({\bf x})} {\partial \rho\llap{$-\!$}^{\rm calc}({\bf x}) \over \partial u_{p}} \hbox{d}^{2}{\bf x} = \left(D, {\partial \rho\llap{$-\!$}^{\rm calc} \over \partial u_{p}}\right).]If [u_{p}] belongs to atom j, then[{\partial \rho\llap{$-\!$}^{\rm calc} \over \partial u_{p}} = {\partial (\tau_{{\bf x}_{j}} \sigma_{j}) \over \partial u_{p}} = \tau_{{\bf x}_{j}} \left({\partial \sigma\llap{$-$}_{j} \over \partial u_{p}}\right)\hbox{\semi}]hence[{\partial R \over \partial u_{p}} = \left(D, \tau_{{\bf x}_{j}} \left({\partial \sigma\llap{$-$}_{j} \over \partial u_{p}}\right)\right).]By the identity of Section[link], this is identical to Lifchitz's expression [(D * \partial \sigma\llap{$-$}_{j}/\partial u_{p})({\bf x}_{j})]. The present derivation in terms of scalar products [see Brünger (1989)[link] for another presentation of it] is conceptually simpler, since it invokes only the chain rule [other uses of which have been reviewed by Lunin (1985)[link]] and Parseval's theorem; economy of computation is obviously related to the good localization of [\partial \rho\llap{$-\!$}^{\rm calc}/\partial u_{p}] compared to [\partial {F}^{\,\rm calc}/\partial u_{p}]. Convolutions, whose meaning is less clear, are no longer involved; they were a legacy of having first gone over to reciprocal space via differential syntheses in the 1940s.

Cast in this form, the calculation of derivatives by FFT methods appears as a particular instance of the procedure described in connection with variational techniques (Section[link]) to calculate the coefficients of local quadratic models in a search subspace; this is far from surprising since varying the electron density through a variation of the parameters of an atomic model is a particular case of the `free' variations considered by the variational approach. The latter procedure would accommodate in a very natural fashion the joint consideration of an energetic (Jack & Levitt, 1978[link]; Brünger et al., 1987[link]; Brünger, 1988[link]; Brünger et al., 1989[link]; Kuriyan et al., 1989[link]) or stereochemical (Konnert, 1976[link]; Sussman et al., 1977[link]; Konnert & Hendrickson, 1980[link]; Hendrickson & Konnert, 1980[link]; Tronrud et al., 1987[link]) restraint function (which would play the role of S) and of the crystallographic residual (which would be C). It would even have over the latter the superiority of affording a genuine second-order approximation, albeit only in a subspace, hence the ability of detecting negative curvature and the resulting bifurcation behaviour (Bricogne, 1984[link]). Current methods are unable to do this because they use only first-order models, and this is known to degrade severely the overall efficiency of the refinement process. Discussion of macromolecular refinement techniques

| top | pdf |

The impossibility of carrying out a full-matrix least-squares refinement of a macromolecular crystal structure, caused by excessive computational cost and by the paucity of observations, led Diamond (1971)[link] to propose a real-space refinement method in which stereochemical knowledge was used to keep the number of free parameters to a minimum. Refinement took place by a least-squares fit between the `observed' electron-density map and a model density consisting of Gaussian atoms. This procedure, coupled to iterative recalculation of the phases, led to the first highly refined protein structures obtained without using full-matrix least squares (Huber et al., 1974[link]; Bode & Schwager, 1975[link]; Deisenhofer & Steigemann, 1975[link]; Takano, 1977a[link],b[link]).

Real-space refinement takes advantage of the localization of atoms (each parameter interacts only with the density near the atom to which it belongs) and gives the most immediate description of stereochemical constraints. A disadvantage is that fitting the `observed' electron density amounts to treating the phases of the structure factors as observed quantities, and to ignoring the experimental error estimates on their moduli. The method is also much more vulnerable to series-termination errors and accidentally missing data than the least-squares method. These objections led to the progressive disuse of Diamond's method, and to a switch towards reciprocal-space least squares following Agarwal's work.

The connection established above between the Cruickshank–Agarwal modified Fourier method and the simple use of the chain rule affords a partial refutation to both the premises of Diamond's method and to the objections made against it:

  • (i) it shows that refinement can be performed through localized computations in real space without having to treat the phases as observed quantities;

  • (ii) at the same time, it shows that measurement errors on the moduli can be fully utilized in real space, via the Fourier synthesis of the functional derivative [\partial R/\partial \rho\llap{$-\!$}^{\rm calc}({\bf x})] or by means of the coefficients of a quadratic model of R in a search subspace. Sampling considerations

| top | pdf |

The calculation of the inner products [(D, \partial \rho\llap{$-\!$}^{\rm calc}/\partial u_{p})] from a sampled gradient map D requires even more caution than that of structure factors via electron-density maps described in Section[link], because the functions [\partial \sigma\llap{$-$}_{j}/\partial u_{p}] have transforms which extend even further in reciprocal space than the [\sigma\llap{$-$}_{j}] themselves. Analytically, if the [\sigma\llap{$-$}_{j}] are Gaussians, the [\partial \sigma\llap{$-$}_{j}/\partial u_{p}] are finite sums of multivariate Hermite functions (Section[link]) and hence the same is true of their transforms. The difference map D must therefore be finely sampled and the relation between error and sampling rate may be investigated as in Section[link] An examination of the sampling rates commonly used (e.g. one third of the resolution) shows that they are insufficient. Tronrud et al. (1987)[link] propose to relax this requirement by applying an artificial temperature factor to [\sigma\llap{$-$}_{j}] (cf. Section[link]) and the negative of that temperature factor to D, a procedure of questionable validity because the latter `sharpening' operation is ill defined [the function exp [(\|{\bf x}\|^{2})] does not define a tempered distribution, so the associativity properties of convolution may be lost]. A more robust procedure would be to compute the scalar product by means of a more sophisticated numerical quadrature formula than a mere grid sum.


Agarwal, R. C. (1978). A new least-squares refinement technique based on the fast Fourier transform algorithm. Acta Cryst. A34, 791–809.
Agarwal, R. C. (1980). The refinement of crystal structure by fast Fourier least-squares. In Computing in Crystallography, edited by R. Diamond, S. Ramaseshan & K. Venkatesan, pp. 18.01–18.13. Bangalore: The Indian Academy of Science.
Agarwal, R. C. (1981). New results on fast Fourier least-squares refinement technique. In Refinement of Protein Structures, compiled by P. A. Machin, J. W. Campbell & M. Elder (ref. DL/SCI/R16), pp. 24–28. Warrington: SERC Daresbury Laboratory.
Agarwal, R. C., Lifchitz, A. & Dodson, E. J. (1981). Appendix (pp. 36–38) to Dodson (1981).
Ahmed, F. R. & Cruickshank, D. W. J. (1953a). A refinement of the crystal structure analysis of oxalic acid dihydrate. Acta Cryst. 6, 385–392.
Ahmed, F. R. & Cruickshank, D. W. J. (1953b). Crystallographic calculations on the Manchester University electronic digital computer (Mark II). Acta Cryst. 6, 765–769.
Alston, N. A. & West, J. (1929). The structure of topaz, [Al(F,OH)]2SiO4. Z. Kristallogr. 69, 149–167.
Baker, E. N. & Dodson, E. J. (1980). Crystallographic refinement of the structure of actinidin at 1.7 Å resolution by fast Fourier least-squares methods. Acta Cryst. A36, 559–572.
Bode, W. & Schwager, P. (1975). The refined crystal structure of bovine β-trypsin at 1.8Å resolution. II. Crystallographic refinement, calcium-binding site, benzamidine binding site and active site at pH 7.0. J. Mol. Biol. 98, 693–717.
Booth, A. D. (1945b). An expression for following the process of refinement in X-ray structure analysis using Fourier series. Philos. Mag. 36, 609–615.
Booth, A. D. (1945c). Accuracy of atomic co-ordinates derived from Fourier synthesis. Nature (London), 156, 51–52.
Booth, A. D. (1946a). A differential Fourier method for refining atomic parameters in crystal structure analysis. Trans. Faraday Soc. 42, 444–448.
Booth, A. D. (1946b). The simultaneous differential refinement of co-ordinates and phase angles in X-ray Fourier synthesis. Trans. Faraday Soc. 42, 617–619.
Booth, A. D. (1946c). The accuracy of atomic co-ordinates derived from Fourier series in X-ray structure analysis. Proc. R. Soc. London Ser. A, 188, 77–92.
Booth, A. D. (1947a). The accuracy of atomic co-ordinates derived from Fourier series in X-ray structure analysis. III. Proc. R. Soc. London Ser. A, 190, 482–489.
Booth, A. D. (1947b). The accuracy of atomic co-ordinates derived from Fourier series in X-ray structure analysis. IV. The two-dimensional projection of oxalic acid. Proc. R. Soc. London Ser. A, 190, 490–496.
Booth, A. D. (1947c). A new refinement technique for X-ray structure analysis. J. Chem. Phys. 15, 415–416.
Booth, A. D. (1947d). Application of the method of steepest descents to X-ray structure analysis. Nature (London), 160, 196.
Booth, A. D. (1948a). A new Fourier refinement technique. Nature (London), 161, 765–766.
Booth, A. D. (1949). The refinement of atomic parameters by the technique known in X-ray crystallography as `the method of steepest descents'. Proc. R. Soc. London Ser. A, 197, 336–355.
Bragg, W. L. & West, J. (1929). A technique for the X-ray examination of crystal structures with many parameters. Z. Kristallogr. 69, 118–148.
Bricogne, G. (1984). Maximum entropy and the foundations of direct methods. Acta Cryst. A40, 410–445.
Brill, R., Grimm, H., Hermann, C. & Peters, C. (1939). Anwendung der röntgenographischen Fourieranalyse auf Fragen den chemischen Bindung. Ann. Phys. (Leipzig), 34, 393–445.
Brünger, A. T. (1988). Crystallographic refinement by simulated annealing. In Crystallographic Computing 4: Techniques and New Technologies, edited by N. W. Isaacs & M. R. Taylor, pp. 126–140. New York: Oxford University Press.
Brünger, A. T. (1989). A memory-efficient fast Fourier transformation algorithm for crystallographic refinement on supercomputers. Acta Cryst. A45, 42–50.
Brünger, A. T., Karplus, M. & Petsko, G. A. (1989). Crystallographic refinement by simulated annealing: application to crambin. Acta Cryst. A45, 50–61.
Brünger, A. T., Kuriyan, J. & Karplus, M. (1987). Crystallographic R factor refinement by molecular dynamics. Science, 235, 458–460.
Busing, W. R. & Levy, H. A. (1961). Least squares refinement programs for the IBM 704. In Computing Methods and the Phase Problem in X-ray Crystal Analysis, edited by R. Pepinsky, J. M. Robertson & J. C. Speakman, pp. 146–149. Oxford: Pergamon Press.
Cochran, W. (1948b). The Fourier method of crystal structure analysis. Nature (London), 161, 765.
Cochran, W. (1948c). The Fourier method of crystal-structure analysis. Acta Cryst. 1, 138–142.
Cochran, W. (1948d). X-ray analysis and the method of steepest descents. Acta Cryst. 1, 273.
Cochran, W. (1951a). Some properties of the [F_{o} - F_{c}]-synthesis. Acta Cryst. 4, 408–411.
Cochran, W. (1951b). The structures of pyrimidines and purines. V. The electron distribution in adenine hydrochloride. Acta Cryst. 4, 81–92.
Cox, E. G. & Cruickshank, D. W. J. (1948). The accuracy of electron-density maps in X-ray structure analysis. Acta Cryst. 1, 92–93.
Cruickshank, D. W. J. (1949a). The accuracy of electron-density maps in X-ray analysis with special reference to dibenzyl. Acta Cryst. 2, 65–82.
Cruickshank, D. W. J. (1949b). The accuracy of atomic co-ordinates derived by least-squares or Fourier methods. Acta Cryst. 2, 154–157.
Cruickshank, D. W. J. (1950). The convergence of the least-squares and Fourier refinement methods. Acta Cryst. 3, 10–13.
Cruickshank, D. W. J. (1952). On the relations between Fourier and least-squares methods of structure determination. Acta Cryst. 5, 511–518.
Cruickshank, D. W. J. (1956). The determination of the anisotropic thermal motion of atoms in crystals. Acta Cryst. 9, 747–753.
Cruickshank, D. W. J. (1965b). Errors in least-squares methods. In Computing Methods in Crystallography, edited by J. S. Rollett, pp. 112–116. Oxford: Pergamon Press.
Cruickshank, D. W. J. (1970). Least-squares refinement of atomic parameters. In Crystallographic Computing, edited by F. R. Ahmed, pp. 187–197. Copenhagen: Munksgaard.
Cruickshank, D. W. J., Pilling, D. E., Bujosa, A., Lovell, F. M. & Truter, M. R. (1961). Crystallographic calculations on the Ferranti Pegasus and mark I computers. In Computing Methods and the Phase Problem in X-Ray Crystal Analysis, edited by R. Pepinsky, J. M. Robertson & J. C. Speakman, pp. 32–78. Oxford: Pergamon Press.
Deisenhofer, J. & Steigemann, W. (1975). Crystallographic refinement of the structure of bovine pancreatic trypsin inhibitor at 1.5 Å resolution. Acta Cryst. B31, 238–250.
Diamond, R. (1971). A real-space refinement procedure for proteins. Acta Cryst. A27, 436–452.
Dietrich, H. (1972). A reconsideration of Fourier methods for the refinement of crystal structures. Acta Cryst. B28, 2807–2814.
Dodson, E. J. (1981). Block diagonal least squares refinement using fast Fourier techniques. In Refinement of Protein Structures, compiled by P. A. Machin J. W. Campbell & M. Elder (ref. DL/SCI/R16), pp. 29–39. Warrington: SERC Daresbury Laboratory.
Freer, S. T., Alden, R. A., Levens, S. A. & Kraut, J. (1976). Refinement of five protein structures by constrained Fo − Fc Fourier methods. In Crystallographic Computing Techniques, edited by F. R. Ahmed, pp. 317–321. Copenhagen: Munksgaard.
Friedlander, P. H., Love, W. & Sayre, D. (1955). Least-squares refinement at high speed. Acta Cryst. 8, 732.
Harker, D. (1936). The application of the three-dimensional Patterson method and the crystal structures of proustite, Ag3AsS3, and pyrargyrite, Ag3SbS3. J. Chem. Phys. 4, 381–390.
Hendrickson, W. A. & Konnert, J. H. (1980). Incorporation of stereo­chemical information into crystallographic refinement. In Computing in Crystallography, edited by R. Diamond, S. Ramaseshan & K. Venkatesan, pp. 13.01–13.26. Bangalore: The Indian Academy of Science.
Huber, R., Kulka, D., Bode, W., Schwager, P., Bartels, K., Deisenhofer, J. & Steigemann, W. (1974). Structure of the complex formed by bovine trypsin and bovine pancreatic trypsin inhibitor. II. Crystallographic refinement at 1.9 Å resolution. J. Mol. Biol. 89, 73–101.
Hughes, E. W. (1941). The crystal structure of melamine. J. Am. Chem. Soc. 63, 1737–1752.
Isaacs, N. W. (1982a). The refinement of macromolecules. In Computational Crystallography, edited by D. Sayre, pp. 381–397. New York: Oxford University Press.
Isaacs, N. W. (1982b). Refinement techniques: use of the FFT. In Computational Crystallography, edited by D. Sayre, pp. 398–408. New York: Oxford University Press.
Isaacs, N. W. (1984). Refinement using the fast-Fourier transform least squares algorithm. In Methods and Applications in Crystallographic Computing, edited by S. R. Hall & T. Ashida, pp. 193–205. New York: Oxford University Press.
Isaacs, N. W. & Agarwal, R. C. (1978). Experience with fast Fourier least squares in the refinement of the crystal structure of rhombohedral 2-zinc insulin at 1.5 Å resolution. Acta Cryst. A34, 782–791.
Jack, A. & Levitt, M. (1978). Refinement of large structures by simultaneous minimization of energy and R factor. Acta Cryst. A34, 931–935.
Konnert, J. H. (1976). A restrained-parameter structure-factor least-squares refinement procedure for large asymmetric units. Acta Cryst. A32, 614–617.
Konnert, J. H. & Hendrickson, W. A. (1980). A restrained-parameter thermal-factor refinement procedure. Acta Cryst. A36, 344–350.
Kuriyan, J., Brünger, A. T., Karplus, M. & Hendrickson, W. A. (1989). X-ray refinement of protein structures by simulated annealing: test of the method on myohemerythrin. Acta Cryst. A45, 396–409.
Lunin, V. Yu. (1985). Use of the fast differentiation algorithm for phase refinement in protein crystallography. Acta Cryst. A41, 551–556.
Patterson, A. L. (1934). A Fourier series method for the determination of the components of interatomic distances in crystals. Phys. Rev. 46, 372–376.
Patterson, A. L. (1935a). A direct method for the determination of the components of interatomic distances in crystals. Z. Kristallogr. 90, 517–542.
Patterson, A. L. (1935b). Tabulated data for the seventeen plane groups. Z. Kristallogr. 90, 543–554.
Qurashi, M. M. (1949). Optimal conditions for convergence of steepest descents as applied to structure determination. Acta Cryst. 2, 404–409.
Qurashi, M. M. (1953). An analysis of the efficiency of convergence of different methods of structure determination. I. The methods of least squares and steepest descents: centrosymmetric case. Acta Cryst. 6, 577–588.
Qurashi, M. M. & Vand, V. (1953). Weighting of the least-squares and steepest-descents methods in the initial stages of the crystal-structure determination. Acta Cryst. 6, 341–349.
Reijen, L. L. van (1942). Diffraction effects in Fourier syntheses and their elimination in X-ray structure investigations. Physica, 9, 461–480.
Robertson, J. M. (1935). An X-ray study of the structure of phthalocyanines. Part I. The metal-free, nickel, copper, and platinum compounds. J. Chem. Soc. pp. 615–621.
Robertson, J. M. (1936c). An X-ray study of the phthalocyanines. Part II. Quantitative structure determination of the metal-free compound. J. Chem. Soc. pp. 1195–1209.
Robertson, J. M. (1937). X-ray analysis and application of Fourier series methods to molecular structures. Phys. Soc. Rep. Prog. Phys. 4, 332–367.
Rollett, J. S. (1970). Least-squares procedures in crystal structure analysis. In Crystallographic Computing, edited by F. R. Ahmed, pp. 167–181. Copenhagen: Munksgaard.
Shoemaker, D. P., Donohue, J., Schomaker, V. & Corey, R. B. (1950). The crystal structure of LS-threonine. J. Am. Chem. Soc. 72, 2328–2349.
Sparks, R. A., Prosen, R. J., Kruse, F. H. & Trueblood, K. N. (1956). Crystallographic calculations on the high-speed digital computer SWAC. Acta Cryst. 9, 350–358.
Stout, G. H. & Jensen, L. H. (1968). X-ray Structure Determination. A Practical Guide. New York: Macmillan.
Sussman, J. L., Holbrook, S. R., Church, G. M. & Kim, S.-H. (1977). A structure-factor least-squares refinement procedure for macromolecular structures using constrained and restrained parameters. Acta Cryst. A33, 800–804.
Takano, T. (1977a). Structure of myoglobin refined at 2.0 Å resolution. I. Crystallographic refinement of metmyoglobin from sperm whale. J. Mol. Biol. 110, 537–568.
Takano, T. (1977b). Structure of myoglobin refined at 2.0 Å resolution. II. Structure of deoxymyoglobin from sperm whale. J. Mol. Biol. 110, 569–584.
Tronrud, D. E., Ten Eyck, L. F. & Matthews, B. W. (1987). An efficient general-purpose least-squares refinement program for macromolecular structures. Acta Cryst. A43, 489–501.
Truter, M. R. (1954). Refinement of a non-centrosymmetrical structure: sodium nitrite. Acta Cryst. 7, 73–77.
Vand, V. (1948). Method of steepest descents: improved formula for X-ray analysis. Nature (London), 161, 600–601.
Vand, V. (1951). A simplified method of steepest descents. Acta Cryst. 4, 285–286.
Warren, B. & Bragg, W. L. (1929). The structure of diopside, CaMg(SiO3)2. Z. Kristallogr. 69, 168–193.
Whittaker, E. T. & Robinson, G. (1944). The Calculus of Observations. London: Blackie.

to end of page
to top of page