language: en

[DIMACS Series in Discrete Mathematics and Theoretical Computer Science Volume 00, 19xx]

Global Optimization Methods for Protein Folding Problems

Richard H. Byrd, Elizabeth Eskow, Andre van der Hoek, Robert B. Schnabel, Chung-Shang Shao, and Zhihong Zou

Abstract. The problem of finding the naturally occurring structure of a protein is believed to correspond to minimizing the free, or potential, energy of the protein. This is generally a very difficult global optimization problem, with a large number of parameters and a huge number of local minimizers including many with function values near that of the global minimizer. This paper presents a new global optimization method for such problems. The method consists of an initial phase that locates some reasonably low local minimizers of the energy function, followed by the main phase that progresses from the best current local minimizers to even lower local minimizers. The method combines portions that work on small subsets of the parameters, including small-scale global optimizations using stochastic methods, with local minimizations involving all the parameters. In computational tests on the protein polyalanine with up to 58 amino acids (116 internal parameters), the method appears to be very successful in finding the lowest energy structures. The largest case is particularly significant because the lowest energy structures that are found include ones that exhibit interesting tertiary as opposed to just secondary structure.

1. Introduction