research papers
Likelihoodenhanced fast translation functions
^{a}Department of Haematology, University of Cambridge, Cambridge Institute for Medical Research, Wellcome Trust/MRC Building, Hills Road, Cambridge CB2 2XY, England, and ^{b}Lawrence Berkeley National Laboratory, One Cyclotron Road, Building 64R0121, Berkeley, California 947208118, USA
^{*}Correspondence email: rjr27@cam.ac.uk
This paper is a companion to a recent paper on fast rotation functions [Storoni et al. (2004), Acta Cryst. D60, 432–438], which showed how a Taylorseries expansion of the rotation function leads to improved likelihoodenhanced fast rotation functions. In a similar manner, it is shown here how linear and quadratic Taylorseries expansions and leastsquares approximations of the translation function lead to likelihoodenhanced translation functions, which can be calculated by FFT and which are more sensitive to the correct translation than the traditional correlationcoefficient fast translation function. These likelihoodenhanced translation targets for molecularreplacement searches have been implemented in the program Phaser using the Computational Crystallography Toolbox (cctbx).
Keywords: molecular replacement; translation functions; LETF; Phaser; cctbx.
1. Introduction
Macromolecular structure solution by ; Machin, 1985). Less commonly, full 6ndimensional searches are carried out using either systematic (Sheriff et al., 1999) or stochastic (Kissinger et al., 1999; Glykos & Kokkinidis, 2000) algorithms.
is usually a twostep process. Firstly, a rotation function is used to find the orientation of the search model. Secondly, the position of the (oriented) search model is found using a form of translation function (Rossmann, 1972Many translationsearch functions have been described in the literature. They fall into two general categories: those that are evaluated at each sampled translation point in real space in a bruteforce search and those that are calculated by FFT and therefore generate values for all points on the Fourier grid in real space simultaneously. The FFT methods have the advantage of being several orders of magnitude faster than the bruteforce searches. In the bruteforce category are Rfactor searches (Dodson, 1988), correlation searches on amplitude or intensity (Fujinaga & Read, 1987) and full searches (Bricogne, 1992, 1997; Read, 2001). In the FFT category are the overlap function (Crowther & Blow, 1967) and variations (Tickle, 1985, 1992), which measure the overlap between the observed and calculated Patterson functions, and the fast on intensity (Navaza & Vernoslova, 1995). When there is prior phase information, either from experimental phases or a partial model, FFTbased phased translation functions can be used (Colman et al., 1976; Read & Schierbeek, 1988; Navaza, 2001).
The e.g. AMoRe (Navaza, 1994), MolRep (Vagin & Teplyakov, 1997) and CNS (Brünger et al., 1998)]. If x is the translation of the oriented search model, then CORR is given by
on intensity (CORR) is currently the most successful fast translation function and is widely used in molecularreplacement software [where h is the of a reflection, M_{h} is its multiplicity, is the intensity of the observed data, is its mean value, is the square of the amplitude of the sum of the phased fixed (i.e. known) and moving (i.e. search) structurefactor contributions and is its mean value.
CORR is not as reliable in identifying the correct translation as the ). The expression presented previously is rearranged here in order to make the approximations that will be developed more intuitive. To maximize numerical stability, we compute the log of the likelihood, which has its maximum for the same values of the parameters as the likelihood. If the reflections are assumed to be independent, the total log likelihood for a translation x in the Rice approximation is given by the sum of the reflection log likelihoods. The likelihood for a single reflection is given by
translation function, which is the same as the Rice function used for structure (Read, 2001for acentric reflections, where I_{0} is the modified Bessel function of order zero, and by
for centric reflections. These likelihoods are defined in terms of the probability of measuring an amplitude [= ].
The contribution of acentric reflections to the loglikelihood is therefore given by
and for centric reflections by
In these equations,
The subscripts j_{f} refer to any fixed (i.e. nontranslating) molecules that have an unknown origin relative to the moving molecule. Each F_{jf } thus represents a structurefactor component with unknown relative phase compared with other components (for example, from fixing the orientation but not the position of a molecule) and may represent the sum of a number of molecular transforms with known relative phase. In contrast, is a fixed contribution with known phase relative to the contributions of symmetryrelated copies of the moving molecule. Σ_{N} is the bare variance of the Wilson (1949) distribution, in which nothing is known apart from the unitcell content. Σ_{T} is a variance that takes into account the acquisition of extra information from the contributions of the fixed and moving molecules. Σ_{N′} accounts for the part of the extra information that arises from the F_{jf } contributions with unknown relative phase. The factor ∊ accounts for the statistical effect of symmetry on the expected intensity and is equal to the number of symmetry operations that, when applied to h, leave it unchanged. The D factors are the fractions of the calculated structurefactor components that are correlated with the true values (Luzzati, 1952). To account for the effect of errors in measuring the observed amplitudes, an observational variance contribution is added to Σ_{N}, as performed for experimental phasing (Green, 1979; de La Fortelle & Bricogne, 1997) and structure (Murshudov et al., 1997).
The AMoRe (Navaza, 1994), in which fast methods are used to generate a list of plausible solutions that is then rescored by a better but computationally more expensive target. In our case, we rescore potential solutions using the translation likelihood target (Read, 2001).
translation function is timeconsuming to compute and this problem is one that can affect success in finding the correct solution. In difficult molecularreplacement solutions, the correct orientation may be a long way down the sorted list of potential orientations in the results from the rotation function, and it may only be possible to identify the correct orientation by the high translationfunction score that it generates. If the translation function is too timeconsuming to compute then, in practice, the number of potential orientations that can be tested may be limited and the correct orientation may be missed by the search. Thus, developing an approximation to the fulllikelihood translation function that retains its superior ability to discriminate correct from incorrect solutions, but that may be calculated by FFT, is important to the practical success of a molecularreplacement program. We follow the strategy used inWe showed recently (Storoni et al., 2004) that likelihoodenhanced fast rotation functions are an excellent compromise between the high quality but slow fulllikelihood rotationfunction target and the lower quality but much faster traditional Crowther FFTbased search methods, as they provide better discrimination between correct and incorrect orientations than the Crowther function but at the same speed. Here, we use series approximations to the full Rice translation function to derive several likelihoodenhanced FFT translation functions. These are of higher quality and as fast or faster than CORR.
2. Series approximations of translation function
The fast ) provides an efficient method to compute translation targets expressed through linear and quadratic terms in . We have examined two methods to construct such series approximations of the translation function. Firstly, we have used Taylorseries expansions to the first and second order. Secondly, we have fitted leastsquares linear and quadratic approximations to the likelihood function.
algorithm (Navaza & Vernoslova, 19952.1. Taylorseries expansions
To compute Taylorseries expansions, we require the derivatives of the function with respect to the expansion variable. Starting from (2), the first derivative of with respect to is given by
and the second derivative is given by
where for acentric reflections
and for centric reflections
The firstorder Taylor series expansion of the Rice function, centred at = χ_{h}, is therefore given by
where is a constant not dependent on x.
Similarly, the secondorder Taylor series expansion of the Rice function, centred at = χ_{h}, is given by
where is a constant not dependent on x.
The expansions provide good estimates of the values of the likelihood function over only a restricted range of values of close to the point of expansion. Optimal results thus require a good choice of the region to be approximated. We have chosen to centre the Taylorseries expansions on the expected value of , so that they are most accurate over the range of values likely to be sampled during the translation search. The expected value takes account of the fixed contribution, if any, and the amplitudes of the molecular transforms of symmetry copies k of the moving molecule. This leads to
We have tested the effect of computing the expected value of using less of the available information, i.e. by taking account only of the scattering power of the moving molecule but ignoring the amplitudes of the moleculartransform contributions. As expected, this approximation works less well (results not shown). In addition, we have tested the use of Taylor expansions centred on zero, which degrades the results significantly (results not shown).
2.2. Leastsquares approximations
Leastsquares approximations are computed by fitting either a line or a parabola to values of the likelihood function sampled over the range likely to be spanned by , weighted by the probability of encountering each value of = . The probability distribution for is computed by analogy with the Simlike rotation likelihood function (Read, 2001),
for acentric reflections and
for centric reflections, where
and F_{big} is the largest term in the sum contributing to .
The linear leastsquares approximation is defined by determining the coefficients and that minimize the residual
Similarly, the quadratic leastsquares approximation is defined by determining the coefficients , and that minimize the residual
In practice, we find that it is sufficient to compute the residual with a sum over as few as five points spanning the range of ; Phaser uses seven points for stability.
3. Likelihoodenhanced translation functions
For calculating the optimal position of a search model given a particular orientation, the translationindependent constants could be ignored as they only change the mean of the searchfunction scores. However, we have chosen to retain them so that the scores for different orientations can be compared. The firstorder Taylorseries expansion of the Rice function, combining (5) and (7), then gives what we call the likelihoodenhanced translation function 1 (LETF1),
The secondorder Taylorseries expansion of the Rice likelihood target, combining (6) and (7), gives the likelihoodenhanced translation function 2, or LETF2,
The linear leastsquares approximation of the Rice likelihood target, using coefficients determined by minimizing (8), gives the linear likelihoodenhanced translation function, or LETFL,
Finally, the quadratic leastsquares approximation of the Rice likelihood target, using coefficients determined by minimizing (9), gives the quadratic likelihoodenhanced translation function, or LETFQ,
Information from fixed parts of the model is introduced into the coefficients of the fast translation targets in two ways. Phased structurefactor contributions are incorporated directly through and through the contribution to the variance term in Σ_{T}. Those parts of the structure for which the orientation but not the position are known also contribute to the variance through in Σ_{T}.
4. Implementation
The target functions CORR, LEFT1, LETF2, LETFL and LETFQ described above were implemented in the program Phaser using the Computational Crystallography Toolbox (GrosseKunstleve et al., 2002). For convenience, the calculations are performed in terms of E values, normalized by dividing the structure factors by (∊Σ_{N})^{1/2}. At the same time the variances, such as ∊Σ_{T} in (2), are divided by ∊Σ_{N}.
The fast translation function of Navaza & Vernoslova (1995) was factored into functions that compute and given the h, the coefficients A_{h} and B_{h}, the observed data , the fixed components of the calculated and the molecular transform (in P1) of the moving molecule before translation. With these functions, all of the LETF functions can be computed. For computing , the run time scales with the second power of the number of symmetry operations. For computing , the run time scales with the fourth power of the number of symmetry operations. For centred cells, the summations can be carried out using only the symmetry operations corresponding to the null centring (the `primitive' subset) to minimize the run time (e.g. for Fcentred cells, this decreases the run time by a factor of 4^{4} = 256 for the summations involving the square of the calculated intensities). The same computational saving can also be achieved by transforming the reflection data and coordinates to a primitive setting. This slightly more involved approach has the additional advantage of reducing the memory requirements (e.g. by a factor of 4 for Fcentred cells).
The coefficients of the FFT to compute involve terms to twice the data resolution and those to compute involve terms to four times the data resolution (Navaza & Vernoslova, 1995). It follows from Langs (2002) that the fast translation functions may be evaluated using a grid coarser than the Shannon sampling corresponding to the terms involved. In principle, to preserve all the details, the grid spacing should be at least as fine as the Shannon sampling: d_{min}/4 for doubled resolution and d_{min}/8 for quadrupled resolution. Numerical tests show that a grid spacing of d_{min}/4 is optimal for the firstorder approximations (LETF1 and LETFL). The results for the secondorder approximations (LETF2 and LETFQ) do not improve much when the grid is made finer than d_{min}/5 and they are usually acceptable with a grid of d_{min}/4.
Note that in our implementation of CORR, the components of are weighted by Luzzati (1952) D values reflecting the expected coordinate errors of the models. This improves the results over those obtained without weights.
5. Test cases
Results from three tests are shown below. These examples were chosen to illustrate the performance of the fast translation function targets in a variety of circumstances, not because the use of the new targets is essential to solving these structures. Earlier work (Read, 2001) has already demonstrated that the likelihood targets are more sensitive to the correct solution than traditional targets such as CORR. In Phaser, the top translations from the fast translation search are rescored with the full translation likelihood target; the better the fast search predicts the top peaks, the shorter the list for rescoring can be. We use scatter plots and the between the fast and slow (LLG) scores to evaluate how well the fast scores approximate the slow score and thus predict the order of the rescored peaks. The test cases below were chosen to assess the fast translation scores in cases where an accurate model accounts for either a small proportion or a large proportion of the total and also in cases where the model is less accurate.
No lowresolution cutoffs were applied to the available data in any of the tests.
5.1. βLactamase and βlactamase inhibitor protein complex
The structure of the complex between βlactamase (BETA) and βlactamase inhibitor protein (BLIP) has served as a test structure for (Read, 2003; Storoni et al., 2004) because the original using traditional molecularreplacement techniques was difficult, even though good models for BETA and BLIP were available (Strynadka et al., 1996). The difficulty arose in the search for the BLIP component, especially in determining its orientation, as the BETA component is easily found by traditional (and maximumlikelihood) methods. BLIP was difficult to find by traditional methods for two main reasons. Firstly, the BLIP component of the structure comprises only 38% of the total scattering (the BETA component accounts for the other 62%). Secondly, the data are anisotropic and so there is systematic variation in the structurefactor amplitudes not accounted for by the molecular model, which increases the noise of the search. We have previously shown that full (Read, 2003) and the likelihoodenhanced fast rotation functions (Storoni et al., 2004) allow the BLIP component to be found easily. overcomes the problems of low scattering and anisotropic data (manuscript in preparation) through better modelling of the structurefactor probabilities and by allowing the information from BETA to be included in the search for BLIP.
5.1.1. Searching for BLIP alone with restricted resolution
The correct orientation for BLIP can be found with a likelihoodbased fast rotation search, even when the information about the BETA component is not exploited (Storoni et al., 2004). Once its orientation is known, the translation can be determined easily with any of the fast translationfunction scores. To make the translation search more challenging, we have reduced the signal by truncating the resolution of the data to 6 Å. This test illustrates the case where the model predicts only a relatively small component of the even if the model is reasonably accurate. As Fig. 1(a) shows, only a small range of values of is spanned for a typical reflection as the model is translated. Over this range the Rice likelihood function is reasonably close to linear. The results in Table 1 demonstrate that all the LETF scores provide a much better prediction of the LLG score than does the CORR score. As one might expect, the higher order approximations provide a better fit to LLG and the leastsquares approximations are slightly better than the Taylorseries approximations. The scatter plots in Fig. 2 and the results in Table 2 show that the correct translation receives the top score in all LETF scores, but not with CORR. Nonetheless, the correct translation is near the top of the list even for CORR and would be recovered in this case if the peaks were rescored with the LLG score.


5.1.2. Searching for BLIP, fixing known BETA contribution
In the previous case, the contribution of BLIP accounts for only a small part of the uncertainty in the prediction of the observed structurefactor amplitude, so only a relatively small portion of the Ricefunction curve is sampled as the molecule is translated. To test the case where the translated model accounts for a much greater part of the uncertainty, we carried out tests in which the known contribution of BETA was fixed during the translation search for BLIP using all data to 3 Å resolution. In this case, as shown in Fig. 1(b), a wider range of values of will be sampled and the Rice likelihood function deviates more from a straight line. The results in Table 1 show that, as one might expect, the firstorder approximations work somewhat more poorly than in the case with BLIP alone, but the correlation with the LLG score is still very high for all LETF scores. The results in Table 2 show that with the correct orientation this translation problem is trivial for all search targets.
5.2. TOXD
In a further test, we used the test data for αdendrotoxin (TOXD) distributed with the CCP4 suite (Collaborative Computational Project, Number 4, 1994). This structure was originally solved by (Skarzynski, 1992), but it shares 36% sequence identity with bovine pancreatic trypsin inhibitor. As a model, we have used the structure of bovine pancreatic trypsin inhibitor from PDB entry 1d0d (St Charles et al., 2000). The results in Table 1 demonstrate that the LETF scores are equally good approximations of LLG, whether the model is closely or more distantly related to the target structure.
6. Conclusions
The results demonstrate that all four likelihoodbased fast translation functions investigated here (LETF1, LETF2, LETFL and LETFQ) are superior to CORR in approximating the fulllikelihood target, LLG, and thus in predicting the top solutions. The firstorder approximations (LETF1 and LETFL) have the significant advantage that they only require one FFT, with a map sampled at d_{min}/4. The secondorder approximations (LETF2 and LETFQ) require only two FFTs compared with the three needed for CORR.
In practice, we prefer the use of the LETF1 fast translation function, which is the program default in Phaser. We have not found a molecularreplacement problem in which the secondorder targets succeed in finding the correct solution when LETF1 fails. This is probably because molecularreplacement problems become more difficult as the fragment to be found becomes smaller or the model becomes less accurate. In both situations, the proportion of the observed structurefactor amplitude explained by the model decreases and, as illustrated in Fig. 1, the relevant portion of the Rice likelihoodfunction curve becomes more linear. In addition, the secondorder approximations require a second FFT, leading to greater memory requirements. Finally, the calculation of the first derivative needed for LETF1 is simpler and perhaps more reliable than the leastsquares fitting required for LETFL.
The translation function is also used in dualspace ), where peaks in the are selected. These represent heavyatom pairs and the heavyatom pairs are then translated through the to find the position of the pair. This pair is the basis of a bootstrap procedure to find the rest of the heavy atoms in a The likelihoodenhanced translation functions described here could also be used for these searches.
searches (GrosseKunstleve & Adams, 2003The program Phaser has been released as part of the PHENIX (Adams et al., 2002) software suite and will be released as part of the CCP4 (Collaborative Computational Project, Number 4, 1994) suite. It is also available from the authors (see http://wwwstructmed.cimr.cam.ac.uk/phaser for details).
Acknowledgements
We are grateful to Michael James and Natalie Strynadka for supplying the data for the βlactamase complex test case. This work was funded by NIH/NIGMS under grant No. 1P01GM063210 and by a Principal Research Fellowship from the Wellcome Trust (RJR).
References
Adams, P. D., GrosseKunstleve, R. W., Hung, L.W., Ioerger, T. R., McCoy, A. J., Moriarty, N. W., Read, R. J., Sacchettini, J. C., Sauter, N. K. & Terwilliger, T. C. (2002). Acta Cryst. D58, 1948–1954. Web of Science CrossRef CAS IUCr Journals Google Scholar
Bricogne, G. (1992). Proceedings of the CCP4 Study Weekend. Molecular Replacement, edited by W. Wolf, E. J. Dodson & S. Gover, pp. 62–75. Warrington: Daresbury Laboratory. Google Scholar
Bricogne, G. (1997). Methods Enzymol. 276, 361–423. CrossRef CAS Web of Science Google Scholar
Brünger, A. T., Adams, P. D., Clore, G. M., Gros, P., GrosseKunstleve, R. W., Jiang, J.S., Kuszewski, J., Nilges, M., Pannu, N. S., Read, R. J., Rice, L. M., Simonson, T. & Warren, G. L. (1998). Acta Cryst. D54, 905–921. Web of Science CrossRef IUCr Journals Google Scholar
Collaborative Computational Project, Number 4 (1994). Acta Cryst. D50, 760–763. CrossRef IUCr Journals Google Scholar
Colman, P. M., Fehlhammer, H. & Bartels, K. (1976). Crystallographic Computing Techniques, edited by F. R. Ahmed, K. Huml & B. Sedlacek, pp. 248–258. Copenhagen: Munksgaard. Google Scholar
Crowther, R. A. & Blow, D. M. (1967). Acta Cryst. 23, 544–548. CrossRef IUCr Journals Web of Science Google Scholar
Dodson, E. J. (1988). Crystallographic Computing 4: Techniques and New Technologies, edited by N. W. Isaacs & M. R. Taylor, pp. 80–96. Oxford University Press. Google Scholar
Fujinaga, M. & Read, R. J. (1987). J. Appl. Cryst. 20, 517–521. CrossRef Web of Science IUCr Journals Google Scholar
Glykos, N. M. & Kokkinidis, M. (2000). Acta Cryst. D56, 169–174. Web of Science CrossRef CAS IUCr Journals Google Scholar
Green, E. A. (1979). Acta Cryst. A35, 351–359. CrossRef CAS IUCr Journals Web of Science Google Scholar
GrosseKunstleve, R. W. & Adams, P. D. (2003). Acta Cryst. D59, 1966–1973. Web of Science CrossRef CAS IUCr Journals Google Scholar
GrosseKunstleve, R. W., Sauter, N. K., Moriarty, N. W. & Adams, P. D. (2002). J. Appl. Cryst. 35, 126–136. Web of Science CrossRef CAS IUCr Journals Google Scholar
Kissinger, C. R., Gelhaar, D. K. & Fogel, D. B. (1999). Acta Cryst. D55, 484–491. Web of Science CrossRef CAS IUCr Journals Google Scholar
La Fortelle, E. de & Bricogne, G. (1997). Methods Enzymol. 276, 472–494. Google Scholar
Langs, D. A. (2002). J. Appl. Cryst. 35, 505. Web of Science CrossRef IUCr Journals Google Scholar
Luzzati, V. (1952). Acta Cryst. 5, 802–810. CrossRef IUCr Journals Web of Science Google Scholar
Machin, P. A. (1985). Editor. Proceedings of the Daresbury Study Weekend. Molecular Replacement. Warrington: Daresbury Laboratory. Google Scholar
Murshudov, G. N., Vagin, A. A. & Dodson, E. J. (1997). Acta Cryst. D53, 240–255. CrossRef CAS Web of Science IUCr Journals Google Scholar
Navaza, J. (1994). Acta Cryst. A50, 157–163. CrossRef CAS Web of Science IUCr Journals Google Scholar
Navaza, J. (2001). Acta Cryst. D57, 1367–1372. Web of Science CrossRef CAS IUCr Journals Google Scholar
Navaza, J. & Vernoslova, E. (1995). Acta Cryst. A51, 445–449. CrossRef CAS Web of Science IUCr Journals Google Scholar
Read, R. J. (2001). Acta Cryst. D57, 1373–1382. Web of Science CrossRef CAS IUCr Journals Google Scholar
Read, R. J. (2003). Crystallogr. Rev. 9, 33–41. CrossRef CAS Google Scholar
Read, R. J. & Schierbeek, A. J. (1988). J. Appl. Cryst. 21, 490–495. CrossRef CAS Web of Science IUCr Journals Google Scholar
Rossmann, M. G. (1972). Editor. The Molecular Replacement Method. New York: Gordon & Breach. Google Scholar
Sheriff, S., Klei, H. E. & Davis, M. E. (1999). J. Appl. Cryst. 32, 98–101. Web of Science CrossRef CAS IUCr Journals Google Scholar
Skarzynski, T. (1992). J. Mol. Biol. 224, 671–683. CrossRef PubMed CAS Web of Science Google Scholar
St Charles, R., Padmanabhan, K., Arni, R. V., Padmanabhan, K. P. & Tulinsky, A. (2000). Protein Sci. 9, 265–272. Web of Science PubMed CAS Google Scholar
Storoni, L. C., McCoy, A. J. & Read, R. J. (2004). Acta Cryst. D60, 432–438. Web of Science CrossRef CAS IUCr Journals Google Scholar
Strynadka, N. C., Jensen, S. E., Alzari, P. M. & James, M. N. (1996). Nature Struct. Biol. 3, 290–297. CrossRef CAS PubMed Web of Science Google Scholar
Tickle, I. J. (1985). Proceedings of the Daresbury Study Weekend. Molecular Replacement, edited by P. A. Machin, pp. 22–26. Warrington: Daresbury Laboratory. Google Scholar
Tickle, I.J. (1992). Proceedings of the Daresbury Study Weekend. Molecular Replacement, edited by W. Wolf, E. J. Dodson & S. Gover, pp. 20–32. Warrington: Daresbury Laboratory. Google Scholar
Vagin, A. & Teplyakov, A. (1997). J. Appl. Cryst. 30, 1022–1025. Web of Science CrossRef CAS IUCr Journals Google Scholar
Wilson, A. J. C. (1949). Acta Cryst. 2, 318–321. CrossRef IUCr Journals Web of Science Google Scholar
© International Union of Crystallography. Prior permission is not required to reproduce short quotations, tables and figures from this article, provided the original authors and source are cited. For more information, click here.