Prediction of Multimolecular Assemblies by Multiple Docking

Structural basis for Mis18 complex assembly and its implications for centromere maintenance

The centromere, defined by the enrichment of CENP-A (a Histone H3 variant) containing nucleosomes, is a specialised chromosomal locus that acts as a microtubule attachment site. To preserve centromere identity, CENP-A levels must be maintained through active CENP-A loading during the cell cycle. A central player mediating this process is the Mis18 complex (Mis18α, Mis18β and Mis18BP1), which recruits the CENP-A-specific chaperone HJURP to centromeres for CENP-A deposition. Here, using a multi-pronged approach, we characterise the structure of the Mis18 complex and show that multiple hetero- and homo-oligomeric interfaces facilitate the hetero-octameric Mis18 complex assembly composed of 4 Mis18α, 2 Mis18β and 2 Mis18BP1. Evaluation of structure-guided/separation-of-function mutants reveals structural determinants essential for cell cycle controlled Mis18 complex assembly and centromere maintenance. Our results provide new mechanistic insights on centromere maintenance, highlighting that while Mis18α can associate with centromeres and deposit CENP-A independently of Mis18β, the latter is indispensable for the optimal level of CENP-A loading required for preserving the centromere identity.

Integrative modeling meets deep learning: Recent advances in modeling protein assemblies

Recent progress in protein structure prediction based on deep learning revolutionized the field of Structural Biology. Beyond single proteins, it also enabled high-throughput prediction of structures of protein-protein interactions. Despite the success in predicting complex structures, large macromolecular assemblies still require specialized approaches. Here we describe recent advances in modeling macromolecular assemblies using integrative and hierarchical approaches. We highlight applications that predict protein-protein interactions and challenges in modeling complexes based on the interaction networks, including the prediction of complex stoichiometry and heterogeneity.

CombFold: predicting structures of large protein assemblies using a combinatorial assembly algorithm and AlphaFold2

Deep learning models, such as AlphaFold2 and RosettaFold, enable high-accuracy protein structure prediction. However, large protein complexes are still challenging to predict due to their size and the complexity of interactions between multiple subunits. Here we present CombFold, a combinatorial and hierarchical assembly algorithm for predicting structures of large protein complexes utilizing pairwise interactions between subunits predicted by AlphaFold2. CombFold accurately predicted (TM-score >0.7) 72% of the complexes among the top-10 predictions in two datasets of 60 large, asymmetric assemblies. Moreover, the structural coverage of predicted complexes was 20% higher compared to corresponding Protein Data Bank entries. We applied the method on complexes from Complex Portal with known stoichiometry but without known structure and obtained high-confidence predictions. CombFold supports the integration of distance restraints based on crosslinking mass spectrometry and fast enumeration of possible complex stoichiometries. CombFold's high accuracy makes it a promising tool for expanding structural coverage beyond monomeric proteins.

Predicting structures of large protein assemblies using combinatorial assembly algorithm and AlphaFold2

Deep learning models, such as AlphaFold2 and RosettaFold, enable high-accuracy protein structure prediction. However, large protein complexes are still challenging to predict due to their size and the complexity of interactions between multiple subunits. Here we present CombFold, a combinatorial and hierarchical assembly algorithm for predicting structures of large protein complexes utilizing pairwise interactions between subunits predicted by AlphaFold2. CombFold accurately predicted (TM-score > 0.7) 72% of the complexes among the Top-10 predictions in two datasets of 60 large, asymmetric assemblies. Moreover, the structural coverage of predicted complexes was 20% higher compared to corresponding PDB entries. We applied the method on complexes from Complex Portal with known stoichiometry but without known structure and obtained high-confidence predictions. CombFold supports the integration of distance restraints based on crosslinking mass spectrometry and fast enumeration of possible complex stoichiometries. CombFold's high accuracy makes it a promising tool for expanding structural coverage beyond monomeric proteins.

Predicting the structure of large protein complexes using AlphaFold and Monte Carlo tree search

AlphaFold can predict the structure of single- and multiple-chain proteins with very high accuracy. However, the accuracy decreases with the number of chains, and the available GPU memory limits the size of protein complexes which can be predicted. Here we show that one can predict the structure of large complexes starting from predictions of subcomponents. We assemble 91 out of 175 complexes with 10–30 chains from predicted subcomponents using Monte Carlo tree search, with a median TM-score of 0.51. There are 30 highly accurate complexes (TM-score ≥0.8, 33% of complete assemblies). We create a scoring function, mpDockQ, that can distinguish if assemblies are complete and predict their accuracy. We find that complexes containing symmetry are accurately assembled, while asymmetrical complexes remain challenging. The method is freely available and accesible as a Colab notebook https://colab.research.google.com/github/patrickbryant1/MoLPC/blob/master/MoLPC.ipynb.

The accuracy of AlphaFold decreases with the number of protein chains and the available GPU memory limits the size of protein complexes that can be predicted. Here, the authors show that complexes with 10–30 chains can be assembled from predicted subcomponents using Monte Carlo tree search.

RL-MLZerD: Multimeric protein docking using reinforcement learning

