PyInteraph: a framework for the analysis of interaction networks in structural ensembles of proteins.

In the last years, a growing interest has been gathering around the ability of Molecular Dynamics (MD) to provide insight into the paths of long-range structural communication in biomolecules. The knowledge of the mechanisms related to structural communication helps in the rationalization in atomistic details of the effects induced by mutations, ligand binding, and the intrinsic dynamics of proteins. We here present PyInteraph, a tool for the analysis of structural ensembles inspired by graph theory. PyInteraph is a software suite designed to analyze MD and structural ensembles with attention to binary interactions between residues, such as hydrogen bonds, salt bridges, and hydrophobic interactions. PyInteraph also allows the different classes of intra- and intermolecular interactions to be represented, combined or alone, in the form of interaction graphs, along with performing network analysis on the resulting interaction graphs. The program also integrates the network description with a knowledge-based force field to estimate the interaction energies between side chains in the protein. It can be used alone or together with the recently developed xPyder PyMOL plugin through an xPyder-compatible format. The software capabilities and associated protocols are here illustrated by biologically relevant cases of study. The program is available free of charge as Open Source software via the GPL v3 license at http://linux.btbs.unimib.it/pyinteraph/.

Deconvolution and database search of complex tandem mass spectra of intact proteins: a combinatorial approach.

Top-down proteomics studies intact proteins, enabling new opportunities for analyzing post-translational modifications. Because tandem mass spectra of intact proteins are very complex, spectral deconvolution (grouping peaks into isotopomer envelopes) is a key initial stage for their interpretation. In such spectra, isotopomer envelopes of different protein fragments span overlapping regions on the m/z axis and even share spectral peaks. This raises both pattern recognition and combinatorial challenges for spectral deconvolution. We present MS-Deconv, a combinatorial algorithm for spectral deconvolution. The algorithm first generates a large set of candidate isotopomer envelopes for a spectrum, then represents the spectrum as a graph, and finally selects its highest scoring subset of envelopes as a heaviest path in the graph. In contrast with other approaches, the algorithm scores sets of envelopes rather than individual envelopes. We demonstrate that MS-Deconv improves on Thrash and Xtract in the number of correctly recovered monoisotopic masses and speed. We applied MS-Deconv to a large set of top-down spectra from Yersinia rohdei (with a still unsequenced genome) and further matched them against the protein database of related and sequenced bacterium Yersinia enterocolitica. MS-Deconv is available at http://proteomics.ucsd.edu/Software.html.

Protein structure modelling and evaluation based on a 4-distance description of side-chain interactions.

BACKGROUND: Accurate evaluation and modelling of residue-residue interactions within and between proteins is a key aspect of computational structure prediction including homology modelling, protein-protein docking, refinement of low-resolution structures, and computational protein design. RESULTS: Here we introduce a method for accurate protein structure modelling and evaluation based on a novel 4-distance description of residue-residue interaction geometry. Statistical 4-distance preferences were extracted from high-resolution protein structures and were used as a basis for a knowledge-based potential, called Hunter. We demonstrate that 4-distance description of side chain interactions can be used reliably to discriminate the native structure from a set of decoys. Hunter ranked the native structure as the top one in 217 out of 220 high-resolution decoy sets, in 25 out of 28 "Decoys 'R' Us" decoy sets and in 24 out of 27 high-resolution CASP7/8 decoy sets. The same concept was applied to side chain modelling in protein structures. On a set of very high-resolution protein structures the average RMSD was 1.47 A for all residues and 0.73 A for buried residues, which is in the range of attainable accuracy for a model. Finally, we show that Hunter performs as good or better than other top methods in homology modelling based on results from the CASP7 experiment. The supporting web site http://bioinfo.weizmann.ac.il/hunter/ was developed to enable the use of Hunter and for visualization and interactive exploration of 4-distance distributions. CONCLUSIONS: Our results suggest that Hunter can be used as a tool for evaluation and for accurate modelling of residue-residue interactions in protein structures. The same methodology is applicable to other areas involving high-resolution modelling of biomolecules.

PharmaGist: a webserver for ligand-based pharmacophore detection.

Predicting molecular interactions is a major goal in rational drug design. Pharmacophore, which is the spatial arrangement of features that is essential for a molecule to interact with a specific target receptor, is an important model for achieving this goal. We present a freely available web server, named PharmaGist, for pharmacophore detection. The employed method is ligand based. Namely, it does not require the structure of the target receptor. Instead, the input is a set of structures of drug-like molecules that are known to bind to the receptor. The output consists of candidate pharmacophores that are computed by multiple flexible alignment of the input ligands. The method handles the flexibility of the input ligands explicitly and in deterministic manner within the alignment process. PharmaGist is also highly efficient, where a typical run with up to 32 drug-like molecules takes seconds to a few minutes on a stardard PC. Another important characteristic is the capability of detecting pharmacophores shared by different subsets of input molecules. This capability is a key advantage when the ligands belong to different binding modes or when the input contains outliers. The webserver has a user-friendly interface available at http://bioinfo3d.cs.tau.ac.il/PharmaGist.

