We introduce SegmA, a novel method for cryo-EM map visualization. By coloring voxels based on their amino acids, SegmA enhances both manual and automated modeling. This coloring approach also serves as a scoring function, extending its utility to de-novo structure modeling.SegmA’s algorithm is a cascade of group rotational equivariant convolutional neural networks (G-CNNs), enabling it to better handle the orientation variability of cryo-EM maps. During the training procedure of SegmA, an iterative co-training algorithm is utilized to filter out poorly labeled samples from the training dataset. SegmA also detects regions of low-confidence labeling, with amino acid detection accuracy increasing to 80% after removing these regions.Beyond 3D visualization, SegmA also has additional applications such as prediction of amino acid centers of mass, scoring of the fitting of a protein structural template into a cryo-EM map, and de-novo modeling of a protein complex.

Design of peptide binders is an attractive strategy for targeting "undruggable" protein-protein interfaces. Current design protocols rely on the extraction of an initial sequence from one known protein interactor of the target protein, followed by in-silico or in-vitro mutagenesis-based optimization of its binding affinity. Wet lab protocols can explore only a minor portion of the vast sequence space and cannot efficiently screen for other desirable properties such as high specificity and low toxicity, while in-silico design requires intensive computational resources and often relies on simplified binding models. Yet, for a multivalent protein target, dozens to hundreds of natural protein partners already exist in the cellular environment. Here, we describe a peptide design protocol that harnesses this diversity via a machine learning generative model. After identifying putative natural binding fragments by literature and homology search, a compositional Restricted Boltzmann Machine is trained and sampled to yield hundreds of diverse candidate peptides. The latter are further filtered via flexible molecular docking and an in-vitro microchip-based binding assay. We validate and test our protocol on calcineurin, a calcium-dependent protein phosphatase involved in various cellular pathways in health and disease. In a single screening round, we identified multiple 16-length peptides with up to six mutations from their closest natural sequence that successfully interfere with the binding of calcineurin to its substrates. In summary, integrating protein interaction and sequence databases, generative modeling, molecular docking and interaction assays enables the discovery of novel protein-protein interaction modulators.

MOTIVATION: A highly efficient template-based protein-protein docking algorithm, nicknamed SnapDock, is presented. It employs a Geometric Hashing-based structural alignment scheme to align the target proteins to the interfaces of non-redundant protein-protein interface libraries. Docking of a pair of proteins utilizing the 22 600 interface PIFACE library is performed in < 2 min on the average. A flexible version of the algorithm allowing hinge motion in one of the proteins is presented as well. RESULTS: To evaluate the performance of the algorithm a blind re-modelling of 3547 PDB complexes, which have been uploaded after the PIFACE publication has been performed with success ratio of about 35%. Interestingly, a similar experiment with the template free PatchDock docking algorithm yielded a success rate of about 23% with roughly 1/3 of the solutions different from those of SnapDock. Consequently, the combination of the two methods gave a 42% success ratio. AVAILABILITY AND IMPLEMENTATION: A web server of the application is under development. CONTACT: [email protected] or [email protected].

A major challenge in protein-protein docking is the distinction between near-native and decoy complex predictions. It has been shown that near native solutions are usually located at the bottom of deep and densely populated funnels in the binding energy plot of the complex. Thus exploration, whether the energy plot of the vicinity of a docking solution is “funnel like”, can serve as a validation of such a solution. Generation of such densely sampled plots, however, is a major computational challenge. We have designed an accurate and highly efficient parallel algorithm for generation of such energy plots and implemented it on a server with 4 GPU processors, each with 2880 cores. The algorithm achieved a speedup of about 150 compared to its serial counterpart, while even outperforming it in the achieved results. While the algorithm proved very useful for near native complex hypothesis validation, it still detects many funnels for decoy solutions, especially those with good shape complementarity.