Numerous biological processes in a cell are carried out by protein complexes. To understand the molecular mechanisms of such processes, it is crucial to know the quaternary structures of the complexes. Although the structures of protein complexes have been determined by biophysical experiments at a rapid pace, there are still many important complex structures that are yet to be determined. To supplement experimental structure determination of complexes, many computational protein docking methods have been developed; however, most of these docking methods are designed only for docking with two chains. Here, we introduce a novel method, RL-MLZerD, which builds multiple protein complexes using reinforcement learning (RL). In RL-MLZerD a multi-chain assembly process is considered as a series of episodes of selecting and integrating pre-computed pairwise docking models in a RL framework. RL is effective in correctly selecting plausible pairwise models that fit well with other subunits in a complex. When tested on a benchmark dataset of protein complexes with three to five chains, RL-MLZerD showed better modeling performance than other existing multiple docking methods under different evaluation criteria, except against AlphaFold-Multimer in unbound docking. Also, it emerged that the docking order of multi-chain complexes can be naturally predicted by examining preferred paths of episodes in the RL computation.

Modeling Perturbations in Protein Filaments at the Micro and Meso Scale Using NAMD and PTools/Heligeom

Protein filaments are dynamic entities that respond to external stimuli by slightly or substantially modifying the internal binding geometries between successive protomers. This results in overall changes in the filament architecture, which are difficult to model due to the helical character of the system. Here, we describe how distortions in RecA nucleofilaments and their consequences on the filament-DNA and bound DNA-DNA interactions at different stages of the homologous recombination process can be modeled using the PTools/Heligeom software and subsequent molecular dynamics simulation with NAMD. Modeling methods dealing with helical macromolecular objects typically rely on symmetric assemblies and take advantage of known symmetry descriptors. Other methods dealing with single objects, such as MMTK or VMD, do not integrate the specificities of regular assemblies. By basing the model building on binding geometries at the protomer-protomer level, PTools/Heligeom frees the building process from a priori knowledge of the system topology and enables irregular architectures and symmetry disruption to be accounted for. Graphical abstract: Model of ATP hydrolysis-induced distortions in the recombinant nucleoprotein, obtained by combining RecA-DNA and two RecA-RecA binding geometries.

Computational structure modeling for diverse categories of macromolecular interactions

Computational protein-protein docking is one of the most intensively studied topics in structural bioinformatics. The field has made substantial progress through over three decades of development. The development began with methods for rigid-body docking of two proteins, which have now been extended in different directions to cover the various macromolecular interactions observed in a cell. Here, we overview the recent developments of the variations of docking methods, including multiple protein docking, peptide-protein docking, and disordered protein docking methods.

Modeling of Multimolecular Complexes

Macromolecular complexes play a key role in cellular function. Predicting the structure and dynamics of these complexes is one of the key challenges in structural biology. Docking applications have traditionally been used to predict pairwise interactions between proteins. However, few methods exist for modeling multi-protein assemblies. Here we present two methods, CombDock and DockStar, that can predict multi-protein assemblies starting from subunit structural models. CombDock can assemble subunits without any assumptions about the pairwise interactions between subunits, while DockStar relies on the interaction graph or, alternatively, a homology model or a cryo-electron microscopy (EM) density map of the entire complex. We demonstrate the two methods using RNA polymerase II with 12 subunits and TRiC/CCT chaperonin with 16 subunits.

Multiscale Visual Drilldown for the Analysis of Large Ensembles of Multi-Body Protein Complexes

When studying multi-body protein complexes, biochemists use computational tools that can suggest hundreds or thousands of their possible spatial configurations. However, it is not feasible to experimentally verify more than only a very small subset of them. In this paper, we propose a novel multiscale visual drilldown approach that was designed in tight collaboration with proteomic experts, enabling a systematic exploration of the configuration space. Our approach takes advantage of the hierarchical structure of the data - from the whole ensemble of protein complex configurations to the individual configurations, their contact interfaces, and the interacting amino acids. Our new solution is based on interactively linked 2D and 3D views for individual hierarchy levels. At each level, we offer a set of selection and filtering operations that enable the user to narrow down the number of configurations that need to be manually scrutinized. Furthermore, we offer a dedicated filter interface, which provides the users with an overview of the applied filtering operations and enables them to examine their impact on the explored ensemble. This way, we maintain the history of the exploration process and thus enable the user to return to an earlier point of the exploration. We demonstrate the effectiveness of our approach on two case studies conducted by collaborating proteomic experts.

DynBench3D, a Web-Resource to Dynamically Generate Benchmark Sets of Large Heteromeric Protein Complexes

Multi-protein machines are responsible for most cellular tasks, and many efforts have been invested in the systematic identification and characterization of thousands of these macromolecular assemblies. However, unfortunately, the (quasi) atomic details necessary to understand their function are available only for a tiny fraction of the known complexes. The computational biology community is developing strategies to integrate structural data of different nature, from electron microscopy to X-ray crystallography, to model large molecular machines, as it has been done for individual proteins and interactions with remarkable success. However, unlike for binary interactions, there is no reliable gold-standard set of three-dimensional (3D) complexes to benchmark the performance of these methodologies and detect their limitations. Here, we present a strategy to dynamically generate non-redundant sets of 3D heteromeric complexes with three or more components. By changing the values of sequence identity and component overlap between assemblies required to define complex redundancy, we can create sets of representative complexes with known 3D structure (i.e., target complexes). Using an identity threshold of 20% and imposing a fraction of component overlap of <0.5, we identify 495 unique target complexes, which represent a real non-redundant set of heteromeric assemblies with known 3D structure. Moreover, for each target complex, we also identify a set of assemblies, of varying degrees of identity and component overlap, that can be readily used as input in a complex modeling exercise (i.e., template subcomplexes). We hope that resources like this will significantly help the development and progress assessment of novel methodologies, as docking benchmarks and blind prediction contests did. The interactive resource is accessible at https://DynBench3D.irbbarcelona.org.

