SGER: Global Minimum Determination by Underestimation: Application to Protein-Ligand Docking

提出了两种新的算法来预测计算生物学中出现的Rn中能量表面函数的全局最小值。这种函数的特点是具有非常多的局部极小值，其数量通常随n呈指数增长。例如，在计算药物设计中的蛋白质配体对接中，就会出现这种类型的能量面。全局最小值的位置决定了停靠配体（药物）在蛋白质表面最可能的位置。这项研究是基于早期的结果，假设能量表面是盆状的，有许多局部极小值。用凸二次函数逼近能量面，低估了能量面大量的局部极小值，使theL1范数误差最小。结果表明，在许多情况下，该凸函数的唯一最小值可以很好地预测能量面的全局最小值。智力优势：我们建议在早期工作的基础上开发两种新的更有效的算法。第一个将确定一个二次低估函数，其中函数Hessian的特征值满足指定的下界和上界。这包括凸二次方程的一种特殊情况。在一些重要的情况下，能量表面不是盆状的，除了大量相对较浅的局部极小值外，还包含相对较少数量的明显的局部极小值。明显的局部极小值的位置尚不清楚，但其中一个是全局极小值。第二种提出的新算法将确定一个低估函数，该函数由少量负高斯函数的和组成。与二次函数一样，所有高斯函数的位置和形状将通过最小化大量局部最小值处的近似误差来确定。预测的能量表面的全局最小点由该高斯函数的最小值在其中心的位置给出。影响：这两种算法将在蛋白质-配体对接能量表面的实际计算模型上进行开发，实施和测试，并根据大学政策提供，作为计算机辅助药物设计软件包的关键组件之一。

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 theL1 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 quadraticas 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.