Protein-protein interactions and especially docking of large proteins are not quite understood. We approach the docking problem by investigating geometric aspects of docking. We implemented an exhaustive search of all possible docking conformations in the 6-dimensional space of rigid motions. We choose an objective (score) function that reflects the number of atoms involved in the interaction. The problem is difficult from a computational point of view since the space is high-dimensional and a huge number of sampled rigid motions are needed to guarantee a good approximation of the maximum value of the score function. We were able to apply several techniques that speed up the exhaustive search and experiments show the successful docking results on 17 out of 19 tried protein complexes.

The success of exhaustive search is the base for the development of improved docking algorithms. A first improvement is achieved by designing an iterative algorithm that minimizes the sum of squared distances between pairs of atoms of two proteins involved in re-docking. One of the computational problems here is collision detection, which we solved by implementing a hierarchical data structure storing the atom spheres representing the proteins. A second improvement is based on methods from Morse theory used to find promising initial relative placements of the proteins. Specifically, we represent the surface of a molecule as a 2-manifold, define a Morse function on this surface, and compute the critical points (i.e., minima, maxima, and saddle points) of this Morse function. The goal is to find appropriate functions so that its critical points capture geometric information, such as pockets and protrusions, as well as biochemical information, such as the electrostatic potential. We then prioritize the critical points using the persistence algorithm of Edelsbrunner et. al. and use a top-down approach to separate promising from hopeless relative placements.

In parallel to our above approach to docking, we investigate the computational complexity of minimizing the Hausdorff distance between two sets of spheres under a group of motions. We have developed an efficient algorithm for the two-dimensional case allowing translations only. To extend this algorithm to three dimensions, we need to understand the complexity of the medial axis of a union of balls. Since exact algorithms for medial axes are slow, we have developed fast approximation algorithms. We have also studied the problem of minimizing the Hausdorff distance under the constraint of having no collisions, which has received little attention in the past. A drawback of the Hausdorff distance is its sensitivity to outliers, which we try to address by minimizing the average or the rms rather than the maximum distance. We have also developed fast approximation algorithms for those variants of the optimization problem.