Modeling the assembly order of multimeric heteroprotein complexes

Protein-protein interactions are the cornerstone of numerous biological processes. Although an increasing number of protein complex structures have been determined using experimental methods, relatively fewer studies have been performed to determine the assembly order of complexes. In addition to the insights into the molecular mechanisms of biological function provided by the structure of a complex, knowing the assembly order is important for understanding the process of complex formation. Assembly order is also practically useful for constructing subcomplexes as a step toward solving the entire complex experimentally, designing artificial protein complexes, and developing drugs that interrupt a critical step in the complex assembly. There are several experimental methods for determining the assembly order of complexes; however, these techniques are resource-intensive. Here, we present a computational method that predicts the assembly order of protein complexes by building the complex structure. The method, named Path-LzerD, uses a multimeric protein docking algorithm that assembles a protein complex structure from individual subunit structures and predicts assembly order by observing the simulated assembly process of the complex. Benchmarked on a dataset of complexes with experimental evidence of assembly order, Path-LZerD was successful in predicting the assembly pathway for the majority of the cases. Moreover, when compared with a simple approach that infers the assembly path from the buried surface area of subunits in the native complex, Path-LZerD has the strong advantage that it can be used for cases where the complex structure is not known. The path prediction accuracy decreased when starting from unbound monomers, particularly for larger complexes of five or more subunits, for which only a part of the assembly path was correctly identified. As the first method of its kind, Path-LZerD opens a new area of computational protein structure modeling and will be an indispensable approach for studying protein complexes.

In silico modeling of the cryptic E2∼ubiquitin-binding site of E6-associated protein (E6AP)/UBE3A reveals the mechanism of polyubiquitin chain assembly

To understand the mechanism for assembly of Lys⁴⁸-linked polyubiquitin degradation signals, we previously demonstrated that the E6AP/UBE3A ligase harbors two functionally distinct E2∼ubiquitin-binding sites: a high-affinity Site 1 required for E6AP Cys⁸²⁰∼ubiquitin thioester formation and a canonical Site 2 responsible for subsequent chain elongation. Ordered binding to Sites 1 and 2 is here revealed by observation of UbcH7∼ubiquitin-dependent substrate inhibition of chain formation at micromolar concentrations. To understand substrate inhibition, we exploited the PatchDock algorithm to model in silico UbcH7∼ubiquitin bound to Site 1, validated by chain assembly kinetics of selected point mutants. The predicted structure buries an extensive solvent-excluded surface bringing the UbcH7∼ubiquitin thioester bond within 6 Å of the Cys⁸²⁰ nucleophile. Modeling onto the active E6AP trimer suggests that substrate inhibition arises from steric hindrance between Sites 1 and 2 of adjacent subunits. Confirmation that Sites 1 and 2 function in trans was demonstrated by examining the effect of E6APC820A on wild-type activity and single-turnover pulse-chase kinetics. A cyclic proximal indexation model proposes that Sites 1 and 2 function in tandem to assemble thioester-linked polyubiquitin chains from the proximal end attached to Cys⁸²⁰ before stochastic en bloc transfer to the target protein. Non-reducing SDS-PAGE confirms assembly of the predicted Cys⁸²⁰-linked ¹²⁵I-polyubiquitin thioester intermediate. Other studies suggest that Glu⁵⁵⁰ serves as a general base to generate the Cys⁸²⁰ thiolate within the low dielectric binding interface and Arg⁵⁰⁶ functions to orient Glu⁵⁵⁰ and to stabilize the incipient anionic transition state during thioester exchange.

PRISM-EM: template interface-based modelling of multi-protein complexes guided by cryo-electron microscopy density maps

The structures of protein assemblies are important for elucidating cellular processes at the molecular level. Three-dimensional electron microscopy (3DEM) is a powerful method to identify the structures of assemblies, especially those that are challenging to study by crystallography. Here, a new approach, PRISM-EM, is reported to computationally generate plausible structural models using a procedure that combines crystallographic structures and density maps obtained from 3DEM. The predictions are validated against seven available structurally different crystallographic complexes. The models display mean deviations in the backbone of <5 Å. PRISM-EM was further tested on different benchmark sets; the accuracy was evaluated with respect to the structure of the complex, and the correlation with EM density maps and interface predictions were evaluated and compared with those obtained using other methods. PRISM-EM was then used to predict the structure of the ternary complex of the HIV-1 envelope glycoprotein trimer, the ligand CD4 and the neutralizing protein m36.

Principles and Overview of Sampling Methods for Modeling Macromolecular Structure and Dynamics

Investigation of macromolecular structure and dynamics is fundamental to understanding how macromolecules carry out their functions in the cell. Significant advances have been made toward this end in silico, with a growing number of computational methods proposed yearly to study and simulate various aspects of macromolecular structure and dynamics. This review aims to provide an overview of recent advances, focusing primarily on methods proposed for exploring the structure space of macromolecules in isolation and in assemblies for the purpose of characterizing equilibrium structure and dynamics. In addition to surveying recent applications that showcase current capabilities of computational methods, this review highlights state-of-the-art algorithmic techniques proposed to overcome challenges posed in silico by the disparate spatial and time scales accessed by dynamic macromolecules. This review is not meant to be exhaustive, as such an endeavor is impossible, but rather aims to balance breadth and depth of strategies for modeling macromolecular structure and dynamics for a broad audience of novices and experts.

