Springer Protocols: Abstract: The Dead-End Elimination Theorem:: Mathematical Aspects, Implementation, Optimizations, Evaluation and Performance

The Dead-End Elimination Theorem:: Mathematical Aspects, Implementation, Optimizations, Evaluation and Performance

By: Marc De Maeyer², Johan Desmet³, Ignace Lasters⁴

Abstract

Full Text

Download PDF (406K)

The placement of amino acid side chains in a given fixed main-chain template forms a recurrent but nontrivial task in protein modeling. Even for a small set of side chains in a given protein, the degrees of freedom for the side chains lead to an enormous number of combinatorial possibilities, inevitably prohibiting a brute force approach to pinpoint the global minimum energy conformation (GMEC). The recognition of the existence of statistically relevant discrete combinations of the dihedral angles (called rotamers) of a side chain forms the basis of all current side-chain placement techniques (1). Several research groups have published methods to predict the side chain positions in a fixed protein main-chain trace (review in refs. 2 and 3)

Affiliation(s): (2) Center for Transgene Technology and Gene Therapy, Flanders Interuniversity Institute for Biotechnology, Leuven, Belgium
(3) Interdisciplinary Research Center, Kortrijk, Belgium
(4) Beagle bvla., Antwerpen, Belgium

Book Title: Protein Structure Prediction: Methods and Protocols

Series: Methods in Molecular Biology | Volume: 143 | Pub. Date: Aug-15-2000 | Page Range: 265-304 | DOI: 10.1385/1-59259-368-2:265

Subject: Protein Science

References

Download References

1.	Janin, J., Wodak, S., Levitt, M., and Maigret, B. (1978) Conformation of amino acid sidechains in proteins. J. Mol. Biol. 125, 357–386.

2.	Vásquez, M. (1996) Modeling sidechain conformation. Curr. Opin. Struct. Biol. 6, 217–221.

3.	Sánchez, R. and Šlali, A. (1997) Advances in comparative protein-structure modelling. Curr. Opin. Struct. Biol. 7, 206–214.

4.	Desmet, J., De Maeyer, M., Hazes, B., and Lasters, I. (1992) The dead-end elimination theorem and its use in protein sidechain positioning. Nature (Lond.) 356, 539–542.

5.	Tanimura, R., Kidera, A., and Nakamura, H. (1994) Determinants of protein sidechain packing. Protein Sci. 3, 2358–2365.

6.	M. De Maeyer, M., Desmet, J., and Lasters, I. (1997) All in one: a highly detailed rotamer library improves both accuracy and speed in the modelling of sidechains by dead end elimination. Fold. Des. 2, 53–66.

7.	Leach, A. R. (1994) Ligand docking to proteins with discrete sidechain flexibility. J. Mol. Biol. 235, 345–356

8.	Desmet, J., De Maeyer M., and Lasters, I. (1997) Computation of the binding of fully flexible peptides to proteins with flexible side chains. FASEB J. 44, 164–172.

9.	Rabijns, A., De Bondt, H. L., and De Ranter, C. (1997) Three-dimensional structure of staphylokinase, a plasminogen activator with therapeutic potential. Nat. Struct. Biol. 4, 357–360.

10.	Rashid, A. K., Van Hauwaert, M. L., Haque, M., Siddiqi, A. H., Lasters, I., De Maeyer, M., Griffon, N., Marden, M. C., Dewilde, S., Clauwaert, J., Vinogradov, S. N., and Moens, L. (1997) Trematode myoglobins, functional molecules with a distal tyrosine. J. Biol. Chem. 272, 2992–2999.

11.	Dahiyat, B. I. and Mayo, S. L. (1996) Protein design automation. Protein Sci. 5, 895–903.

12.	Dahiyat, B. I. and Mayo, S. L. (1997) De novo protein design: fully automated sequence selection. Science 278, 82–87.

13.	Lasters, I., Desmet, J., and De Maeyer, M. (1997) Dead-end based modeling tools to explore the sequence space that is compatible with a given scaffold. J. Protein Chem. 16, 449–452.

14.	James, M. N. G., and Sielecki, A. R. (1983) Structure and refinement of penicillopepsin at 1. 8 Å resolution. J. Mol. Biol. 163, 299–361.

15.	McGregor, M. J., Islam, S. A., and Sternberg, M. J. E. (1987) Analysis of the relationship between sidechain conformation and secondary structure in globular proteins. J. Mol. Biol. 198, 295–310.

