Combinatorial docking approach for structure prediction of large proteins and multi-molecular assemblies

Protein folding and protein binding are similar processes. In both, structural units combinatorially associate with each other. In the case of folding, we mostly handle relatively small units, building blocks or domains, that are covalently linked. In the case of multi-molecular binding, the subunits are relatively large and are associated only by non-covalent bonds. Experimentally, the difficulty in the determination of the structures of such large assemblies increases with the complex size and the number of components it contains. Computationally, the prediction of the structures of multi-molecular complexes has largely not been addressed, probably owing to the magnitude of the combinatorial complexity of the problem. Current docking algorithms mostly target prediction of pairwise interactions. Here our goal is to predict the structures of multi-unit associations, whether these are chain-connected as in protein folding, or separate disjoint molecules in the assemblies. We assume that the structures of the single units are known, either through experimental determination or modeling. Our aim is to combinatorially assemble these units to predict their structure. To address this problem we have developed CombDock. CombDock is a combinatorial docking algorithm for the structural units assembly problem. Below, we briefly describe the algorithm and present examples of its various applications to folding and to multi-molecular assemblies. To test the robustness of the algorithm, we use inaccurate models of the structural units, derived either from crystal structures of unbound molecules or from modeling of the target sequences. The algorithm has been able to predict near-native arrangements of the input structural units in almost all of the cases, suggesting that a combinatorial approach can overcome the imperfect shape complementarity caused by the inaccuracy of the models. In addition, we further show that through a combinatorial docking strategy it is possible to enhance the predictions of pairwise interactions involved in a multi-molecular assembly.     

Multi-LZerD: multiple protein docking for asymmetric complexes

The tertiary structures of protein complexes provide a crucial insight about the molecular mechanisms that regulate their functions and assembly. However, solving protein complex structures by experimental methods is often more difficult than single protein structures. Here, we have developed a novel computational multiple protein docking algorithm, Multi‐LZerD, that builds models of multimeric complexes by effectively reusing pairwise docking predictions of component proteins. A genetic algorithm is applied to explore the conformational space followed by a structure refinement procedure. Benchmark on eleven hetero‐multimeric complexes resulted in near‐native conformations for all but one of them (a root mean square deviation smaller than 2.5Å). We also show that our method copes with unbound docking cases well, outperforming the methodology that can be directly compared with our approach. Multi‐LZerD was able to predict near‐native structures for multimeric complexes of various topologies.Proteins 2012; © 2012 Wiley Periodicals, Inc.     

Automated docking of peptides and proteins by using a genetic algorithm combined with a tabu search.

A genetic algorithm (GA) combined with a tabu search (TA) has been applied as a minimization method to rake the appropriate associated sites for some biomolecular systems. In our docking procedure, surface complementarity and energetic complementarity of a ligand with its receptor have been considered separately in a two-stage docking method. The first stage was to find a set of potential associated sites mainly based on surface complementarity using a genetic algorithm combined with a tabu search. This step corresponds with the process of finding the potential binding sites where pharmacophores will bind. In the second stage, several hundreds of GA minimization steps were performed for each associated site derived from the first stage mainly based on the energetic complementarity. After calculations for both of the two stages, we can offer several solutions of associated sites for every complex. In this paper, seven biomolecular systems, including five bound complexes and two unbound complexes, were chosen from the Protein Data Bank (PDB) to test our method. The calculated results were very encouraging-the hybrid minimization algorithm successfully reaches the correct solutions near the best binded modes for these protein complexes. The docking results not only predict the bound complexes very well, but also get a relatively accurate complexed conformation for unbound systems. For the five bound complexes, the results show that surface complementarity is enough to find the precise binding modes, the top solution from the tabu list generally corresponds to the correct binding mode. For the two unbound complexes, due to the conformational changes upon binding, it seems more difficult to get their correct binding conformations. The predicted results show that the correct binding mode also corresponds to a relatively large surface complementarity score. In these two test cases, the correct solution can be found in the top several solutions from the tabu list. For unbound complexes, the interaction energy from energetic complementarity is very important, it can be used to filter these solutions from the surface complementarity. After the evaluation of the energetic complementarity, the conformations and orientations close to the crystallographically determined structures are resolved. In most cases, the smallest root mean square distance (r.m.s.d.) from the GA combined with TA solutions is in a relatively small region. Our program of automatic docking is really a universal one among the procedures used for the theoretical study of molecular recognition.     