Principles of assembly reveal a periodic table of protein complexes

Structural insights into protein complexes have had a broad impact on our understanding of biological function and evolution. In this work, we sought a comprehensive understanding of the general principles underlying quaternary structure organization in protein complexes. We first examined the fundamental steps by which protein complexes can assemble, using experimental and structure-based characterization of assembly pathways. Most assembly transitions can be classified into three basic types, which can then be used to exhaustively enumerate a large set of possible quaternary structure topologies. These topologies, which include the vast majority of observed protein complex structures, enable a natural organization of protein complexes into a periodic table. On the basis of this table, we can accurately predict the expected frequencies of quaternary structure topologies, including those not yet observed. These results have important implications for quaternary structure prediction, modeling, and engineering.

Performance of ZDOCK in CAPRI rounds 20-26

We report the performance of our approaches for protein-protein docking and interface analysis in CAPRI rounds 20-26. At the core of our pipeline was the ZDOCK program for rigid-body protein-protein docking. We then reranked the ZDOCK predictions using the ZRANK or IRAD scoring functions, pruned and analyzed energy landscapes using clustering, and analyzed the docking results using our interface prediction approach RCF. When possible, we used biological information from the literature to apply constraints to the search space during or after the ZDOCK runs. For approximately half of the standard docking challenges we made at least one prediction that was acceptable or better. For the scoring challenges we made acceptable or better predictions for all but one target. This indicates that our scoring functions are generally able to select the correct binding mode.

Unraveling the molecular architecture of a G protein-coupled receptor/β-arrestin/Erk module complex

β-arrestins serve as signaling scaffolds downstream of G protein-coupled receptors, and thus play a crucial role in a plethora of cellular processes. Although it is largely accepted that the ability of β-arrestins to interact simultaneously with many protein partners is key in G protein-independent signaling of GPCRs, only the precise knowledge of these multimeric arrangements will allow a full understanding of the dynamics of these interactions and their functional consequences. However, current experimental procedures for the determination of the three-dimensional structures of protein-protein complexes are not well adapted to analyze these short-lived, multi-component assemblies. We propose a model of the receptor/β-arrestin/Erk1 signaling module, which is consistent with most of the available experimental data. Moreover, for the β-arrestin/Raf1 and the β-arrestin/ERK interactions, we have used the model to design interfering peptides and shown that they compete with both partners, hereby demonstrating the validity of the predicted interaction regions.

DockStar: a novel ILP-based integrative method for structural modeling of multimolecular protein complexes

MOTIVATION

Atomic resolution modeling of large multimolecular assemblies is a key task in Structural Cell Biology. Experimental techniques can provide atomic resolution structures of single proteins and small complexes, or low resolution data of large multimolecular complexes.

RESULTS

We present a novel integrative computational modeling method, which integrates both low and high resolution experimental data. The algorithm accepts as input atomic resolution structures of the individual subunits obtained from X-ray, NMR or homology modeling, and interaction data between the subunits obtained from mass spectrometry. The optimal assembly of the individual subunits is formulated as an Integer Linear Programming task. The method was tested on several representative complexes, both in the bound and unbound cases. It placed correctly most of the subunits of multimolecular complexes of up to 16 subunits and significantly outperformed the CombDock and Haddock multimolecular docking methods.

AVAILABILITY AND IMPLEMENTATION

http://bioinfo3d.cs.tau.ac.il/DockStar

CONTACT

naamaamir@mail.tau.ac.il or wolfson@tau.ac.il

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.

An integrative approach to the study of filamentous oligomeric assemblies, with application to RecA

Oligomeric macromolecules in the cell self-organize into a wide variety of geometrical motifs such as helices, rings or linear filaments. The recombinase proteins involved in homologous recombination present many such assembly motifs. Here, we examine in particular the polymorphic characteristics of RecA, the most studied member of the recombinase family, using an integrative approach that relates local modes of monomer/monomer association to the global architecture of their screw-type organization. In our approach, local modes of association are sampled via docking or Monte Carlo simulations. This enables shedding new light on fiber morphologies that may be adopted by the RecA protein. Two distinct RecA helical morphologies, the so-called "extended" and "compressed" forms, are known to play a role in homologous recombination. We investigate the variability within each form in terms of helical parameters and steric accessibility. We also address possible helical discontinuities in RecA filaments due to multiple monomer-monomer association modes. By relating local interface organization to global filament morphology, the strategies developed here to study RecA self-assembly are particularly well suited to other DNA-binding proteins and to filamentous protein assemblies in general.

Structure, dynamics, assembly, and evolution of protein complexes

The assembly of individual proteins into functional complexes is fundamental to nearly all biological processes. In recent decades, many thousands of homomeric and heteromeric protein complex structures have been determined, greatly improving our understanding of the fundamental principles that control symmetric and asymmetric quaternary structure organization. Furthermore, our conception of protein complexes has moved beyond static representations to include dynamic aspects of quaternary structure, including conformational changes upon binding, multistep ordered assembly pathways, and structural fluctuations occurring within fully assembled complexes. Finally, major advances have been made in our understanding of protein complex evolution, both in reconstructing evolutionary histories of specific complexes and in elucidating general mechanisms that explain how quaternary structure tends to evolve. The evolution of quaternary structure occurs via changes in self-assembly state or through the gain or loss of protein subunits, and these processes can be driven by both adaptive and nonadaptive influences.