Novel approach for efficient pharmacophore-based virtual screening: method and applications.

Virtual screening is emerging as a productive and cost-effective technology in rational drug design for the identification of novel lead compounds. An important model for virtual screening is the pharmacophore. Pharmacophore is the spatial configuration of essential features that enable a ligand molecule to interact with a specific target receptor. In the absence of a known receptor structure, a pharmacophore can be identified from a set of ligands that have been observed to interact with the target receptor. Here, we present a novel computational method for pharmacophore detection and virtual screening. The pharmacophore detection module is able to (i) align multiple flexible ligands in a deterministic manner without exhaustive enumeration of the conformational space, (ii) detect subsets of input ligands that may bind to different binding sites or have different binding modes, (iii) address cases where the input ligands have different affinities by defining weighted pharmacophores based on the number of ligands that share them, and (iv) automatically select the most appropriate pharmacophore candidates for virtual screening. The algorithm is highly efficient, allowing a fast exploration of the chemical space by virtual screening of huge compound databases. The performance of PharmaGist was successfully evaluated on a commonly used data set of G-Protein Coupled Receptor alpha1A. Additionally, a large-scale evaluation using the DUD (directory of useful decoys) data set was performed. DUD contains 2950 active ligands for 40 different receptors, with 36 decoy compounds for each active ligand. PharmaGist enrichment rates are comparable with other state-of-the-art tools for virtual screening.

A hierarchical protein folding scheme based on the building block folding model.

The building block protein folding model states that the native protein structure is the product of a combinatorial assembly of relatively structurally independent contiguous parts of the protein that possess a hydrophobic core, i.e., building blocks (BBs). According to this model, our group proposed a three-stage scheme for a feasible time-wise semi ab-intio protein structure prediction. Given a protein sequence, at the first stage of the prediction scheme, we propose cutting the sequence into structurally assigned BBs. Next, we perform a combinatorial assembly and attempt to predict the relative three-dimensional arrangement of the BBs. In the third stage, we refine and rank the assemblies. The scheme has proven to be very promising in reducing the complexity of the protein folding problem and gaining insight into the protein folding process. In this chapter, we describe the different stages of the scheme and discuss a possible application of the model to protein design.

PatchDock and SymmDock: servers for rigid and symmetric docking.

Here, we describe two freely available web servers for molecular docking. The PatchDock method performs structure prediction of protein-protein and protein-small molecule complexes. The SymmDock method predicts the structure of a homomultimer with cyclic symmetry given the structure of the monomeric unit. The inputs to the servers are either protein PDB codes or uploaded protein structures. The services are available at http://bioinfo3d.cs.tau.ac.il. The methods behind the servers are very efficient, allowing large-scale docking experiments.

Prediction of multimolecular assemblies by multiple docking.

The majority of proteins function when associated in multimolecular assemblies. Yet, prediction of the structures of multimolecular complexes has largely not been addressed, probably due to the magnitude of the combinatorial complexity of the problem. Docking applications have traditionally been used to predict pairwise interactions between molecules. We have developed an algorithm that extends the application of docking to multimolecular assemblies. We apply it to predict quaternary structures of both oligomers and multi-protein complexes. The algorithm predicted well a near-native arrangement of the input subunits for all cases in our data set, where the number of the subunits of the different target complexes varied from three to ten. In order to simulate a more realistic scenario, unbound cases were tested. In these cases the input conformations of the subunits are either unbound conformations of the subunits or a model obtained by a homology modeling technique. The successful predictions of the unbound cases, where the input conformations of the subunits are different from their conformations within the target complex, suggest that the algorithm is robust. We expect that this type of algorithm should be particularly useful to predict the structures of large macromolecular assemblies, which are difficult to solve by experimental structure determination.

Geometry-based flexible and symmetric protein docking.