Conformational Transitions upon Ligand Binding: Holo-Structure Prediction from Apo Conformations

Biological function of proteins is frequently associated with the formation of complexes with small-molecule ligands. Experimental structure determination of such complexes at atomic resolution, however, can be time-consuming and costly. Computational methods for structure prediction of protein/ligand complexes, particularly docking, are as yet restricted by their limited consideration of receptor flexibility, rendering them not applicable for predicting protein/ligand complexes if large conformational changes of the receptor upon ligand binding are involved. Accurate receptor models in the ligand-bound state (holo structures), however, are a prerequisite for successful structure-based drug design. Hence, if only an unbound (apo) structure is available distinct from the ligand-bound conformation, structure-based drug design is severely limited. We present a method to predict the structure of protein/ligand complexes based solely on the apo structure, the ligand and the radius of gyration of the holo structure. The method is applied to ten cases in which proteins undergo structural rearrangements of up to 7.1 Å backbone RMSD upon ligand binding. In all cases, receptor models within 1.6 Å backbone RMSD to the target were predicted and close-to-native ligand binding poses were obtained for 8 of 10 cases in the top-ranked complex models. A protocol is presented that is expected to enable structure modeling of protein/ligand complexes and structure-based drug design for cases where crystal structures of ligand-bound conformations are not available.     

Protein flexibility in ligand docking and virtual screening to protein kinases

The main complicating factor in structure-based drug design is receptor rearrangement upon ligand binding (induced fit). It is the induced fit that complicates cross-docking of ligands from different ligand-receptor complexes. Previous studies have shown the necessity to include protein flexibility in ligand docking and virtual screening. Very few docking methods have been developed to predict the induced fit reliably and, at the same time, to improve on discriminating between binders and non-binders in the virtual screening process.We present an algorithm called the ICM-flexible receptor docking algorithm (IFREDA) to account for protein flexibility in virtual screening. By docking flexible ligands to a flexible receptor, IFREDA generates a discrete set of receptor conformations, which are then used to perform flexible ligand-rigid receptor docking and scoring. This is followed by a merging and shrinking step, where the results of the multiple virtual screenings are condensed to improve the enrichment factor. In the IFREDA approach, both side-chain rearrangements and essential backbone movements are taken into consideration, thus sampling adequately the conformational space of the receptor, even in cases of large loop movements.As a preliminary step, to show the importance of incorporating protein flexibility in ligand docking and virtual screening, and to validate the merging and shrinking procedure, we compiled an extensive small-scale virtual screening benchmark of 33 crystal structures of four different protein kinases sub-families (cAPK, CDK-2, P38 and LCK), where we obtained an enrichment factor fold-increase of 1.85±0.65 using two or three multiple experimental conformations. IFREDA was used in eight protein kinase complexes and was able to find the correct ligand conformation and discriminate the correct conformations from the “misdocked” conformations solely on the basis of energy calculation. Five of the generated structures were used in the small-scale virtual screening stage and, by merging and shrinking the results with those of the original structure, we show an enrichment factor fold increase of 1.89±0.60, comparable to that obtained using multiple experimental conformations.Our cross-docking tests on the protein kinase benchmark underscore the necessity of incorporating protein flexibility in both ligand docking and virtual screening. The methodology presented here will be extremely useful in cases where few or no experimental structures of complexes are available, while some binders are known.     

Protein docking using surface matching and supervised machine learning

Computational prediction of protein complex structures through docking offers a means to gain a mechanistic understanding of protein interactions that mediate biological processes. This is particularly important as the number of experimentally determined structures of isolated proteins exceeds the number of structures of complexes. A comprehensive docking procedure is described in which efficient sampling of conformations is achieved by matching surface normal vectors, fast filtering for shape complementarity, clustering by RMSD, and scoring the docked conformations using a supervised machine learning approach. Contacting residue pair frequencies, residue propensities, evolutionary conservation, and shape complementarity score for each docking conformation are used as input data to a Random Forest classifier. The performance of the Random Forest approach for selecting correctly docked conformations was assessed by cross-validation using a nonredundant benchmark set of X-ray structures for 93 heterodimer and 733 homodimer complexes. The single highest rank docking solution was the correct (near-native) structure for slightly more than one third of the complexes. Furthermore, the fraction of highly ranked correct structures was significantly higher than the overall fraction of correct structures, for almost all complexes. A detailed analysis of the difficult to predict complexes revealed that the majority of the homodimer cases were explained by incorrect oligomeric state annotation. Evolutionary conservation and shape complementarity score as well as both underrepresented and overrepresented residue types and residue pairs were found to make the largest contributions to the overall prediction accuracy. Finally, the method was also applied to docking unbound subunit structures from a previously published benchmark set.     