Modeling protein assemblies in the proteome

Most (if not all) proteins function when associated in multimolecular assemblies. Attaining the structures of protein assemblies at the atomic scale is an important aim of structural biology. Experimentally, structures are increasingly available, and computations can help bridge the resolution gap between high- and low-resolution scales. Existing computational methods have made substantial progress toward this aim; however, current approaches are still limited. Some involve manual adjustment of experimental data; some are automated docking methods, which are computationally expensive and not applicable to large-scale proteome studies; and still others exploit the symmetry of the complexes and thus are not applicable to nonsymmetrical complexes. Our study aims to take steps toward overcoming these limitations. We have developed a strategy for the construction of protein assemblies computationally based on binary interactions predicted by a motif-based protein interaction prediction tool, PRISM (Protein Interactions by Structural Matching). Previously, we have shown its power in predicting pairwise interactions. Here we take a step toward multimolecular assemblies, reflecting the more prevalent cellular scenarios. With this method we are able to construct homo-/hetero-complexes and symmetric/asymmetric complexes without a limitation on the number of components. The method considers conformational changes and is applicable to large-scale studies. We also exploit electron microscopy density maps to select a solution from among the predictions. Here we present the method, illustrate its results, and highlight its current limitations.

Pairwise and multimeric protein-protein docking using the LZerD program suite

Physical interactions between proteins are involved in many important cell functions and are key for understanding the mechanisms of biological processes. Protein-protein docking programs provide a means to computationally construct three-dimensional (3D) models of a protein complex structure from its component protein units. A protein docking program takes two or more individual 3D protein structures, which are either experimentally solved or computationally modeled, and outputs a series of probable complex structures.In this chapter we present the LZerD protein docking suite, which includes programs for pairwise docking, LZerD and PI-LZerD, and multiple protein docking, Multi-LZerD, developed by our group. PI-LZerD takes protein docking interface residues as additional input information. The methods use a combination of shape-based protein surface features as well as physics-based scoring terms to generate protein complex models. The programs are provided as stand-alone programs and can be downloaded from http://kiharalab.org/proteindocking.

DockTrina: docking triangular protein trimers

In spite of the abundance of oligomeric proteins within a cell, the structural characterization of protein-protein interactions is still a challenging task. In particular, many of these interactions involve heteromeric complexes, which are relatively difficult to determine experimentally. Hence there is growing interest in using computational techniques to model such complexes. However, assembling large heteromeric complexes computationally is a highly combinatorial problem. Nonetheless the problem can be simplified greatly by considering interactions between protein trimers. After dimers and monomers, triangular trimers (i.e. trimers with pair-wise contacts between all three pairs of proteins) are the most frequently observed quaternary structural motifs according to the three-dimensional (3D) complex database. This article presents DockTrina, a novel protein docking method for modeling the 3D structures of nonsymmetrical triangular trimers. The method takes as input pair-wise contact predictions from a rigid body docking program. It then scans and scores all possible combinations of pairs of monomers using a very fast root mean square deviation test. Finally, it ranks the predictions using a scoring function which combines triples of pair-wise contact terms and a geometric clash penalty term. The overall approach takes less than 2 min per complex on a modern desktop computer. The method is tested and validated using a benchmark set of 220 bound and seven unbound protein trimer structures. DockTrina will be made available at http://nano-d.inrialpes.fr/software/docktrina.

Basin Hopping as a General and Versatile Optimization Framework for the Characterization of Biological Macromolecules

Since its introduction, the basin hopping (BH) framework has proven useful for hard nonlinear optimization problems with multiple variables and modalities. Applications span a wide range, from packing problems in geometry to characterization of molecular states in statistical physics. BH is seeing a reemergence in computational structural biology due to its ability to obtain a coarse-grained representation of the protein energy surface in terms of local minima. In this paper, we show that the BH framework is general and versatile, allowing to address problems related to the characterization of protein structure, assembly, and motion due to its fundamental ability to sample minima in a high-dimensional variable space. We show how specific implementations of the main components in BH yield algorithmic realizations that attain state-of-the-art results in the context of ab initio protein structure prediction and rigid protein-protein docking. We also show that BH can map intermediate minima related with motions connecting diverse stable functionally relevant states in a protein molecule, thus serving as a first step towards the characterization of transition trajectories connecting these states.

Predicting Multi-Component Protein Assemblies Using an Ant Colony Approach

Many biological processes are governed by large assemblies of protein molecules. However, it is often very difficult to determine the three-dimensional structures of these assemblies using experimental biophysical techniques. Hence there is a need to develop computational approaches to fill this gap. This article presents an ant colony optimization approach to predict the structure of large multi-component protein complexes. Starting from pair-wise docking predictions, a multi-graph consisting of vertices representing the component proteins and edges representing candidate interactions is constructed. This allows the assembly problem to be expressed in terms of searching for a minimum weight spanning tree. However, because the problem remains highly combinatorial, the search space cannot be enumerated exhaustively and therefore heuristic optimisation techniques must be used. The utility of the ant colony based approach is demonstrated by re-assembling known protein complexes from the Protein Data Bank. The algorithm is able to identify near-native solutions for five of the six cases tested. This demonstrates that the ant colony approach provides a useful way to deal with the highly combinatorial multi-component protein assembly problem.

