Protein-protein interactions play a central role in various aspects of the structural and functional organization of the cell. Protein docking, the computational prediction of such interactions, is crucial for better understanding cellular processes and provides valuable information for rational drug design.; Protein docking can be formulated as the problem of minimizing a noisy free energy function. All previous approaches use either systematic sampling or a Monte Carlo approach, neither accounting for the specific funnel-like shape of the free energy surface. This thesis introduces the Semi-Definite Underestimator (SDU) method, a stochastic global optimization method designed to take advantage of such funnel-like behavior. SDU operates in the conformational space of rigid body motions---the Euclidean group SE(3)---with side chain flexibility being allowed. The tightest convex quadratic underestimator is constructed based on a sampled set of local minima by solving a semi-definite programming problem and is used to bias sampling. This process is iterated until convergence. Under appropriate conditions SDU locates the global energy minimum with probability approaching one as the sample set of local minima grows. The parameterization of SE(3) is shown to have a significant impact on the shape of the binding energy funnels and the effectiveness of SDU. Two different parameterizations are introduced, one of which is inspired by protein association kinetics. Applications to a benchmark set of protein complexes and recent targets of a community-wide docking experiment are discussed. This algorithm delivers a more than twenty-fold computational gain compared to Monte Carlo methods.; The mechanism of protein-involved molecular interactions is also studied from another perspective. Analogous enzymes are evolutionarily independent but convergent products. A new method is developed to assess the molecular similarity of their binding sites. To optimally superimpose the two sets of structural descriptors spatially and physicochemically, the method performs an exhaustive search in the discretized SE(3) space using Fast Fourier Transforms. The method is applied to a number of analogous enzyme pairs. Advantages over the more traditional structure comparison method based on the maximum clique algorithm are discussed.
展开▼