This dissertation proposes new optimization algorithms targeting protein-protein docking which is an important class of problems in computational structural biology. The ultimate goal of docking methods is to predict the 3-dimensional structure of a stable protein-protein complex. We study two specific problems encountered in predictive docking of proteins. The first problem is Side-Chain Positioning (SCP), a central component of homology modeling and computational protein docking methods. We formulate SCP as a Maximum Weighted Independent Set (MWIS) problem on an appropriately constructed graph. Our formulation also considers the significant special structure of proteins that SCP exhibits for docking. We develop an approximate algorithm that solves a relaxation of MWIS and employ randomized estimation heuristics to obtain high-quality feasible solutions to the problem. The algorithm is fully distributed and can be implemented on multi-processor architectures. Our computational results on a benchmark set of protein complexes show that the accuracy of our approximate MWIS-based algorithm predictions is comparable with the results achieved by a state-of-the-art method that finds an exact solution to SCP. The second problem we target in this work is protein docking refinement. We propose two different methods to solve the refinement problem. The first approach is based on a Monte Carlo-Minimization (MCM) search to optimize rigid-body and side-chain conformations for binding. In particular, we study the impact of optimally positioning the side-chains in the interface region between two proteins in the process of binding. We report computational results showing that incorporating side-chain flexibility in docking provides substantial improvement in the quality of docked predictions compared to the rigid-body approaches. Further, we demonstrate that the inclusion of unbound side-chain conformers in the side-chain search introduces significant improvement in the performance of the docking refinement protocols. In the second approach, we propose a novel stochastic optimization algorithm based on Subspace Semi-Definite programming-based Underestimation (SSDU), which aims to solve protein docking and protein structure prediction. SSDU is based on underestimating the binding energy function in a permissive subspace of the space of rigid-body motions. We apply Principal Component Analysis (PCA) to determine the permissive subspace and reduce the dimensionality of the conformational search space. We consider the general class of convex polynomial underestimators, and formulate the problem of finding such underestimators as a Semi-Definite Programming (SDP) problem. Using these underestimators, we perform a biased sampling in the vicinity of the conformational regions where the energy function is at its global minimum. Moreover, we develop an exploration procedure based on density-based clustering to detect the near-native regions even when there are many local minima residing far from each other. We also incorporate a Model Selection procedure into SSDU to pick a predictive conformation. Testing our algorithm over a benchmark of protein complexes indicates that SSDU substantially improves the quality of docking refinement compared with existing methods.

<p>Ion permeation through voltage gated sodium channels is modulated by many drugs and toxins. However, the atomistic mechanisms of action of most these ligands are poorly understood. This study focuses on three compounds: a steroidal alkaloid batrachotoxin (BTX), a pyrethroid insecticide deltamethrin, and an alkylamide insecticide BTG 502, which bind to distinct but allosterically coupled receptor sites. BTX belongs to the class of the sodium channel agonists (activators), which cause persistent channel activation by inhibiting channel inactivation. Traditionally, BTX is believed to bind at the channel-lipid interface and allosterically modulate ion permeation through the channel. However, in the last decade, amino acid residues that affect BTX action have been found in the pore-facing inner helices of all four domains, suggesting that BTX binds in the channel pore (Tikhonov and Zhorov, <em>FEBS Letters</em> 2005). An alkylamide insecticide BTG 502 reduces sodium currents and antagonizes the action of BTX on cockroach sodium channels, suggesting that it also binds inside the pore. Conversely, pyrethroids bind at the lipid-exposed cavity formed by a short intracellular linker-helix IIS4-S5 and transmembrane helices IIS5 and IIIS6.</p> <p>In this study we first developed a new method of electrostatic-energy calculations, a new protocol of ligand docking, and tested this methodology on 60 ligand-protein complexes of known structure (Garden and Zhorov 2010). We then applied this methodology to rationalize effects of various mutations in the domain III inner helix of the cockroach sodium channel BgNav1.1 on the action of BTX, BTG 502 and deltamethrin. Our collaborators, Dr. Ke Dong et al. from Michigan State University, mutated all residues in the pore-lining helix of domain III (IIIS6) and found several new BTX and BTG 502 sensing residues. Using these data along with other published data on BTX- and deltamethrin-sensing residues as distance constrains, we docked BTX, BTG 502 and deltamethrin in a Kv1.2-based homology model of the open BgNav1.1 channel. We arrived at models, which are consistent with all currently available data on the action of the ligands. In the BTX-binding model, the toxin adopts a “horseshoe” conformation and binds in the channel pore with the horseshoe plane normal to the pore axis. In this binding mode BTX allows would allow ion permeation through the hydrophilic inner face of the horseshoe, and resist the activation-gate closure. Various BTX moieties interact with known BTX sensing residues. In particular, the tertiary ammonium group of BTX is engaged in cation-p interactions with the newly discovered BTX-sensing residue Phe³ⁱ¹⁶. In the BTG 502-binding model, the ligand wraps around IIIS6 making direct contacts with all known BTG 502-sending residues, including buried residues on the IIIS6 helix side, which does not face the pore. Deltamethrin binds within the cavity formed by the linker-helix IIS4-S5, the outer helix IIS5, and the inner helix IIIS6 at the interface between domains II and III, similar to the pyrethroid-binding mode predicted by others (O'Reilly, Khambay et al. 2006). Our study revealed a unique mode of action of BTX in which the agonists enables the ion permeation by forming a “channel within a channel”. We also found that the BTG 502 receptor site overlaps with receptors for BTX and deltamethrin, which are located in different parts of the channel.</p> / Doctor of Philosophy (PhD)