GUIDING PROTEIN DOCKING WITH GEOMETRIC AND EVOLUTIONARY INFORMATION

Structural modeling of molecular assemblies promises to improve our understanding of molecular interactions and biological function. Even when focusing on modeling structures of protein dimers from knowledge of monomeric native structure, docking two rigid structures onto one another entails exploring a large configurational space. This paper presents a novel approach for docking protein molecules and elucidating native-like configurations of protein dimers. The approach makes use of geometric hashing to focus the docking of monomeric units on geometrically complementary regions through rigid-body transformations. This geometry-based approach improves the feasibility of searching the combined configurational space. The search space is narrowed even further by focusing the sought rigid-body transformations around molecular surface regions composed of amino acids with high evolutionary conservation. This condition is based on recent findings, where analysis of protein assemblies reveals that many functional interfaces are significantly conserved throughout evolution. Different search procedures are employed in this work to search the resulting narrowed configurational space. A proof-of-concept energy-guided probabilistic search procedure is also presented. Results are shown on a broad list of 18 protein dimers and additionally compared with data reported by other labs. Our analysis shows that focusing the search around evolutionary-conserved interfaces results in lower lRMSDs.

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.

Evaluation of multiple protein docking structures using correctly predicted pairwise subunits

Background

Many functionally important proteins in a cell form complexes with multiple chains. Therefore, computational prediction of multiple protein complexes is an important task in bioinformatics. In the development of multiple protein docking methods, it is important to establish a metric for evaluating prediction results in a reasonable and practical fashion. However, since there are only few works done in developing methods for multiple protein docking, there is no study that investigates how accurate structural models of multiple protein complexes should be to allow scientists to gain biological insights.

Methods

We generated a series of predicted models (decoys) of various accuracies by our multiple protein docking pipeline, Multi-LZerD, for three multi-chain complexes with 3, 4, and 6 chains. We analyzed the decoys in terms of the number of correctly predicted pair conformations in the decoys.

Results and conclusion

We found that pairs of chains with the correct mutual orientation exist even in the decoys with a large overall root mean square deviation (RMSD) to the native. Therefore, in addition to a global structure similarity measure, such as the global RMSD, the quality of models for multiple chain complexes can be better evaluated by using the local measurement, the number of chain pairs with correct mutual orientation. We termed the fraction of correctly predicted pairs (RMSD at the interface of less than 4.0Å) as fpair and propose to use it for evaluation of the accuracy of multiple protein docking.

Novel insights through the integration of structural and functional genomics data with protein networks

In recent years, major advances in genomics, proteomics, macromolecular structure determination, and the computational resources capable of processing and disseminating the large volumes of data generated by each have played major roles in advancing a more systems-oriented appreciation of biological organization. One product of systems biology has been the delineation of graph models for describing genome-wide protein-protein interaction networks. The network organization and topology which emerges in such models may be used to address fundamental questions in an array of cellular processes, as well as biological features intrinsic to the constituent proteins (or "nodes") themselves. However, graph models alone constitute an abstraction which neglects the underlying biological and physical reality that the network's nodes and edges are highly heterogeneous entities. Here, we explore some of the advantages of introducing a protein structural dimension to such models, as the marriage of conventional network representations with macromolecular structural data helps to place static node and edge constructs in a biologically more meaningful context. We emphasize that 3D protein structures constitute a valuable conceptual and predictive framework by discussing examples of the insights provided, such as enabling in silico predictions of protein-protein interactions, providing rational and compelling classification schemes for network elements, as well as revealing interesting intrinsic differences between distinct node types, such as disorder and evolutionary features, which may then be rationalized in light of their respective functions within networks.

SymmRef: a flexible refinement method for symmetric multimers

Symmetric protein complexes are abundant in the living cell. Predicting their atomic structure can shed light on the mechanism of many important biological processes. Symmetric docking methods aim to predict the structure of these complexes given the unbound structure of a single monomer, or its model. Symmetry constraints reduce the search-space of these methods and make the prediction easier compared to asymmetric protein-protein docking. However, the challenge of modeling the conformational changes that the monomer might undergo is a major obstacle. In this article, we present SymmRef, a novel method for refinement and reranking of symmetric docking solutions. The method models backbone and side-chain movements and optimizes the rigid-body orientations of the monomers. The backbone movements are modeled by normal modes minimization and the conformations of the side-chains are modeled by selecting optimal rotamers. Since solved structures of symmetric multimers show asymmetric side-chain conformations, we do not use symmetry constraints in the side-chain optimization procedure. The refined models are re-ranked according to an energy score. We tested the method on a benchmark of unbound docking challenges. The results show that the method significantly improves the accuracy and the ranking of symmetric rigid docking solutions. SymmRef is available for download at http:// bioinfo3d.cs.tau.ac.il/SymmRef/download.html.

Determining macromolecular assembly structures by molecular docking and fitting into an electron density map