16.	Ponder, J. W. and Richards, F. M. (1987) Tertiary templates for proteins. Use of packing criteria in the enumeration of allowed sequences for different structural classes. J. Mol. Biol. 193, 775–791.

17.	IUPAC-IUB Commission on Biochemical Nomenclature (1970) Abbreviations and symbols for the description of the conformation of Polypeptide chains. Tentative rules. (1969) J. Mol. Biol. 52, 1–17.

18.	Schrauber, H., Eisenhaber, F., and Argos, P. (1993) Rotamers: to be or not to be? An analysis of amino acid sidechain conformations in globular proteins. J. Mol. Biol. 230, 592–612.

19.	Lasters, I., De Maeyer, M., and Desmet, J. (1995) Enhanced dead-end elimination in the search for the global minimum energy conformation of a collection of protein sidechains. Protein Eng. 8, 815–822.

20.	Goldstein, R. F. (1994) Efficient rotamer elimination applied to protein sidechains and related spin glasses. Biophys. J. 66, 1335–1340.

21.	Lasters, I. and Desmet, J. (1993) The fuzzy-end elimination theorem: correctly implementing the sidechain placement algorithm based on the dead-end elimination theorem. Protein Eng. 6, 717–722.

22.	Press, W., Flannery, B. P., Tuekolsky, S. A., and Vetterling, W. T. (1989) in Numerical Recipes. The Art of Scientific Computing, Cambridge University Press, UK.

23.	Eisenmenger, F., Argos, P., and Abagyan, R. (1993) A method to configure protein sidechains from the mainchain trace in homology modelling. J. Mol. Biol. 231, 849–860.

24.	Delhaise, Ph., Bardiaux, M., and Wodak, S. (1984) Interactive computer animation of macromolecules. J. Mol. Graph. 2, 103–106.

25.	Wodak, S., De Coen, J. L., Edelstein, S. J., Demarne, H., and Beuzard, Y. (1986) Modification of human hemoglobin by gluthadione. III. Perturbations of hemoglobin conformation analyzed by computer modeling. J. Biol. Chem. 261, 14,717–14,724.

26.	Warshel, A. and Levitt, M. (1976) Theoretical studies of enzymatic reactions: dielectric, electrostatic and steric stabilization of the carbonium ion in the reaction of lysozyme. J. Mol. Biol. 103, 227–249

27.	Brooks, B. R., Bruccoleri, R., Olafson, D., States, D. J., Swaminathan, S., and Karplus, M. (1983) CHARMM: a program for macromolecular energy, minimization, and dynamics calculations. J. Comput. Chem. 4, 187–217.

28.	Keller, K. A., Shibata, M., Marcus, E., Ornstein, R. L., and Rein, R. (1995) Finding the global minimum: a fuzzy end elimination implementation. Protein Eng. 8, 893–904.

29.	Bernstein, F. C., Tasumi, M., Koetzle, T. F., et al. (1977) The Protein Data Bank: a computer-based archival file for macromolecular structures. J. Mol. Biol. 112, 535–542.

30.	Desmet, J., De Maeyer, M., and Lasters, I. (1994) The “The Dead, End Elimination” Theorem: A New Approach to the Side, Chain Packing Problem, in The Protein Folding Problem and Tertiary Structure Prediction (Merz, K. M. Jr and Le Grands, S. M., eds.), Birkhäuser, Boston, pp. 307–337.

31.	Desmet, J., De Maeyer, M., and Lasters, I. (1997) Theoretical and algorithmical optimisations of the dead-end elimination theorem, in Proceedings of the Pacific Symposium on Biocomputing’ 97 (Altman, R. B., Dunker, A. K., Hunter, L., and Klein, T. E., eds.) World Scientific, Signapore, pp. 122–133.

32.	Miller, S., Janin, J., Lesk, A. M., and Chothia, C. (1987) Interior and surface of monomeric proteins. J. Mol. Biol. 196, 641–656.

33.	Holm, L. and Sander, C. (1992) Fast and simple Monte Carlo algorithm for sidechain optimization in proteins: application to model building by homology. Proteins: Struct. Funct. Genet. 14, 213–223.

34.	Tufféry, P., Etchebest, C., Hazout, S., and Lavery, R. (1993) A critical comparison of search algorithm applied to the optimization of protein sidechain conformations. J. Comput. Chem. 14, 790–798.