Protein-protein docking with simultaneous optimization of rigid-body displacement and side-chain conformations

Protein-protein docking algorithms provide a means to elucidate structural details for presently unknown complexes. Here, we present and evaluate a new method to predict protein-protein complexes from the coordinates of the unbound monomer components. The method employs a low-resolution, rigid-body, Monte Carlo search followed by simultaneous optimization of backbone displacement and side-chain conformations using Monte Carlo minimization. Up to 10(5) independent simulations are carried out, and the resulting "decoys" are ranked using an energy function dominated by van der Waals interactions, an implicit solvation model, and an orientation-dependent hydrogen bonding potential. Top-ranking decoys are clustered to select the final predictions. Small-perturbation studies reveal the formation of binding funnels in 42 of 54 cases using coordinates derived from the bound complexes and in 32 of 54 cases using independently determined coordinates of one or both monomers. Experimental binding affinities correlate with the calculated score function and explain the predictive success or failure of many targets. Global searches using one or both unbound components predict at least 25% of the native residue-residue contacts in 28 of the 32 cases where binding funnels exist. The results suggest that the method may soon be useful for generating models of biologically important complexes from the structures of the isolated components, but they also highlight the challenges that must be met to achieve consistent and accurate prediction of protein-protein interactions.     

A flexible docking scheme to explore the binding selectivity of PDZ domains

Modeling of protein binding site flexibility in molecular docking is still a challenging problem due to the large conformational space that needs sampling. Here, we propose a flexible receptor docking scheme: A dihedral restrained replica exchange molecular dynamics (REMD), where we incorporate the normal modes obtained by the Elastic Network Model (ENM) as dihedral restraints to speed up the search towards correct binding site conformations. To our knowledge, this is the first approach that uses ENM modes to bias REMD simulations towards binding induced fluctuations in docking studies. In our docking scheme, we first obtain the deformed structures of the unbound protein as initial conformations by moving along the binding fluctuation mode, and perform REMD using the ENM modes as dihedral restraints. Then, we generate an ensemble of multiple receptor conformations (MRCs) by clustering the lowest replica trajectory. Using ROSETTA LIGAND , we dock ligands to the clustered conformations to predict the binding pose and affinity. We apply this method to postsynaptic density‐95/Dlg/ZO‐1 (PDZ) domains; whose dynamics govern their binding specificity. Our approach produces the lowest energy bound complexes with an average ligand root mean square deviation of 0.36 Å. We further test our method on (i) homologs and (ii) mutant structures of PDZ where mutations alter the binding selectivity. In both cases, our approach succeeds to predict the correct pose and the affinity of binding peptides. Overall, with this approach, we generate an ensemble of MRCs that leads to predict the binding poses and specificities of a protein complex accurately.     

Constructing ensembles of flexible fragments in native proteins by iterative stochastic elimination is relevant to protein-protein interfaces

We investigate the extent to which ensembles of flexible fragments (FF), generated by our loop conformational search method, include conformations that are near experimental and reflect conformational changes that these FFs undergo when binary protein-protein complexes are formed. Twenty-eight FFs, which are located in protein-protein interfaces and have different conformations in the bound structure (BS) and unbound structure (UbS) were extracted. The conformational space of these fragments in the BS and UbS was explored with our method which is based on the iterative stochastic elimination (ISE) algorithm. Conformational search of BSs generated bound ensembles and conformational search of UbSs produced unbound ensembles. ISE samples conformations near experimental (less than 1.05 A root mean square deviation, RMSD) for 51 out of the 56 examined fragments in the bound and unbound ensembles. In 14 out of the 28 unbound fragments, it also samples conformations within 1.05 A from the BS in the unbound ensemble. Sampling the bound conformation in the unbound ensemble demonstrates the potential biological relevance of the predicted ensemble. The 10 lowest energy conformations are the best choice for docking experiments, compared with any other 10 conformations of the ensembles. We conclude that generating conformational ensembles for FFs with ISE is relevant to FF conformations in the UbS and BS. Forming ensembles of the isolated proteins with our method prior to docking represents more comprehensively their inherent flexibility and is expected to improve docking experiments compared with results obtained by docking only UbSs.     