We present a set of geometric docking algorithms for rigid, flexible, and cyclic symmetry docking. The algorithms are highly efficient and have demonstrated very good performance in CAPRI Rounds 3-5. The flexible docking algorithm, FlexDock, is unique in its ability to handle any number of hinges in the flexible molecule, without degradation in run-time performance, as compared to rigid docking. The algorithm for reconstruction of cyclically symmetric complexes successfully assembles multimolecular complexes satisfying C(n) symmetry for any n in a matter of minutes on a desktop PC. Most of the algorithms presented here are available at the Tel Aviv University Structural Bioinformatics Web server (http://bioinfo3d.cs.tau.ac.il/).

Approaching the CAPRI challenge with an efficient geometry-based docking.

The last 3 rounds (3-5) of CAPRI included a wide range of docking targets. Several targets were especially challenging, since they involved large-scale movements and symmetric rearrangement, while others were based on homology models. We have approached the targets with a variety of geometry-based docking algorithms that include rigid docking, symmetric docking, and flexible docking with symmetry constraints. For all but 1 docking target, we were able to submit at least 1 acceptable quality prediction. Here, we detail for each target the prediction methods used and the specific biological data employed, and supply a retrospective analysis of the results. We highlight the advantages of our techniques, which efficiently exploit the geometric shape complementarity properties of the interaction. These enable them to run only few minutes on a standard PC even for flexible docking, thus proving their scalability toward computational genomic scale experiments. We also outline the major required enhancements, such as the introduction of side-chain position refinement and the introduction of flexibility for both docking partners.

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.

Taking geometry to its edge: fast unbound rigid (and hinge-bent) docking.

We present a very efficient rigid "unbound" soft docking methodology, which is based on detection of geometric shape complementarity, allowing liberal steric clash at the interface. The method is based on local shape feature matching, avoiding the exhaustive search of the 6D transformation space. Our experiments at CAPRI rounds 1 and 2 show that although the method does not perform an exhaustive search of the 6D transformation space, the "correct" solution is never lost. However, such a solution might rank low for large proteins, because there are alternatives with significantly larger geometrically compatible interfaces. In many cases this problem can be resolved by successful a priori focusing on the vicinity of potential binding sites as well as the extension of the technique to flexible (hinge-bent) docking. This is demonstrated in the experiments performed as a lesson from our CAPRI experience.

Deterministic pharmacophore detection via multiple flexible alignment of drug-like molecules.

We present a novel highly efficient method for the detection of a pharmacophore from a set of drug-like ligands that interact with a target receptor. A pharmacophore is a spatial arrangement of physico-chemical features in a ligand that is essential for the interaction with a specific receptor. In the absence of a known three-dimensional (3D) receptor structure, a pharmacophore can be identified from a multiple structural alignment of ligand molecules. The key advantages of the presented algorithm are: (a) its ability to multiply align flexible ligands in a deterministic manner, (b) its ability to focus on subsets of the input ligands, which may share a large common substructure, resulting in the detection of both outlier molecules and alternative binding modes, and (c) its computational efficiency, which allows to detect pharmacophores shared by a large number of molecules on a standard PC. The algorithm was extensively tested on a dataset of almost 80 ligands acting on 12 different receptors. The results, which were achieved using a set of standard default parameters, were consistent with reference pharmacophores that were derived from the bound ligand-receptor complexes. The pharmacophores detected by the algorithm are expected to be a key component in the discovery of new leads by screening large databases of drug-like molecules. A user-friendly web interface is available at http://bioinfo3d.cs.tau.ac.il/pharma. Supplementary material can be found at http://bioinfo3d.cs.tau.ac.il/pharma/reduction/.

Mechanism of two classes of cancer mutations in the phosphoinositide 3-kinase catalytic subunit.

Many human cancers involve up-regulation of the phosphoinositide 3-kinase PI3Kalpha, with oncogenic mutations identified in both the p110alpha catalytic and the p85alpha regulatory subunits. We used crystallographic and biochemical approaches to gain insight into activating mutations in two noncatalytic p110alpha domains-the adaptor-binding and the helical domains. A structure of the adaptor-binding domain of p110alpha in a complex with the p85alpha inter-Src homology 2 (inter-SH2) domain shows that oncogenic mutations in the adaptor-binding domain are not at the inter-SH2 interface but in a polar surface patch that is a plausible docking site for other domains in the holo p110/p85 complex. We also examined helical domain mutations and found that the Glu545 to Lys545 (E545K) oncogenic mutant disrupts an inhibitory charge-charge interaction with the p85 N-terminal SH2 domain. These studies extend our understanding of the architecture of PI3Ks and provide insight into how two classes of mutations that cause a gain in function can lead to cancer.

Protein structure prediction via combinatorial assembly of sub-structural units.

Following the hierarchical nature of protein folding, we propose a three-stage scheme for the prediction of a protein structure from its sequence. First, the sequence is cut to fragments that are each assigned a structure. Second, the assigned structures are combinatorially assembled to form the overall 3D organization. Third, highly ranked predicted arrangements are completed and refined. This work focuses on the second stage of this scheme: the combinatorial assembly. We present CombDock, a combinatorial docking algorithm. CombDock gets an ordered set of protein sub-structures and predicts the inter-contacts that define their overall organization. We reduce the combinatorial assembly to a graph-theory problem, and give a heuristic polynomial solution to this computationally hard problem. We applied CombDock to various examples of structural units of two types: protein domains and building blocks, which are relatively stable sub-structures of domains. Moreover, we tested CombDock using increasingly distorted input, where the native structural units were replaced by similarly folded units extracted from homologous proteins and, in the more difficult cases, from globally unrelated proteins. The algorithm is robust, showing low sensitivity to input distortion. This suggests that CombDock is a useful tool in protein structure prediction that may be applied to large target proteins.