35.	Wilson, C., Gregoret, L. M., and Agard, D. A. (1993) Modeling sidechain conformation for homologous proteins using an energy-based rotamer search. J. Mol. Biol. 229, 996–1006.

36.	Lee, C. and Subbiah, S. (1991) Prediction of protein sidechain conformation by packing optimization. J. Mol. Biol. 217, 373–388.

37.	Laughton, C. A. (1994) Prediction of protein sidechain conformations from local three-dimensional homology relationships. J. Mol. Biol. 235, 1088–1097.

38.	Koehl, P. and Delarue, M. (1994) Application of a self-consistent mean field theory to predict protein sidechains conformation and estimate their conformational entropy. J. Mol. Biol. 239, 249–275.

39.	Hwang, J. and Liao, W. (1995) Sidechain prediction by neural networks and simulated annealing optimization. Protein Eng. 8, 363–370.

40.	Jones, T. A., Zou, J.-Y., Cowan, S. W., and Kjelgaard, M. (1991) Improved methods for building protein models in electron density maps and the location of errors in these models. Acta Cryst. A47, 110–119.

41.	Schiffer, C. A., Caldwell, J. W., Kollman, P. A., and Stroud, R. M. (1990) Prediction of homologous protein structures based on conformational searches and energetics. Proteins: Struct. Funct. Genet. 8, 30–43.

42.	Alard, Ph and Wodak, S. J. (1991) Detection of cavities in a set of interpenetrating spheres. J. Comp. Chem. 12, 918–922.

43.	Bower, M. J., Cohen, F. E., and Dunbrack, R. L. Jr. (1997) Prediction of protein side-chain rotamers from a backbone-dependent rotamer library: a new homology modeling tool. J. Mol. Biol. 267, 1268–1282.

45.	Săli, A. (1995) Modelling mutations and homologous proteins. Curr. Opin. Biotechnol. 6, 437–451.

46.	Vásquez, M. (1996) Modeling sidechain conformation. Curr. Opin. Struct. Biol. 6, 217–221.

47.	Tufféry, P., Etchebest, C., Hazout, S., and Lavery, R. (1991) A new appoach to the rapid determination of protein side chain conformations. J. Biomol. Struct. Dyn. 8, 1267–1289.

48.	Tufféry, P., Etchebest, C., Hazout, S., and Lavery, R. (1993) A critical comparison of search algorithm applied to the optimization of protein sidechain conformations. J. Comput. Chem. 14, 790–798.

49.	Correa, P. E. (1990) The building of protein structures from alpha-carbon coordinates. Proteins: Struct. Funct. Genet. 7, 366–377.

50.	Lee, C. and Subbiah, S. (1991) Prediction of protein sidechain conformation by packing optimization. J. Mol. Biol. 217, 373–388.

51.	Chinea, G., Padron, G., Hooft, R. W., Sander, C., and Vriend, G. (1995) The use of position-specific rotamers in model building by homology. Proteins 23, 415–421.

52.	Laughton, C. A. (1994) Prediction of protein sidechain conformations from local three-dimensional homology relationships. J. Mol. Biol. 235,1088–1097.

53.	Kono, H. and Doi, J. (1994) Energy minimization method using automata network for sequence and sidechain conformation prediction from given backbone geometry. Proteins: Struct. Funct. Genet. 19, 244–255.

54.	Holm, L. and Sander, C. (1991) Database algorithm for generating protein backbone and sidechain co-ordinates from a Cα trace: application to model building and detection of co-ordinate errors. J. Mol. Biol. 218, 183–194.

55.	Lee, C. (1994) Predicting protein mutant energetics by self-consistent ensemble optimization. J. Mol. Biol. 236, 918–939.

56.	Shenkin, P. S., Farid, H., and Fetrow, J. S. (1996) Prediction and evaluation of side-chain conformations for protein backbone structures. Proteins 26, 323–352.

57.	Koehl, P. and Delarue, M. (1994) Application of a self-consistent mean field theory to predict protein sidechains conformation and estimate their conformational entropy. J. Mol. Biol. 239, 249–275.

58.	Levitt, M. (1992) Accurate modelling of protein conformation by automatic segment matching. J. Mol. Biol. 226, 507–533.

59.	Dandekar, T. and König, R. (1997) Computational methods for the prediction of protein folds. Biochim. Biophys. Acta. 1343, 1–15.

60.	Hendrickson, W. A., Teeter, M. M. (1981) Structure of the hydrophobic protein crambin determined directly from the anomalous scattering of sulphur. Nature 290, 107.