MOTIVATION: A wide range of fundamental biological processes are mediated by membrane proteins. Despite their large number and importance, less than 1% of all 3D protein structures deposited in the Protein Data Bank are of membrane proteins. This is mainly due to the challenges of crystallizing such proteins or performing NMR spectroscopy analyses. All the more so, there is only a small number of membrane protein-protein complexes with known structure. Therefore, developing computational tools for docking membrane proteins is crucial. Numerous methods for docking globular proteins exist, however few have been developed especially for membrane proteins and designed to address docking within the lipid bilayer environment. RESULTS: We present a novel algorithm, Memdock, for docking α-helical membrane proteins which takes into consideration the lipid bilayer environment for docking as well as for refining and ranking the docking candidates. We show that our algorithm improves both the docking accuracy and the candidates ranking compared to a standard protein-protein docking algorithm. AVAILABILITY AND IMPLEMENTATION: http://bioinfo3d.cs.tau.ac.il/Memdock/ CONTACTS: [email protected] or [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: Design of protein-protein interaction (PPI) inhibitors is a major challenge in Structural Bioinformatics. Peptides, especially short ones (5-15 amino acid long), are natural candidates for inhibition of protein-protein complexes due to several attractive features such as high structural compatibility with the protein binding site (mimicking the surface of one of the proteins), small size and the ability to form strong hotspot binding connections with the protein surface. Efficient rational peptide design is still a major challenge in computer aided drug design, due to the huge space of possible sequences, which is exponential in the length of the peptide, and the high flexibility of peptide conformations. RESULTS: In this article we present PinaColada, a novel computational method for the design of peptide inhibitors for protein-protein interactions. We employ a version of the ant colony optimization heuristic, which is used to explore the exponential space ([Formula: see text]) of length n peptide sequences, in combination with our fast robotics motivated PepCrawler algorithm, which explores the conformational space for each candidate sequence. PinaColada is being run in parallel, on a DELL PowerEdge 2.8 GHZ computer with 20 cores and 256 GB memory, and takes up to 24 h to design a peptide of 5-15 amino acids length. AVAILABILITY AND IMPLEMENTATION: An online server available at: http://bioinfo3d.cs.tau.ac.il/PinaColada/. CONTACT: [email protected]; [email protected].

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: [email protected] or [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: Design of protein-protein interaction (PPI) inhibitors is a key challenge in structural bioinformatics and computer-aided drug design. Peptides, which partially mimic the interface area of one of the interacting proteins, are natural candidates to form protein-peptide complexes competing with the original PPI. The prediction of such complexes is especially challenging due to the high flexibility of peptide conformations. RESULTS: In this article, we present PepCrawler, a new tool for deriving binding peptides from protein-protein complexes and prediction of peptide-protein complexes, by performing high-resolution docking refinement and estimation of binding affinity. By using a fast path planning approach, PepCrawler rapidly generates large amounts of flexible peptide conformations, allowing backbone and side chain flexibility. A newly introduced binding energy funnel 'steepness score' was applied for the evaluation of the protein-peptide complexes binding affinity. PepCrawler simulations predicted high binding affinity for native protein-peptide complexes benchmark and low affinity for low-energy decoy complexes. In three cases, where wet lab data are available, the PepCrawler predictions were consistent with the data. Comparing to other state of the art flexible peptide-protein structure prediction algorithms, our algorithm is very fast, and takes only minutes to run on a single PC. AVAILABILITY: http://bioinfo3d.cs.tau.ac.il/PepCrawler/ CONTACT: [email protected]; [email protected].

MOTIVATION: The database of known protein structures (PDB) is increasing rapidly. This results in a growing need for methods that can cope with the vast amount of structural data. To analyze the accumulating data, it is important to have a fast tool for identifying similar structures and clustering them by structural resemblance. Several excellent tools have been developed for the comparison of protein structures. These usually address the task of local structure alignment, an important yet computationally intensive problem due to its complexity. It is difficult to use such tools for comparing a large number of structures to each other at a reasonable time. RESULTS: Here we present GOSSIP, a novel method for a global all-against-all alignment of any set of protein structures. The method detects similarities between structures down to a certain cutoff (a parameter of the program), hence allowing it to detect similar structures at a much higher speed than local structure alignment methods. GOSSIP compares many structures in times which are several orders of magnitude faster than well-known available structure alignment servers, and it is also faster than a database scanning method. We evaluate GOSSIP both on a dataset of short structural fragments and on two large sequence-diverse structural benchmarks. Our conclusions are that for a threshold of 0.6 and above, the speed of GOSSIP is obtained with no compromise of the accuracy of the alignments or of the number of detected global similarities. AVAILABILITY: A server, as well as an executable for download, are available at http://bioinfo3d.cs.tau.ac.il/gossip/.

Cryo-EM has become an increasingly powerful technique for elucidating the structure, dynamics, and function of large flexible macromolecule assemblies that cannot be determined at atomic resolution. However, due to the relatively low resolution of cryo-EM data, a major challenge is to identify components of complexes appearing in cryo-EM maps. Here, we describe EMatch, a novel integrated approach for recognizing structural homologues of protein domains present in a 6-10 A resolution cryo-EM map and constructing a quasi-atomic structural model of their assembly. The method is highly efficient and has been successfully validated on various simulated data. The strength of the method is demonstrated by a domain assembly of an experimental cryo-EM map of native GroEL at 6 A resolution.

MOTIVATION: Secondary-Structure Guided Superposition tool (SSGS) is a permissive secondary structure-based algorithm for matching of protein structures and in particular their fragments. The algorithm was developed towards protein structure prediction via fragment assembly. RESULTS: In a fragment-based structural prediction scheme, a protein sequence is cut into building blocks (BBs). The BBs are assembled to predict their relative 3D arrangement. Finally, the assemblies are refined. To implement this prediction scheme, a clustered structural library representing sequence patterns for protein fragments is essential. To create a library, BBs generated by cutting proteins from the PDB are compared and structurally similar BBs are clustered. To allow structural comparison and clustering of the BBs, which are often relatively short with flexible loops, we have devised SSGS. SSGS maintains high similarity between cluster members and is highly efficient. When it comes to comparing BBs for clustering purposes, the algorithm obtains better results than other, non-secondary structure guided protein superimposition algorithms.

The generation of binding modes between two molecules, also known as molecular docking, is a key problem in rational drug design and biomolecular recognition. Docking a ligand, e.g., a drug molecule or a protein molecule, to a protein receptor, involves recognition of molecular surfaces as molecules interact at their surface. Recent studies report that the activity of many molecules induces conformational transitions by 'hinge-bending', which involves movements of relatively rigid parts with respect to each other. In ligand-receptor binding, relative rotational movements of molecular substructures about their common hinges have been observed. For automatically predicting flexible molecular interactions, we adapt a new technique developed in Computer Vision and Robotics for the efficient recognition of partially occluded articulated objects. These type of objects consist of rigid parts which are connected by rotary joints (hinges). Our approach is based on an extension and generalization of the Geometric Hashing and Generalized Hough Transform paradigm for rigid object recognition. Unlike other techniques which match each part individually, our approach exploits forcefully and efficiently enough the fact that the different rigid parts do belong to the same flexible molecule. We show experimental results obtained by an implementation of the algorithm for rigid and flexible docking. While the 'correct', crystal-bound complex is obtained with a small RMSD, additional, predictive 'high scoring' binding modes are generated as well. The diverse applications and implications of this general, powerful tool are discussed.

This application presents an algorithm for model-based partial recognition of CAD/CAM objects in 3-D space. Its main goal is to serve as an industrial application in robotic aided production lines and to facilitate the programming of process robots. Hence, a special emphasis is given to its practical capabilities. The recognition algorithm is invariant to the 3-D similarity transformation: rotation (& reflection), translation and scale. The objects can be represented as wireframes, solids or surfaces. The algorithm is based on the geometric hashing method and exploits specific CAD/CAM geometric constraints.

The problem of receptor-ligand recognition and binding is encountered in a very large number of biological processes, The behavior of the molecules depends both on their geometric shape and on the chemical interactions among their atoms. This work addresses only the geometrical (key-in-lock) aspect of the problem, where acceptable solutions should exhibit shape complementarity. The problem we are faced with here is reminiscent of partial 3-D surface matching problems in computer vision. Here we present a new 3-D molecular surface representation by (hundreds of) sparse interest (critical) points with associated normals and a subsequent matching approach which is based on the geometric hashing paradigm originally developed for computer vision motivated object recognition applications. Potential solutions resulting in the interpenetration of the molecules are discarded by a subsequent verification procedure. Numerous examples of the successful geometric prediction of our technique are presented. In all cases the performance of our algorithm has been by several orders of magnitude faster than of other state-of-the-art docking algorithms.

An algorithm for the detection of 'perceptual similarity' among planar shapes is suggested. Current state-of-the-art matching algorithms deal mainly with shapes which are similar modulo a well defined geometric transformation. The goal of this paper is to suggest a similarity measure among shapes which 'look similar', such as different fonts of a letter or pictures of different 'perceptually similar' chairs. The essence of the authors' approach consists in the representation of the shapes as special weighted graphs, the vertices of which represent the 'lumps' of the shapes in a given orientation. Then, these graphs are gradually reduced by a 'small leaf' trimming procedure until the resulting graphs are isomorphic. A similarity measure is calculated based on this representation. Since the graphs are orientation dependent, the similarity measure is minimized over all orientations of one of the shapes. Experimental results of pairwise comparisons of a 24 shape database are presented.

A method for model-based recognition of articulated objects in cluttered scenes is presented. The objects consist of rigid parts connected by rotary or prismatic joints. The method is based on an extension of the generalized Hough transform approach. It is applicable to various viewing transformations. Unlike previous methods there is no significant degradation in performance for recognition of articulated objects compared with the recognition of rigid objects containing similar amounts of information. The method was implemented and successfully tested for recognition of partially overlapping 2-D objects with rotary joints which have undergone rotation, translation, and scaling.>

An experimental and theoretical analysis of the noise model in the geometric hashing technique is presented. The efficacy of the technique is discussed in the cases of affine transformations, similarities, and grid motions. The efficacy of the voting procedure, in geometric hashing is discussed, and it is shown that its introduction significantly reduces the expected burden of the verification stage. The discussion is illustrated by results of simulations which have been performed to test the expected performance of the algorithm.>

An operator based on the intuitive motion of symmetry, which effectively locates interest points in real time and can be incorporated also in active visual systems, is introduced. The results of its operation agree with some psychophysical evidence concerning symmetry as well as evidence concerning fixation points. The operator can be applied successfully without prior knowledge of the world. Combining the operator with some preconceptions about the image is a powerful tool for feature detection in intricate natural scenes. The localization of faces and facial features in real time is demonstrated on detailed and noisy pictures.>

Two algorithms to find the longest common subcurve of two 2D curves are presented. These algorithms are based on conversion of the curves into shape signature strings and application of string matching techniques to find long matching substrings, followed by direct curve matching of the corresponding candidate subcurves to find the longest matching subcurve. The first algorithm is of complexity O(n), where n is the number of sample points on the curves. The second one, while being theoretically somewhat less efficient, proved to be robust and efficient in practical applications. Both algorithms solve the problem of general curves without being dependent on some set of special points on the curves. The algorithms have industrial applications to problems of object assembly and object recognition. Experimental results are included. The algorithms can be easily extended to the 3D case.>

New techniques are described for model-based recognition of the objects in 3-D space. The recognition is performed from single gray-scale images taken from unknown viewpoints. The objects in the scene may be overlapping and partially occluded. An efficient matching algorithm, which assumes affine approximation to the prospective viewing transformation, is proposed. The algorithm has an offline model preprocessing (shape representation) phase which is independent of the scene information and a recognition phase based on efficient indexing. It has a straightforward parallel implementation. The algorithm was successfully tested in recognition of industrial objects appearing in composite occluded scenes.>

An integrated vision-manipulation algorithm for assembly of apictorial jigsaw puzzles is presented. A discussion is presented of the solution of large jigsaw puzzles using vision, combinatorial optimization, and fine assembly techniques. The implementations of a vision algorithm for assembly of large jigsaw puzzles and a fully integrated robotic-vision algorithm for assembly of small puzzles are presented. The problem of assembling pieces with unpredictable shape is discussed.>

Novel techniques are described for model-based recognition of 3-D objects from unknown viewpoints using single-gray-scale images. The objects in the scene may be overlapping and partially occluded. Efficient matching algorithms, which assume affine approximation to the perspective viewing transformation, are proposed. The study is currently restricted to flat rigid 3-D objects. Point, line and curve matching algorithms are presented. The study especially emphasizes the curve matching problem. Experimental results are included.>

A general method for model-based object recognition in occluded scenes is presented. It is based on geometric hashing. The method stands out for its efficiency. We describe the general framework of the method and illustrate its applications for various recogni- tion problems both in 3-D and 2-D. Special attention is given to the recognition of 3-D objects in occluded scenes from 2-D gray scale images. New experimental results are included for this important case.

A method for recognition of partially occluded and overlapping objects in composite scenes is presented. The objects to be recognized belong to a large database of model objects which are known in advance. A geometric hashing technique which is an improvement of a previous technique due to J.T. Schwartz and M. Sharir (1987) is proposed. The algorithm's complexity is linear in the number of sample points on the boundary of the composite scene. Experimental results from large databases are presented, including results that could not be obtained by the previous technique.>

Techniques are described for model-based recognition of 3-D objects from unknown viewpoints using single gray-scale images. The method is especially useful for recognition of scenes with overlapping and partially occluded objects. An efficient matching algorithm, which assumes affine approximation to the perspective viewing transformation, is proposed. The algorithm has an off line model preprocessing phase and a recognition phase to reduce matching complexity. The algorithm was successfully tested in recognition of flat industrial objects appearing in composite occluded scenes.>