Structural models of macromolecular assemblies are instrumental for gaining a mechanistic understanding of cellular processes. Determining these structures is a major challenge for experimental techniques, such as X-ray crystallography, NMR spectroscopy and electron microscopy (EM). Thus, computational modeling techniques, including molecular docking, are required. The development of most molecular docking methods has so far been focused on modeling of binary complexes. We have recently introduced the MultiFit method for modeling the structure of a multisubunit complex by simultaneously optimizing the fit of the model into an EM density map of the entire complex and the shape complementarity between interacting subunits. Here, we report algorithmic advances of the MultiFit method that result in an efficient and accurate assembly of the input subunits into their density map. The successful predictions and the increasing number of complexes being characterized by EM suggests that the CAPRI challenge could be extended to include docking-based modeling of macromolecular assemblies guided by EM.

Structural modeling of histone methyltransferase complex Set1C from Saccharomyces cerevisiae using constraint-based docking

Set1C is a histone methyltransferase playing an important role in yeast gene regulation. Modeling the structure of this eight-subunit protein complex is an important open problem to further elucidate its functional mechanism. Recently, there has been progress in modeling of larger complexes using constraints to restrict the combinatorial explosion in binary docking of subunits. Here, we model the subunits of Set1C and develop a constraint-based docking approach, which uses high-quality protein interaction as well as functional data to guide and constrain the combinatorial assembly procedure. We obtained 22 final models. The core complex consisting of the subunits Set1, Bre2, Sdc1 and Swd2 is conformationally conserved in over half of the models, thus, giving high confidence. We characterize these high-confidence and the lower confidence interfaces and discuss implications for the function of Set1C.

Strengths and weaknesses of data-driven docking in critical assessment of prediction of interactions

The recent CAPRI rounds have introduced new docking challenges in the form of protein-RNA complexes, multiple alternative interfaces, and an unprecedented number of targets for which homology modeling was required. We present here the performance of HADDOCK and its web server in the CAPRI experiment and discuss the strengths and weaknesses of data-driven docking. HADDOCK was successful for 6 out of 9 complexes (6 out of 11 targets) and accurately predicted the individual interfaces for two more complexes. The HADDOCK server, which is the first allowing the simultaneous docking of generic multi-body complexes, was successful in 4 out of 7 complexes for which it participated. In the scoring experiment, we predicted the highest number of targets of any group. The main weakness of data-driven docking revealed from these last CAPRI results is its vulnerability for incorrect experimental data related to the interface or the stoichiometry of the complex. At the same time, the use of experimental and/or predicted information is also the strength of our approach as evidenced for those targets for which accurate experimental information was available (e.g., the 10 three-stars predictions for T40!). Even when the models show a wrong orientation, the individual interfaces are generally well predicted with an average coverage of 60% ± 26% over all targets. This makes data-driven docking particularly valuable in a biological context to guide experimental studies like, for example, targeted mutagenesis.

Accounting for large amplitude protein deformation during in silico macromolecular docking

Rapid progress of theoretical methods and computer calculation resources has turned in silico methods into a conceivable tool to predict the 3D structure of macromolecular assemblages, starting from the structure of their separate elements. Still, some classes of complexes represent a real challenge for macromolecular docking methods. In these complexes, protein parts like loops or domains undergo large amplitude deformations upon association, thus remodeling the surface accessible to the partner protein or DNA. We discuss the problems linked with managing such rearrangements in docking methods and we review strategies that are presently being explored, as well as their limitations and success.

Three-dimensional modeling of protein interactions and complexes is going 'omics

High-throughput interaction discovery initiatives have revealed the existence of hundreds of multiprotein complexes whose functions are regulated through thousands of protein-protein interactions (PPIs). However, the structural details of these interactions, often necessary to understand their function, are only available for a tiny fraction, and the experimental difficulties surrounding complex structure determination make computational modeling techniques paramount. In this manuscript, we critically review some of the most recent developments in the field of structural bioinformatics applied to the modeling of protein interactions and complexes, from large macromolecular machines to domain-domain and peptide-mediated interactions. In particular, we place a special emphasis on those methods that can be applied in a proteome-wide manner, and discuss how they will help in the ultimate objective of building 3D interactome networks.

Macromolecular docking restrained by a small angle X-ray scattering profile

While many structures of single protein components are becoming available, structural characterization of their complexes remains challenging. Methods for modeling assembly structures from individual components frequently suffer from large errors, due to protein flexibility and inaccurate scoring functions. However, when additional information is available, it may be possible to reduce the errors and compute near-native complex structures. One such type of information is a small angle X-ray scattering (SAXS) profile that can be collected in a high-throughput fashion from a small amount of sample in solution. Here, we present an efficient method for protein-protein docking with a SAXS profile (FoXSDock): generation of complex models by rigid global docking with PatchDock, filtering of the models based on the SAXS profile, clustering of the models, and refining the interface by flexible docking with FireDock. FoXSDock is benchmarked on 124 protein complexes with simulated SAXS profiles, as well as on 6 complexes with experimentally determined SAXS profiles. When induced fit is less than 1.5Å interface C(α) RMSD and the fraction residues of missing from the component structures is less than 3%, FoXSDock can find a model close to the native structure within the top 10 predictions in 77% of the cases; in comparison, docking alone succeeds in only 34% of the cases. Thus, the integrative approach significantly improves on molecular docking alone. The improvement arises from an increased resolution of rigid docking sampling and more accurate scoring.

Integrative structure modeling of macromolecular assemblies from proteomics data

Proteomics techniques have been used to generate comprehensive lists of protein interactions in a number of species. However, relatively little is known about how these interactions result in functional multiprotein complexes. This gap can be bridged by combining data from proteomics experiments with data from established structure determination techniques. Correspondingly, integrative computational methods are being developed to provide descriptions of protein complexes at varying levels of accuracy and resolution, ranging from complex compositions to detailed atomic structures.