61.	Watenpaugh, K. D., Sieker, L. C., Jensen, L. H. (1980) Crystallographic refinement of rubredoxin at 1.2 Å degrees resolution. J. Mol. Biol. 138, 615–633.

62.	Bode, W., Epp, O., Huber, R., Laskowski, M. Jr., and Ardelt, W. (1985) The crystal and molecular structure of the third domain of silver pheasant ovomucoid (OMSVP3) Eur. J. Biochem. 147, 387–395.

63.	Wlodawer, A., Walter, J., Huber, R., and Sjolin, L. (1984) Structure of bovine pancreatic trypsin inhibitor. Results of joint neutron and X-ray refinement of crystal form II. J. Mol. Biol. 180, 301–329.

64.	Derrick, J. P. and Wigley, D. B. (1994) The third IgG-binding domain from strepto-coccal protein G. An analysis by X-ray crystallography of the structure alone and in a complex with Fab. J. Mol. Biol. 243, 906–918.

65.	Smith, J. L., Corfield, P. W., Hendrickson, W. A., and Low, B. W. (1988) Refinement at 1.4 Å resolution of a model of erabutoxin b: treatment of ordered solvent and discrete disorder. Acta Crystallogr. A. 44, 357–368.

66.	Zhao, B., Carson, M., Ealick, S. E., and Bugg, C. E. (1992) Structure of scorpion toxin variant-3 at 1.2 Å resolution. J. Mol. Biol. 227, 239–252.

67.	Pflugrath, J. W., Wiegand, G., Huber, R., and Vertesy, L. (1986) Crystal structure determination, refinement and the molecular model of the alpha-amylase inhibitor Hoe-467A. J. Mol. Biol. 189, 383–386.

68.	Vijay-Kumar, S., Bugg, C. E., and Cook, W. J. (1987) Structure of ubiquitin refined at 1.8 Å resolution. J. Mol. Biol. 194, 531–544.

69.	Matsuura, Y., Takano, T., and Dickerson, R. E. (1982) Structure of cytochrome c551 from Pseudomonas aeruginosa refined at 1.6 Å resolution and comparison of the two redox forms. J. Mol. Biol. 156, 389–409.

70.	Zegers, I., Haikal, A. F., Palmer, R., and Wyns, L. (1994) Crystal structure of RNase T1 with 3′-guanylic acid and guanosine. J. Biol. Chem. 269, 127–133.

71.	Lederer, F., Glatigny, A., Bethge, P. H., Bellamy, H. D., and Matthew, F. S. (1981) Improvement of the 2.5 Å resolution model of cytochrome b562 by redetermining the primary structure and using molecular graphics. J. Mol. Biol. 148, 427–448.

72.	Finzel, B. C., Weber, P. C., Ohlendorf, D. H., and Salemme, F. R. (1991) Crystallographic refinement of bovine pro-phospholipase A2 at 1.6 Å resolution. Acta Crystallogr. 47, 814–816.

73.	Wlodawer, A., Svensson, L. A., Sjolin, L., and Gilliland, G. L. (1988) Structure of phosphate-free ribonuclease A refined at 1.26 Å. Biochemistry 27, 2705–2717.

74.	Zegers, I., Maes, D., Dao-Thi, M. H., Poortmans, F., Palmer, R., and Wyns, L. (1994) The structures of RNase A complexed with 3′-CMP and d(CpA): active site conformation and conserved water molecules. Protein Sci. 3, 2322–2339.

75.	Baker, E. N. (1988) Structure of azurin from Alcaligenes denitrificans refinement at 1.8 Å resolution and comparison of the two crystallographically independent molecules. J. Mol. Biol. 203, 1071–1095.

76.	Artymiuk, P. J. and Blake, C. C. (1981) Refinement of human lysozyme at 1.5 Å resolution analysis of non-bonded and hydrogen-bond interactions. J. Mol. Biol. 152, 737–762.

77.	Bolognesi, M., Onesti, S., Gatti, G., Coda, A., Ascenzi, P., and Brunori, M. (1989) Aplysia limacina myoglobin. Crystallographic analysis at 1.6 Å resolution. J. Mol. Biol. 205, 529–544.

78.	Wright, C. S. (1990) 2.2 A resolution structure analysis of two refined N-acetylneuraminyl-lactose-wheat germ agglutinin isolectin complexes. J. Mol. Biol. 215, 635–651.

79.	Huber, R., Steigemann, W., Kukla, D., et al. (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.