TROSY and CRINEPT: NMR with large molecular and supramolecular structures in solution

TROSY and CRINEPT are new techniques for solution NMR studies of molecular and supramolecular structures. They allow the collection of high-resolution spectra of structures with molecular weights >100 kDa, significantly extending the range of macromolecular systems that can be studied by NMR in solution. TROSY has already been used to map protein-protein interfaces, to conduct structural studies on membrane proteins and to study nucleic acid conformations in multimolecular assemblies. These techniques will help us to investigate the conformational states of individual macromolecular components and will support de novo protein structure determination in large supramolecular structures.     

The relationship between the flexibility of proteins and their conformational states on forming protein-protein complexes with an application to protein-protein docking

We investigate the extent to which the conformational fluctuations of proteins in solution reflect the conformational changes that they undergo when they form binary protein-protein complexes. To do this, we study a set of 41 proteins that form such complexes and whose three-dimensional structures are known, both bound in the complex and unbound. We carry out molecular dynamics simulations of each protein, starting from the unbound structure, and analyze the resulting conformational fluctuations in trajectories of 5 ns in length, comparing with the structure in the complex. It is found that fluctuations take some parts of the molecules into regions of conformational space close to the bound state (or give information about it), but at no point in the simulation does each protein as whole sample the complete bound state. Subsequent use of conformations from a clustered MD ensemble in rigid-body docking is nevertheless partially successful when compared to docking the unbound conformations, as long as the unbound conformations are themselves included with the MD conformations and the whole globally rescored. For one key example where sub-domain motion is present, a ribonuclease inhibitor, principal components analysis of the MD was applied and was also able to produce conformations for docking that gave enhanced results compared to the unbound. The most significant finding is that core interface residues show a tendency to be less mobile (by size of fluctuation or entropy) than the rest of the surface even when the other binding partner is absent, and conversely the peripheral interface residues are more mobile. This surprising result, consistent across up to 40 of the 41 proteins, suggests different roles for these regions in protein recognition and binding, and suggests ways that docking algorithms could be improved by treating these regions differently in the docking process.     

A flexible docking approach for prediction of T cell receptor–peptide–MHC complexes

T cell receptors (TCRs) are immune proteins that specifically bind to antigenic molecules, which are often foreign peptides presented by major histocompatibility complex proteins (pMHCs), playing a key role in the cellular immune response. To advance our understanding and modeling of this dynamic immunological event, we assembled a protein–protein docking benchmark consisting of 20 structures of crystallized TCR/pMHC complexes for which unbound structures exist for both TCR and pMHC. We used our benchmark to compare predictive performance using several flexible and rigid backbone TCR/pMHC docking protocols. Our flexible TCR docking algorithm, TCRFlexDock, improved predictive success over the fixed backbone protocol, leading to near‐native predictions for 80% of the TCR/pMHC cases among the top 10 models, and 100% of the cases in the top 30 models. We then applied TCRFlexDock to predict the two distinct docking modes recently described for a single TCR bound to two different antigens, and tested several protein modeling scoring functions for prediction of TCR/pMHC binding affinities. This algorithm and benchmark should enable future efforts to predict, and design of uncharacterized TCR/pMHC complexes.     

Protein-protein docking with multiple residue conformations and residue substitutions

