Geometric Techniques for Protein-Protein Docking

Proteins are ubiquitous and essential biomolecules that are involved in nearly all biological processes. Proteins function when they interact with other proteins to form complexes; however determining the structure of protein-protein complexes remains a difficult and lengthy process. There has been a long-standing interest in developing computational methods to predict protein complex structures to support and even as a possible alternative to the experimental methods; however the problem is still far from being solved.;The protein-protein docking problem refers to the problem of finding the conformation of a complex given that the two constituent proteins are known to interact and whose unbound structures are known.;We attack the problem from two aspects. Proteins undergo conformational changes in unbound docking. Ability to incorporate flexibility is the key in a successful unbound docking algorithm. In the first part of the thesis, we address the flexibility by sampling side-chain configurations to approximate the bound configuration. The results for our method indicate that in most of the cases the best configuration of an ensemble is close to the bound state (within 1 A) or it is closer to the bound than the unbound is. An unbound protein surface can be covered by overlapping patches. For each patch, an ensemble of representative configurations can be generated. Docking of two proteins can be performed by using ensembles of patches that constitute two proteins and therefore finding a conformation that is closer to the bound conformation.;In the second part of the thesis, we present a novel shape descriptor, called surface-histogram, for matching local protein shape complementarity. We design a matching function, for a pair of surface-histograms, that prefers gaps over overlaps in the absence of a perfect fit. Our efficient protein-protein docking algorithm, shDock, first finds local complementary shapes by matching surface-histograms, then filters the matches by a global collision filtering and finally ranks the candidates by a contact score which estimates the contact surface area between the two proteins. Our results demonstrate that surface-histograms are effective at identifying complementarity interface regions. We test shDock extensively on the ZDOCK benchmark 3.0. In comparison to four other state-of-the-art shape-based algorithms, shDOck demonstrated improved performance in both bound and unbound docking.