SDU: Docking refinement by semi-definite underestimation

SDU (Semi-Definite programming based Underestimation) is a stochastic global optimization method based on the assumption that the free energy, ΔG, is a funnel-like function within the region defined by each cluster (Paschalidis et al., 2007). Given a set of K local minima x₁,…,x_K of ΔG, we construct a convex quadratic function U(x) = x′Qx + b′x + c that underestimates ΔG at all local minima i.e., U(x_i) ≤ ΔG(x_i), i = 1, . . . ,K. The underestimator U(x) can be found by solving a semi-definite programming problem. Assuming that U(x) reflects the funnel-like behavior of free energy function, we call the global minimum x^P of U the “predictive conformation”, where x^P = −(1/2)Q^-1b. We bias sampling toward x^P by selecting points from the probability density function proportional to –U. The new points are used as starting states in local energy minimization, and then added to the set of local minima. High energy samples or those far from x^P are discarded. If there is no progress in reducing the minimum energy over several iterations then the algorithms is terminated.

In spite of the success of SDU as an optimizer for functions with funnel-shaped basins, its application to docking turned out to be more difficult than expected. SDU is effective for selecting moves in either translational or rotational subspaces (Paschalidis et al., 2006). However, the direct application of SDU in the space of rotations and translations fails to yield useful underestimators. Alternating searches in rotational and translational subspaces yields a feasible but inefficient algorithm. We have substantially improved performance by separately optimizing the center-to-center distance and describing SE(3) in terms of five angles. It is potentially important that this strategy samples encounter complexes, and hence it is reminiscent of the model of molecular association through a series of micro-collisions.