The protein docking problem has two major aspects: sampling conformations and orientations, and scoring them for fit. To investigate the extent to which the protein docking problem may be attributed to the sampling of ligand side‐chain conformations, multiple conformations of multiple residues were calculated for the uncomplexed (unbound) structures of protein ligands. These ligand conformations were docked into both the complexed (bound) and unbound conformations of the cognate receptors, and their energies were evaluated using an atomistic potential function. The following questions were considered: (1) does the ensemble of precalculated ligand conformations contain a structure similar to the bound form of the ligand? (2) Can the large number of conformations that are calculated be efficiently docked into the receptors? (3) Can near‐native complexes be distinguished from non‐native complexes? Results from seven test systems suggest that the precalculated ensembles do include side‐chain conformations similar to those adopted in the experimental complexes. By assuming additivity among the side chains, the ensemble can be docked in less than 12 h on a desktop computer. These multiconformer dockings produce near‐native complexes and also non‐native complexes. When docked against the bound conformations of the receptors, the near‐native complexes of the unbound ligand were always distinguishable from the non‐native complexes. When docked against the unbound conformations of the receptors, the near‐native dockings could usually, but not always, be distinguished from the non‐native complexes. In every case, docking the unbound ligands with flexible side chains led to better energies and a better distinction between near‐native and non‐native fits. An extension of this algorithm allowed for docking multiple residue substitutions (mutants) in addition to multiple conformations. The rankings of the docked mutant proteins correlated with experimental binding affinities. These results suggest that sampling multiple residue conformations and residue substitutions of the unbound ligand contributes to, but does not fully provide, a solution to the protein docking problem. Conformational sampling allows a classical atomistic scoring function to be used; such a function may contribute to better selectivity between near‐native and non‐native complexes. Allowing for receptor flexibility may further extend these results.     

The observation of the local ordering characteristics of spermidine-condensed DNA: atomic force microscopy and polarizing microscopy studies.

Condensation of DNA by multivalent cations can provide useful insights into the physical factors governing the folding and packaging of DNA in vivo. In this work, local ordered structures of spermidine-DNA complexes prepared from different DNA concentrations have been examined by using atomic force microscopy (AFM) and polarizing microscopy (PM). Two types (I and II) of DNA condensates, significantly different in sizes, were observed. It was found that for extremely dilute solutions (DNA concentrations around 1 ng/microl or below), the DNA molecules would collapse into toroidal structures with a volume equivalent to a single lambda-DNA (type I). In relatively dilute solutions (DNA concentrations between 1 and 10 ng/microll), a significantly larger structure of multimolecular toroids (circular and elliptical, type II) were formed, which were constructed by many fine particles. Measurements show that the average diameter of these fine particles was similar to the outer diameter of the monomolecular toroids observed in extremely dilute solutions, and the thickness of the multimolecular toroids had a distribution of multi-layers with height increments of 11 nm, indicating that the multimolecular toroidal structures have lamellar characteristics. Moreover, by enriching the DNA-spermidine complexes in very diluted solution, branch-like structures constructed by subunits were observed by using AFM. The analysis of the pellets in polarizing microscopy reveals a liquid-crystal-like pattern. These observations suggest that DNA-spermidine condensation could have multiple stages, which are very sensitive to the DNA and spermidine concentrations.     

Shape complementarity of protein-protein complexes at multiple resolutions

Biological complexes typically exhibit intermolecular interfaces of high shape complementarity. Many computational docking approaches use this surface complementarity as a guide in the search for predicting the structures of protein-protein complexes. Proteins often undergo conformational changes to create a highly complementary interface when associating. These conformational changes are a major cause of failure for automated docking procedures when predicting binding modes between proteins using their unbound conformations. Low resolution surfaces in which high frequency geometric details are omitted have been used to address this problem. These smoothed, or blurred, surfaces are expected to minimize the differences between free and bound structures, especially those that are due to side chain conformations or small backbone deviations. Despite the fact that this approach has been used in many docking protocols, there has yet to be a systematic study of the effects of such surface smoothing on the shape complementarity of the resulting interfaces. Here we investigate this question by computing shape complementarity of a set of 66 protein-protein complexes represented by multiresolution blurred surfaces. Complexed and unbound structures are available for these protein-protein complexes. They are a subset of complexes from a nonredundant docking benchmark selected for rigidity (i.e. the proteins undergo limited conformational changes between their bound and unbound states). In this work, we construct the surfaces by isocontouring a density map obtained by accumulating the densities of Gaussian functions placed at all atom centers of the molecule. The smoothness or resolution is specified by a Gaussian fall-off coefficient, termed "blobbyness." Shape complementarity is quantified using a histogram of the shortest distances between two proteins' surface mesh vertices for both the crystallographic complexes and the complexes built using the protein structures in their unbound conformation. The histograms calculated for the bound complex structures demonstrate that medium resolution smoothing (blobbyness = -0.9) can reproduce about 88% of the shape complementarity of atomic resolution surfaces. Complexes formed from the free component structures show a partial loss of shape complementarity (more overlaps and gaps) with the atomic resolution surfaces. For surfaces smoothed to low resolution (blobbyness = -0.3), we find more consistency of shape complementarity between the complexed and free cases. To further reduce bad contacts without significantly impacting the good contacts we introduce another blurred surface, in which the Gaussian densities of flexible atoms are reduced. From these results we discuss the use of shape complementarity in protein-protein docking.     

