Crossref journal-article
American Association for the Advancement of Science (AAAS)
Science (221)
Abstract

Finding the optimal solution to a complex optimization problem is of great importance in many fields, ranging from protein structure prediction to the design of microprocessor circuitry. Some recent progress in finding the global minima of potential energy functions is described, focusing on applications of the simple “basin-hopping” approach to atomic and molecular clusters and more complicated hypersurface deformation techniques for crystals and biomolecules. These methods have produced promising results and should enable larger and more complex systems to be treated in the future.

Bibliography

Wales, D. J., & Scheraga, H. A. (1999). Global Optimization of Clusters, Crystals, and Biomolecules. Science, 285(5432), 1368–1372.

Authors 2
  1. David J. Wales (first)
  2. Harold A. Scheraga (additional)
References 106 Referenced 993
  1. Schmidt M., Kusche R., Kronmüller W., von Issendorff B., Haberland H., Phys. Rev. Lett. 79, 99 (1997). (10.1103/PhysRevLett.79.99) / Phys. Rev. Lett. by Schmidt M. (1997)
  2. Wales D. J., Miller M. A., Walsh T. R., Nature 394, 758 (1998). (10.1038/29487) / Nature by Wales D. J. (1998)
  3. Zwanzig R., Szabo A., Bagchi B., Proc. Natl. Acad. Sci. U.S.A. 89, 20 (1992); (10.1073/pnas.89.1.20) / Proc. Natl. Acad. Sci. U.S.A. by Zwanzig R. (1992)
  4. Leopold P. E. Montal M. Onuchic J. N. 89 8721 (1992); (10.1073/pnas.89.18.8721)
  5. Hao M. H., Scheraga H. A., J. Phys. Chem. 98, 9882 (1994); (10.1021/j100090a024) / J. Phys. Chem. by Hao M. H. (1994)
  6. Sali A., Shakhnovich E., Karplus M., Nature 369, 248 (1994) ; (10.1038/369248a0) / Nature by Sali A. (1994)
  7. 10.1002/prot.340210302
  8. 10.1063/1.472697
  9. 10.1126/science.282.5389.740
  10. Maranas C. D., Floudas C. A., J. Chem. Phys. 100, 1247 (1994); (10.1063/1.467236) / J. Chem. Phys. by Maranas C. D. (1994)
  11. Oresic M. Shalloway D. 101 9844 (1994); (10.1063/1.468485)
  12. Amara P., Straub J. E., J. Phys. Chem. 99, 14840 (1995); (10.1021/j100040a039) / J. Phys. Chem. by Amara P. (1995)
  13. Cvijovic D., Klinowski J., Science 267, 664 (1995). (10.1126/science.267.5198.664) / Science by Cvijovic D. (1995)
  14. Scheraga H. A., Biophys. Chem. 59, 329 (1996). (10.1016/0301-4622(95)00126-3) / Biophys. Chem. by Scheraga H. A. (1996)
  15. Niesse J. A., Mayne H. R., J. Chem. Phys. 105, 4700 (1996). (10.1063/1.472311) / J. Chem. Phys. by Niesse J. A. (1996)
  16. Hartke B., Chem. Phys. Lett. 258, 144 (1996). (10.1016/0009-2614(96)00629-X) / Chem. Phys. Lett. by Hartke B. (1996)
  17. Dittes F.-M., Phys. Rev. Lett. 76, 4651 (1996); (10.1103/PhysRevLett.76.4651) / Phys. Rev. Lett. by Dittes F.-M. (1996)
  18. Barhen J., Protopopescu V., Reister D., Science 276, 1094 (1997); (10.1126/science.276.5315.1094) / Science by Barhen J. (1997)
  19. Venkatesh P. K., Cohen M. H., Carr R. W., Dean A. M., Phys. Rev. E 55, 6219 (1997); (10.1103/PhysRevE.55.6219) / Phys. Rev. E by Venkatesh P. K. (1997)
  20. Stanton A. F., Bleil R. E., Kais S., J. Comput. Chem. 18, 594 (1997); (10.1002/(SICI)1096-987X(199703)18:4<594::AID-JCC12>3.0.CO;2-G) / J. Comput. Chem. by Stanton A. F. (1997)
  21. Huber G. A., McCammon J. A., Phys. Rev. E 55, 4822 (1997); (10.1103/PhysRevE.55.4822) / Phys. Rev. E by Huber G. A. (1997)
  22. Niesse J. A., Mayne H. R., J. Comp. Chem. 18, 1233 (1997) . (10.1002/(SICI)1096-987X(19970715)18:9<1233::AID-JCC11>3.0.CO;2-6) / J. Comp. Chem. by Niesse J. A. (1997)
  23. Schelstraete S., Verschelde H., J. Phys. Chem. A 101, 310 (1997). (10.1021/jp9621181) / J. Phys. Chem. A by Schelstraete S. (1997)
  24. Derreumaux P., J. Chem. Phys. 106, 5260 (1997). (10.1063/1.473525) / J. Chem. Phys. by Derreumaux P. (1997)
  25. Huber T., van Gunsteren W. F., J. Phys. Chem. A 102, 5937 (1998); (10.1021/jp9806258) / J. Phys. Chem. A by Huber T. (1998)
  26. Schneider J., Morgenstern I., Singer J. M., Phys. Rev. E 58, 5085 (1998); (10.1103/PhysRevE.58.5085) / Phys. Rev. E by Schneider J. (1998)
  27. Wenzel W., Hamacher K., Phys. Rev. Lett. 82, 3003 (1999). (10.1103/PhysRevLett.82.3003) / Phys. Rev. Lett. by Wenzel W. (1999)
  28. A number of books are also available for example R. Horst P. M. Pardalos and N. V. Thoai Introduction to Global Optimization (Kluwer Academic Dordrecht Netherlands 1995) and there is also a journal for specialists Journal of Global Optimization.
  29. D. J. Wales J. P. K. Doye A. Dullweber F. Y. Naumkin The Cambridge Cluster Database. Available at
  30. Wales D. J., J. Am. Chem. Soc. 112, 7908 (1990). (10.1021/ja00178a010) / J. Am. Chem. Soc. by Wales D. J. (1990)
  31. Parks E. K., et al., J. Chem. Phys. 107, 1861 (1997); (10.1063/1.474536) / J. Chem. Phys. by Parks E. K. (1997)
  32. 10.1002/adma.19960080513
  33. L. T. Wille Annual Reviews of Computational Physics VII D. Stauffer Ed. (World Scientific Singapore in press).
  34. Wawak R. J., Pillardy J., Liwo A., Gibson K. D., Scheraga H. A., J. Phys. Chem. A 102, 2904 (1998). (10.1021/jp972424u) / J. Phys. Chem. A by Wawak R. J. (1998)
  35. Doye J. P. K., Wales D. J., Phys. Rev. Lett. 80, 1357 (1998). (10.1103/PhysRevLett.80.1357) / Phys. Rev. Lett. by Doye J. P. K. (1998)
  36. Northby J. A., J. Chem. Phys. 87, 6166 (1987). (10.1063/1.453492) / J. Chem. Phys. by Northby J. A. (1987)
  37. Kirkpatrick S., Gelatt C. D., Vecchi M. P., Science 220, 671 (1983). (10.1126/science.220.4598.671) / Science by Kirkpatrick S. (1983)
  38. Wille L. T., Chem. Phys. Lett. 133, 405 (1987). (10.1016/0009-2614(87)87091-4) / Chem. Phys. Lett. by Wille L. T. (1987)
  39. Ma J., Hsu D., Straub J. E., J. Chem. Phys. 99, 4024 (1993); (10.1063/1.466098) / J. Chem. Phys. by Ma J. (1993)
  40. Ma J. Straub J. E. 101 533 (1994); (10.1063/1.468163)
  41. ; C. Tsoo and C. L. Brooks III ibid. 101 6405 (1994). (10.1063/1.468397)
  42. Stillinger F. H., Weber T. A., J. Stat. Phys. 52, 1429 (1988). (10.1007/BF01011658) / J. Stat. Phys. by Stillinger F. H. (1988)
  43. Piela L., Kostrowicki J., Scheraga H. A., J. Phys. Chem. 93, 3339 (1989). (10.1021/j100345a090) / J. Phys. Chem. by Piela L. (1989)
  44. Kostrowicki J. Piela L. Cherayil B. J. Scheraga H. A. 95 4113 (1991); (10.1021/j100163a040)
  45. ; F. H. Stillingerand D. K. Stillinger ibid. 93 6106 (1990); (10.1063/1.459003)
  46. Head-Gordon T., Stillinger F. H., Arrecis J., Proc. Natl. Acad. Sci. USA 88, 11076 (1991); (10.1073/pnas.88.24.11076) / Proc. Natl. Acad. Sci. USA by Head-Gordon T. (1991)
  47. Wawak R. J., Wimmer M. M., Scheraga H. A., J. Phys. Chem. 96, 5138 (1992); (10.1021/j100191a071) / J. Phys. Chem. by Wawak R. J. (1992)
  48. Scheraga H. A., Int. J. Quant. Chem. 42, 1529 (1992); (10.1002/qua.560420526) / Int. J. Quant. Chem. by Scheraga H. A. (1992)
  49. Pillardy J., Olszewski K. A., Piela L., J. Mol. Struct. (Theochem) 270, 277 (1992). (10.1016/0022-2860(92)85034-E) / J. Mol. Struct. (Theochem) by Pillardy J. (1992)
  50. Pillardy J., Piela L., J. Phys. Chem. 99, 11805 (1995). (10.1021/j100031a003) / J. Phys. Chem. by Pillardy J. (1995)
  51. Pillardy J., Piela L., J. Comp. Chem. 18, 2040 (1997); (10.1002/(SICI)1096-987X(199712)18:16<2040::AID-JCC8>3.0.CO;2-L) / J. Comp. Chem. by Pillardy J. (1997)
  52. Moret M. A. Pascutti P. G. Bisch P. M. Mundim K. C. 19 647 (1998). (10.1002/(SICI)1096-987X(19980430)19:6<647::AID-JCC6>3.0.CO;2-R)
  53. Doye J. P. K., Wales D. J., Berry R. S., J. Chem. Phys. 103, 4234 (1995). (10.1063/1.470729) / J. Chem. Phys. by Doye J. P. K. (1995)
  54. Wawak R. J., Gibson K. D., Liwo A., Scheraga H. A., Proc. Natl. Acad. Sci. USA 93, 1743 (1996). (10.1073/pnas.93.5.1743) / Proc. Natl. Acad. Sci. USA by Wawak R. J. (1996)
  55. J. H. Holland Adaptation in Natural and Artificial Systems (Univ. of Michigan Press Ann Arbor 1975).
  56. Rabow A. A., Scheraga H. A., Protein Sci. 5, 1800 (1996). (10.1002/pro.5560050906) / Protein Sci. by Rabow A. A. (1996)
  57. D. E. Goldberg Genetic Algorithms in Search Optimization and Machine Learning (Addison-Wesley Reading MA 1989).
  58. Deaven D. M., Ho K. M., Phys. Rev. Lett. 75, 288 (1995). (10.1103/PhysRevLett.75.288) / Phys. Rev. Lett. by Deaven D. M. (1995)
  59. Deaven D. M., Tit N., Morris J. R., Ho K. M., Chem. Phys. Lett. 256, 195 (1996). (10.1016/0009-2614(96)00406-X) / Chem. Phys. Lett. by Deaven D. M. (1996)
  60. Xue G., J. Glob. Opt. 1, 187 (1991). / J. Glob. Opt. by Xue G. (1991)
  61. Barrón C., Gómez S., Romero D., App. Math. Lett. 9, 75 (1996). (10.1016/0893-9659(96)00076-6) / App. Math. Lett. by Barrón C. (1996)
  62. Barrón C. Gómez S. Romero D. 10 25 (1997). (10.1016/S0893-9659(97)00078-5)
  63. Wales D. J., Doye J. P. K., J. Phys. Chem. A 101, 5111 (1997). (10.1021/jp970984n) / J. Phys. Chem. A by Wales D. J. (1997)
  64. An example computer code in Fortran can be downloaded from
  65. Li Z., Scheraga H. A., J. Mol. Struct. (Theochem) 179, 333 (1988). (10.1016/0166-1280(88)80133-7) / J. Mol. Struct. (Theochem) by Li Z. (1988)
  66. White R. P., Mayne H. R., Chem. Phys. Lett. 289, 463 (1998); (10.1016/S0009-2614(98)00431-X) / Chem. Phys. Lett. by White R. P. (1998)
  67. Wales D. J. Hodges M. P. 286 65 (1998); (10.1016/S0009-2614(98)00065-7)
  68. Doye J. P. K., Wales D. J., New J. Chem. 22, 733 (1998). (10.1039/a709249k) / New J. Chem. by Doye J. P. K. (1998)
  69. A. Markham and D. J. Wales unpublished work.
  70. Wolf M. D., Landman U., J. Phys. Chem. A 102, 6129 (1998). (10.1021/jp9814597) / J. Phys. Chem. A by Wolf M. D. (1998)
  71. Tsallis C., Stariolo D. A., Physica A 233, 395 (1996); (10.1016/S0378-4371(96)00271-3) / Physica A by Tsallis C. (1996)
  72. Andricioaei I., Straub J. E., J. Chem. Phys. 107, 9117 (1997); (10.1063/1.475203) / J. Chem. Phys. by Andricioaei I. (1997)
  73. Hansmann U. H. E., Okamoto Y., Phys. Rev. E 56, 2228 (1997). (10.1103/PhysRevE.56.2228) / Phys. Rev. E by Hansmann U. H. E. (1997)
  74. Doye J. P. K., Wales D. J., Z. Phys. D 40, 194 (1997); (10.1007/s004600050192) / Z. Phys. D by Doye J. P. K. (1997)
  75. Mousseau N., Barkema G. T., Phys. Rev. E 57, 2419 (1998). (10.1103/PhysRevE.57.2419) / Phys. Rev. E by Mousseau N. (1998)
  76. 10.1126/science.278.5337.404
  77. W. H. DeCamp in Crystal Growth of Organic Materials A. S. Myerson D. A. Green P. Meenan Eds. (ACS Proceedings Series American Chemical Society Washington DC 1996).
  78. Gavezzotti A., Acc. Chem. Res. 27, 309 (1994); (10.1021/ar00046a004) / Acc. Chem. Res. by Gavezzotti A. (1994)
  79. Gavezzotti A., J. Am. Chem. Soc. 113, 4622 (1991); (10.1021/ja00012a034) / J. Am. Chem. Soc. by Gavezzotti A. (1991)
  80. van Eijck B. P., Mooij W. T. M., Kroon J., Acta Crystallogr. B51, 99 (1995); (10.1107/S0108768194009651) / Acta Crystallogr. by van Eijck B. P. (1995)
  81. Gavezzotti A., Filippini G., J. Am. Chem. Soc. 118, 7153 (1996); (10.1021/ja9540637) / J. Am. Chem. Soc. by Gavezzotti A. (1996)
  82. Aakeroy C. B. Nieuwenhuyzen M. Price S. L. 120 8986 (1998) . (10.1021/ja981122i)
  83. Karfunkel H., Gdanitz R. J., J. Comput. Chem. 13, 1171 (1992). (10.1002/jcc.540131002) / J. Comput. Chem. by Karfunkel H. (1992)
  84. Gavezzotti A., Faraday Discuss. 106, 63 (1997). (10.1039/a701436h) / Faraday Discuss. by Gavezzotti A. (1997)
  85. Williams D. E., Acta Crystallogr. A52, 326 (1996). (10.1107/S0108767395016679) / Acta Crystallogr. by Williams D. E. (1996)
  86. Kariuki B. M., Serrano-González H., Johnston R. L., Harris K. D. M., Chem. Phys. Lett. 280, 189 (1997). (10.1016/S0009-2614(97)01156-1) / Chem. Phys. Lett. by Kariuki B. M. (1997)
  87. Warme P. K., Momany F. A., Rumball S. V., Tuttle R. W., Scheraga H. A., Biochemistry 13, 768 (1974); (10.1021/bi00701a020) / Biochemistry by Warme P. K. (1974)
  88. Jones T. A., Thirup S., EMBO J. 5, 819 (1986); (10.1002/j.1460-2075.1986.tb04287.x) / EMBO J. by Jones T. A. (1986)
  89. Clark D. A., Shirazi J., Rawlings C. J., Protein Eng. 4, 751 (1991); (10.1093/protein/4.7.751) / Protein Eng. by Clark D. A. (1991)
  90. Rooman M. J., Wodak S. J., Biochemistry 31, 10239 (1992); (10.1021/bi00157a010) / Biochemistry by Rooman M. J. (1992)
  91. Johnson M. S., Overington J. P., Blundell T. L., J. Mol. Biol. 231, 735 (1993). (10.1006/jmbi.1993.1323) / J. Mol. Biol. by Johnson M. S. (1993)
  92. Fisher D., Rice D., Bowie J. U., Eisenberg D., FASEB J. 10, 126 (1996); (10.1096/fasebj.10.1.8566533) / FASEB J. by Fisher D. (1996)
  93. Goldstein R., Luthey-Schulten Z. A., Wolynes P. G., Proc. Natl. Acad. Sci. USA 89, 9029 (1992) . (10.1073/pnas.89.19.9029) / Proc. Natl. Acad. Sci. USA by Goldstein R. (1992)
  94. Koretke K. K., Luthey-Schulten Z. A., Wolynes P. G., Protein Sci. 5, 1043 (1996). (10.1002/pro.5560050607) / Protein Sci. by Koretke K. K. (1996)
  95. Skolnick J., Koliński A., Brooks C. L., Godzik A., Rey A., Curr. Biol. 3, 414 (1993); (10.1016/0960-9822(93)90348-R) / Curr. Biol. by Skolnick J. (1993)
  96. Koliński A., Skolnick J., Proteins Struct. Funct. Genet. 18, 338 (1994); (10.1002/prot.340180405) / Proteins Struct. Funct. Genet. by Koliński A. (1994)
  97. Skolnick J., Koliński A., Ortiz A. R., J. Mol. Biol. 265, 217 (1997); (10.1006/jmbi.1996.0720) / J. Mol. Biol. by Skolnick J. (1997)
  98. Reva B. A., Finkelstein A. V., Skolnick J., Fold. Des. 3, 141 (1998). (10.1016/S1359-0278(98)00019-4) / Fold. Des. by Reva B. A. (1998)
  99. Pillardy J., Liwo A., Groth M., Scheraga H. A., J. Phys. Chem. 103, 7353 (1999). (10.1021/jp991014y) / J. Phys. Chem. by Pillardy J. (1999)
  100. Lee J., Scheraga H. A., Rackovsky S., J. Comput. Chem. 18, 1222 (1997). (10.1002/(SICI)1096-987X(19970715)18:9<1222::AID-JCC10>3.0.CO;2-7) / J. Comput. Chem. by Lee J. (1997)
  101. Liwo A., Lee J., Ripoll D. R., Pillardy J., Scheraga H. A., Proc. Natl. Acad. Sci. U.S.A. 96, 5482 (1999). (10.1073/pnas.96.10.5482) / Proc. Natl. Acad. Sci. U.S.A. by Liwo A. (1999)
  102. Lee J., et al., Biopolymers 46, 103 (1998). (10.1002/(SICI)1097-0282(199808)46:2<103::AID-BIP5>3.0.CO;2-Q) / Biopolymers by Lee J. (1998)
  103. Liwo A., et al., J. Comput. Chem. 19, 259 (1998). (10.1002/(SICI)1096-987X(199802)19:3<259::AID-JCC1>3.0.CO;2-S) / J. Comput. Chem. by Liwo A. (1998)
  104. Lee J., Liwo A., Scheraga H. A., Proc. Natl. Acad. Sci. U.S.A. 96, 2025 (1999). (10.1073/pnas.96.5.2025) / Proc. Natl. Acad. Sci. U.S.A. by Lee J. (1999)
  105. Third Community Wide Experiment on the Critical Assessment of Techniques for Protein Structure Prediction (CASP3). Available at
  106. D.J.W. is grateful to J. Doye for his comments on this manuscript and to the Royal Society and the Engineering and Physical Sciences Research Council for financial support. H.A.S. is grateful to J. Pillardy for help in writing parts of this manuscript and to the NIH and the NSF for financial support.
Dates
Type When
Created 23 years, 1 month ago (July 27, 2002, 5:42 a.m.)
Deposited 1 year, 7 months ago (Jan. 13, 2024, 3:56 a.m.)
Indexed 1 hour, 10 minutes ago (Sept. 2, 2025, 1:03 p.m.)
Issued 26 years ago (Aug. 27, 1999)
Published 26 years ago (Aug. 27, 1999)
Published Print 26 years ago (Aug. 27, 1999)
Funders 0

None

@article{Wales_1999, title={Global Optimization of Clusters, Crystals, and Biomolecules}, volume={285}, ISSN={1095-9203}, url={http://dx.doi.org/10.1126/science.285.5432.1368}, DOI={10.1126/science.285.5432.1368}, number={5432}, journal={Science}, publisher={American Association for the Advancement of Science (AAAS)}, author={Wales, David J. and Scheraga, Harold A.}, year={1999}, month=aug, pages={1368–1372} }