It is proposed to develop two new algorithms for predicting the global minimum of energy surface functions in Rn arising in computational biology. Such functions are characterized by having a very large number of local minima, where the number typically grows exponentially with n. Energy surfaces of this type arise, for example, in protein-ligand docking in computational drug design. The location of the global minimum determines the most likely location of the docked ligand (drug) on the protein surface. This research is based on earlier results where it is assumed that the energy surface is basin-shaped, with many local minima. The energy surface was approximated by a convex quadratic function which underestimated a large number of local minima of the energy surface, and minimized the error in the L1 norm. It was shown that in many cases the unique minimum of this convex function was a good predictor of the global minimum of the energy surface. Intellectual Merit: We propose to build on this earlier work by developing two new and more efficient algorithms. The first will determine a quadratic underestimating function where the eigenvalues of the function Hessian satisfy specified lower and upper bounds. This includes the convex quadratic as a special case. In some important cases the energy surface, rather than being basin-shaped, contains a relatively small number of pronounced local minima, in addition to a large number relatively shallow local minima. The location of the pronounced local minima is not known, but one of them is the global minimum. The second proposed new algorithm will determine an underestimating function which consists of the sum of a small number of negative Gaussians. The location and shape of all Gaussians will be determined, as with the quadratic function, by minimizing the approximation error at a large number of local minima. The predicted global minimum point of the energy surface is then given by the location of that Gaussian with the minimum function value at its center. Impact: These two algorithms will be developed, implemented and tested on realistic computational models of protein-ligand docking energy surfaces, and made available, in accordance with University policy, to be used as one of the key components of a computer-aided drug design software package.