Building macromolecular assemblies by information-driven docking: introducing the HADDOCK multibody docking server

Over the last years, large scale proteomics studies have generated a wealth of information of biomolecular complexes. Adding the structural dimension to the resulting interactomes represents a major challenge that classical structural experimental methods alone will have difficulties to confront. To meet this challenge, complementary modeling techniques such as docking are thus needed. Among the current docking methods, HADDOCK (High Ambiguity-Driven DOCKing) distinguishes itself from others by the use of experimental and/or bioinformatics data to drive the modeling process and has shown a strong performance in the critical assessment of prediction of interactions (CAPRI), a blind experiment for the prediction of interactions. Although most docking programs are limited to binary complexes, HADDOCK can deal with multiple molecules (up to six), a capability that will be required to build large macromolecular assemblies. We present here a novel web interface of HADDOCK that allows the user to dock up to six biomolecules simultaneously. This interface allows the inclusion of a large variety of both experimental and/or bioinformatics data and supports several types of cyclic and dihedral symmetries in the docking of multibody assemblies. The server was tested on a benchmark of six cases, containing five symmetric homo-oligomeric protein complexes and one symmetric protein-DNA complex. Our results reveal that, in the presence of either bioinformatics and/or experimental data, HADDOCK shows an excellent performance: in all cases, HADDOCK was able to generate good to high quality solutions and ranked them at the top, demonstrating its ability to model symmetric multicomponent assemblies. Docking methods can thus play an important role in adding the structural dimension to interactomes. However, although the current docking methodologies were successful for a vast range of cases, considering the variety and complexity of macromolecular assemblies, inclusion of some kind of experimental information (e.g. from mass spectrometry, nuclear magnetic resonance, cryoelectron microscopy, etc.) will remain highly desirable to obtain reliable results.

A hybrid clustering of protein binding sites

The Protein Data Bank contains the description of approximately 27 000 protein-ligand binding sites. Most of the ligands at these sites are biologically active small molecules, affecting the biological function of the protein. The classification of their binding sites may lead to relevant results in drug discovery and design. Clusters of similar binding sites were created here by a hybrid, sequence and spatial structure-based approach, using the OPTICS clustering algorithm. A dissimilarity measure was defined: a distance function on the amino acid sequences of the binding sites. All the binding sites were clustered in the Protein Data Bank according to this distance function, and it was found that the clusters characterized well the Enzyme Commission numbers of the entries. The results, carefully color coded by the Enzyme Commission numbers of the proteins, containing the 20 967 binding sites clustered, are available as html files in three parts at http://pitgroup.org/seqclust/.

Analysis and prediction of protein quaternary structure

The quaternary structure (QS) of a protein is determined by measuring its molecular weight in solution. The data have to be extracted from the literature, and they may be missing even for proteins that have a crystal structure reported in the Protein Data Bank (PDB). The PDB and other databases derived from it report QS information that either was obtained from the depositors or is based on an analysis of the contacts between polypeptide chains in the crystal, and this frequently differs from the QS determined in solution.The QS of a protein can be predicted from its sequence using either homology or threading methods. However, a majority of the proteins with less than 30% sequence identity have different QSs. A model of the QS can also be derived by docking the subunits when their 3D structure is independently known, but the model is likely to be incorrect if large conformation changes take place when the oligomer assembles.

PTools: an opensource molecular docking library

Background

Macromolecular docking is a challenging field of bioinformatics. Developing new algorithms is a slow process generally involving routine tasks that should be found in a robust library and not programmed from scratch for every new software application.

Results

We present an object-oriented Python/C++ library to help the development of new docking methods. This library contains low-level routines like PDB-format manipulation functions as well as high-level tools for docking and analyzing results. We also illustrate the ease of use of this library with the detailed implementation of a 3-body docking procedure.

Conclusion

The PTools library can handle molecules at coarse-grained or atomic resolution and allows users to rapidly develop new software. The library is already in use for protein-protein and protein-DNA docking with the ATTRACT program and for simulation analysis. This library is freely available under the GNU GPL license, together with detailed documentation.

Inferential optimization for simultaneous fitting of multiple components into a CryoEM map of their assembly

Models of macromolecular assemblies are essential for a mechanistic description of cellular processes. Such models are increasingly obtained by fitting atomic-resolution structures of components into a density map of the whole assembly. Yet, current density-fitting techniques are frequently insufficient for an unambiguous determination of the positions and orientations of all components. Here, we describe MultiFit, a method used for simultaneously fitting atomic structures of components into their assembly density map at resolutions as low as 25 A. The component positions and orientations are optimized with respect to a scoring function that includes the quality-of-fit of components in the map, the protrusion of components from the map envelope, and the shape complementarity between pairs of components. The scoring function is optimized by our exact inference optimizer DOMINO (Discrete Optimization of Multiple INteracting Objects) that efficiently finds the global minimum in a discrete sampling space. MultiFit was benchmarked on seven assemblies of known structure, consisting of up to seven proteins each. The input atomic structures of the components were obtained from the Protein Data Bank, as well as by comparative modeling based on a 16-99% sequence identity to a template structure. A near-native configuration was usually found as the top-scoring model. Therefore, MultiFit can provide initial configurations for further refinement of many multicomponent assembly structures described by electron microscopy.