TITLE: A New Distributed Algorithm for the Side-chain Positioning Problem with
Applications in Macromolecular Docking
ABSTRACT: Proteins, as one of the most substantial elements of the cell, interact with each other or with other biochemical
compounds. These intercellular interactions play a central role in cellular functions such as cell signaling, ligand binding, metabolic control and gene regulation. Based on thermodynamics principles, proteins and other chemical compounds bind to each other in a
way that minimizes the Gibbs free energy of the complex. The prediction of the 3-dimensional (3-D) structure of a stable receptorligand complex is known as the protein-docking problem. Experimental techniques such as X-ray crystallography and Nuclear Magnetic Resonance can be used to predict such 3-D structures, but they are expensive, time-consuming and not universally applicable. Hence,
using computational methods to solve such problems has drawn a lot of attention.
Side-chain Positioning (SCP) is an important component of computational protein docking methods. Existing SCP methods and available software have been designed for protein folding applications where side-chain positioning is also important. As a result they do not take into account significant special structure that SCP for docking exhibits. We propose a new algorithm which poses SCP as a Maximum Weighted Independent Set (MWIS) problem on an appropriately constructed graph. We develop an approach which solves a relaxation of the MWIS and then rounds the solution to obtain a high-quality feasible solution to the problem. The algorithm is fully distributed and can be executed on a large network of processing nodes requiring only local information and message-passing between neighboring nodes. Motivated by the special structure in docking, we establish optimality guarantees for a certain class of graphs. Our results on a
benchmark set of enzyme-inhibitor protein complexes show that our predictions are close to the native structure. We also establish that
the use of our SCP algorithm produces superior docking results.
The proposed doctoral research will develop new stochastic global optimization methods targeting protein-protein docking problems. The method first applies Principle Component Analysis (PCA) to reduce the dimensionality of the docking data. In the context of docking
search, squeezing the search region is of great importance due to the large problem instances one has to tackle. Then we focus on
finding general convex quadratic underestimators to the binding energy function that is funnel-like. Finding the optimum underestimator
requires solving a semi-definite programming problem. The underestimator is used to bias sampling in the search region. Preliminary
results reveal a great potential in this approach and motivate more investigations in future research.
COMMITTEE: Advisor: Ioannis Paschalidis, SE/ECE; Sandor Vajda, SE/BME; Bobak Naser, SE/ECE; Pirooz Vakili, SE/ME
- 11:30 am on Tuesday, December 18, 2012
- 1:30 pm on Tuesday, December 18, 2012
- 15 Saint Mary's Street, Rm 105