All recent successful methods for protein-protein docking are based on a multistage approach. Such an approach first applies a coarse grain search, and then isolates a number of regions (clusters) in the conformational space that need to be further explored. Final-stage exploration involves cluster refinement and cluster discrimination steps and poses several challenges: a multitude of clusters to explore, a very rugged energy landscape, and the need to account for the flexibility of the proteins and to incorporate entropy metrics in otherwise quite sophisticated energy potentials. The central goal of this proposal is to develop novel high-throughput optimization methods that can efficiently explore a multitude of conformational clusters andproduce high-quality predictions of the boundstructure. To that end, the work will leverage a new global optimization method developed by the proposing team, the Semi-Definite programming-based Underestimation (SOU) method, which can exploit the funnel-like shape of energy functions. Specific aims include: (1) the development of a final-stage optimization method that can efficiently explore conformational clusters; (2) the extension of the final-stage optimization method developed under Specific Aim 1 to allow full flexibility for the side-chains in the interface between the two proteins; and (3) the development of a cluster-discrimination algorithm that combines stochastic search approaches with estimates of funnel volume as a surrogatefor the entropy of complexes in the funnel. Novel aspects of the proposed work include: (i) the identification and efficient exploration of multi- dimensional energy funnels in the translation/orientational subspaces defined by the movement of the ligand towards the receptor, (ii) the coordination of translational and orientational movements of the ligand, which can potentially reveal information about dominant association pathways, (Hi) the development of an algorithm for fast re-packing of the interface side-chains using ideas from combinatorial optimization, and (iv) the incorporation of a surrogate entropy metric in cluster discrimination leveraging stochastic search approaches. This work will substantially improve upon docking results for relatively weak protein complexes and enable the flexible docking of larger proteins than what is possible today, resulting in a better understanding of processes such as metabolic control, signal transduction, and gene regulation.