Electrostatic contributions to protein-protein interactions: fast energetic filters for docking and their physical basis

The methods of continuum electrostatics are used to calculate the binding free energies of a set of protein-protein complexes including experimentally determined structures as well as other orientations generated by a fast docking algorithm. In the native structures, charged groups that are deeply buried were often found to favor complex formation (relative to isosteric nonpolar groups), whereas in nonnative complexes generated by a geometric docking algorithm, they were equally likely to be stabilizing as destabilizing. These observations were used to design a new filter for screening docked conformations that was applied, in conjunction with a number of geometric filters that assess shape complementarity, to 15 antibody-antigen complexes and 14 enzyme-inhibitor complexes. For the bound docking problem, which is the major focus of this paper, native and near-native solutions were ranked first or second in all but two enzyme-inhibitor complexes. Less success was encountered for antibody-antigen complexes, but in all cases studied, the more complete free energy evaluation was able to identify native and near-native structures. A filter based on the enrichment of tyrosines and tryptophans in antibody binding sites was applied to the antibody-antigen complexes and resulted in a native and near-native solution being ranked first and second in all cases. A clear improvement over previously reported results was obtained for the unbound antibody-antigen examples as well. The algorithm and various filters used in this work are quite efficient and are able to reduce the number of plausible docking orientations to a size small enough so that a final more complete free energy evaluation on the reduced set becomes computationally feasible.     

Protein kinase CK2: a new view of an old molecular complex

Protein kinase CK2 (formerly known as casein kinase II) has been viewed traditionally as a stable heterotetrameric complex, but new analytical techniques are bringing a different picture into focus. The transient nature of this complex has been highlighted by the elucidation of its structure. Furthermore, analysis of the spatiotemporal organization of individual CK2 subunits in living cells has shown that they are dynamic and that they integrate into different multimolecular assemblies. These new studies give an additional dimension to the challenge of determining the cellular regulation of this protein kinase.     

Protein docking and complementarity

Predicting the structures of protein-protein complexes is a difficult problem owing to the topographical and thermodynamic complexity of these structures. Past efforts in this area have focussed on fitting the interacting proteins together using rigid body searches, usually with the conformations of the proteins as they occur in crystal structure complexes. Here we present work which uses a rigid body docking method to generate the structures of three known protein complexes, using both the bound and unbound conformations of the interacting molecules. In all cases we can regenerate the geometry of the crystal complexes to high accuracy. We also are able to find geometries that do not resemble the crystal structure but nevertheless are surprisingly reasonable both mechanistically and by some simple physical criteria. In contrast to previous work in this area, we find that simple methods for evaluating the complementarity at the protein-protein interface cannot distinguish between the configurations that resemble the crystal structure complex and those that do not. Methods that could not distinguish between such similar and dissimilar configurations include surface area burial, solvation free energy, packing and mechanism-based filtering. Evaluations of the total interaction energy and the electrostatic interaction energy of the complexes were somewhat better. Of the techniques that we tried, energy minimization distinguished most clearly between the "true" and "false" positives, though even here the energy differences were surprisingly small. We found the lowest total interaction energy from amongst all of the putative complexes generated by docking was always within 5 A root-mean-square of the crystallographic structure. There were, however, several putative complexes that were very dissimilar to the crystallographic structure but had energies that were close to that of the low energy structure. The magnitude of the error in energy calculations has not been established in macromolecular systems, and thus the reliability of the small differences in energy remains to be determined. The ability of this docking method to regenerate the crystallographic configurations of the interacting proteins using their unbound conformations suggests that it will be a useful tool in predicting the structures of unsolved complexes.