A Structural-informatics approach for tracing beta-sheets: building pseudo-C(alpha) traces for beta-strands in intermediate-resolution density maps

We report the development of two computational methods to assist density map interpretation at intermediate resolutions: sheettracer for building pseudo-C(alpha) models of beta-sheets, and a deconvolution method for enhancing features attributed to major secondary structural elements. Sheettracer is tightly coupled with sheetminer, which was developed to locate sheet densities in intermediate-resolution density maps. The results from sheetminer are used as inputs to sheettracer, which employs a multi-step ad hoc morphological analysis of sheet densities to trace individual strands of beta-sheets. The methods were tested on simulated density maps from 12 protein crystal structures that represent a reasonably complete sampling of sheet morphology. The sheet-tracing results were quantitatively assessed in terms of sensitivity, specificity and rms deviations. Furthermore, sheettracer and the deconvolution method were rigorously tested on experimental maps of the lambda2 protein of reovirus at resolutions of 7.6A and 11.8A. Our results clearly demonstrate the capability of sheettracer in building pseudo-C(alpha) models of beta-sheets in intermediate-resolution density maps and the power of the deconvolution method in enhancing the performance of sheettracer. These computational methods, along with other related ones, should facilitate recognition and analysis of folding motifs from experimental data at intermediate resolutions.     

Combining electron microscopy and comparative protein structure modeling

Recently, advances have been made in methods and applications that integrate electron microscopy density maps and comparative modeling to produce atomic structures of macromolecular assemblies. Electron microscopy can benefit from comparative modeling through the fitting of comparative models into electron microscopy density maps. Also, comparative modeling can benefit from electron microscopy through the use of intermediate-resolution density maps in fold recognition, template selection and sequence-structure alignment.     

Determining protein topology from skeletons of secondary structures

We report a novel computational procedure for determining protein native topology, or fold, by defining loop connectivity based on skeletons of secondary structures that can usually be obtained from low to intermediate-resolution density maps. The procedure primarily involves a knowledge-based geometry filter followed by an energetics-based evaluation. It was tested on a large set of skeletons covering a wide range of protein architecture, including one modeled from an experimentally determined 7.6A cryo-electron microscopy (cryo-EM) density map. The results showed that the new procedure could effectively deduce protein folds without high-resolution structural data, a feature that could also be used to recognize native fold in structure prediction and to interpret data in fields like structure genomics. Most importantly, in the energetics-based evaluation, it was revealed that, despite the inevitable errors in the artificially constructed structures and limited accuracy of knowledge-based potential functions, the average energy of an ensemble of structures with slightly different configurations around the native skeleton is a much more robust parameter for marking native topology than the energy of individual structures in the ensemble. This result implies that, among all the possible topology candidates for a given skeleton, evolution has selected the native topology as the one that can accommodate the largest structural variations, not the one rigidly trapped in a deep, but narrow, conformational energy well.     

A structural-informatics approach for mining beta-sheets: locating sheets in intermediate-resolution density maps

Here, we report a new computational method, called sheetminer, for mining beta-sheets in the density maps at intermediate resolutions of 6 to 10A. The method employs a multi-step ad hoc morphological analysis of density maps to identify the unique characteristics of beta-sheets. It was tested on density maps from 12 protein crystal structures that were artificially blurred to intermediate resolutions. There are a total of 35 independent beta-sheets with a wide distribution of morphology. The method successfully located 34 of them and missed only one. The method was also applied to an experimental 9A electron cryomicroscopic structure and an 8A X-ray density map. In both cases, the sheet-searching results were found to agree very well with known high-resolution crystal structures. Collectively, these results demonstrate clearly the robustness of sheetminer in locating the regions belonging to beta-sheets in the intermediate-resolution density maps. Furthermore, sheetminer is completely complementary to all other existing computational methods, including helixhunter and threading algorithms. Their combined usage has the potential to significantly enhance the computational modeling capacity for a much more complete interpretation of structural data at intermediate resolutions, from which extraction of functional information would be more effective. This is particularly important in the field of structural genomics, in which the fast screening approach may not always yield crystals that diffract to atomic resolution. An exciting future application of sheetminer is as a valuable tool for revealing the structures of amyloid fibrils that are rich in beta-motifs.     

Modeling protein structure at near atomic resolutions with Gorgon

Electron cryo-microscopy (cryo-EM) has played an increasingly important role in elucidating the structure and function of macromolecular assemblies in near native solution conditions. Typically, however, only non-atomic resolution reconstructions have been obtained for these large complexes, necessitating computational tools for integrating and extracting structural details. With recent advances in cryo-EM, maps at near-atomic resolutions have been achieved for several macromolecular assemblies from which models have been manually constructed. In this work, we describe a new interactive modeling toolkit called Gorgon targeted at intermediate to near-atomic resolution density maps (10-3.5 ?), particularly from cryo-EM. Gorgon's de novo modeling procedure couples sequence-based secondary structure prediction with feature detection and geometric modeling techniques to generate initial protein backbone models. Beyond model building, Gorgon is an extensible interactive visualization platform with a variety of computational tools for annotating a wide variety of 3D volumes. Examples from cryo-EM maps of Rotavirus and Rice Dwarf Virus are used to demonstrate its applicability to modeling protein structure.     

Gorgon and pathwalking: macromolecular modeling tools for subnanometer resolution density maps

The complex interplay of proteins and other molecules, often in the form of large transitory assemblies, are critical to cellular function. Today, X-ray crystallography and electron cryo-microscopy (cryo-EM) are routinely used to image these macromolecular complexes, though often at limited resolutions. Despite the rapidly growing number of macromolecular structures, few tools exist for modeling and annotating structures in the range of 3-10 ? resolution. To address this need, we have developed a number of utilities specifically targeting subnanometer resolution density maps. As part of the 2010 Cryo-EM Modeling Challenge, we demonstrated two of our latest de novo modeling tools, Pathwalking and Gorgon, as well as a tool for secondary structure identification (SSEHunter) and a new rigid-body/flexible fitting tool in Gorgon. In total, we submitted 30 structural models from ten different subnanometer resolution data sets in four of the six challenge categories. Each of our utlities produced accurate structural models and annotations across the various density maps. In the end, the utilities that we present here offer users a robust toolkit for analyzing and modeling protein structure in macromolecular assemblies at non-atomic resolutions.     

Edged watershed segmentation: A semi-interactive algorithm for segmentation of low-resolution maps from electron cryomicroscopy

Electron cryomicroscopy (cryo-EM) allows for the structural analysis of large protein complexes that may be difficult to study by other means. Frequently, maps of complexes from cryo-EM are obtained at resolutions between 10 and 25 Å. To aid in the interpretation of these medium- to low-resolution maps, they may be subdivided into three-dimensional segments representing subunits or subcomplexes. This division is often accomplished using a manual segmentation approach. While extremely useful, manual segmentation is subjective. We have developed a novel semi-interactive segmentation algorithm that can incorporate prior knowledge of subunit composition or structure without biasing the boundaries between subunits or subcomplexes. This algorithm has been characterized with experimental and simulated cryo-EM density maps at resolutions between 10 and 25 Å.     

EM-fold: de novo atomic-detail protein structure determination from medium-resolution density maps

Electron density maps of membrane proteins or large macromolecular complexes are frequently only determined at medium resolution between 4?? and 10??, either by cryo-electron microscopy or X-ray crystallography. In these density maps, the general arrangement of secondary structure elements (SSEs) is revealed, whereas their directionality and connectivity remain elusive. We demonstrate that the topology of proteins with up to 250 amino acids can be determined from such density maps when combined with a computational protein folding protocol. Furthermore, we accurately reconstruct atomic detail in loop regions and amino acid side chains not visible in the experimental data. The EM-Fold algorithm assembles the SSEs de novo before atomic detail is added using Rosetta. In a benchmark of 27 proteins, the protocol consistently and reproducibly achieves models with root mean square deviation values <3??.     

Structural analysis of antiviral agents that interact with the capsid of human rhinoviruses

X-Ray diffraction data have been obtained for nine related antiviral agents ("WIN compounds") while bound to human rhinovirus 14 (HRV14). These compounds can inhibit both viral attachment to host cells and uncoating. To calculate interpretable electron density maps it was necessary to account for (1) the low (approximately 60%) occupancies of these compounds in the crystal, (2) the large (up to 7.9 A) conformational changes induced at the attachment site, and (3) the incomplete diffraction data. Application of a density difference map technique, which exploits the 20-fold noncrystallographic redundancy in HRV14, resulted in clear images of the HRV14:WIN complexes. A real-space refinement procedure was used to fit atomic models to these maps. The binding site of WIN compounds in HRV14 is a hydrophobic pocket composed mainly from residues that form the beta-barrel of VP1. Among rhinoviruses, the residues associated with the binding pocket are far more conserved than external residues and are mostly contained within regular secondary structural elements. Molecular dynamics simulations of three HRV14:WIN complexes suggest that portions of the WIN compounds and viral protein near the entrance of the binding pocket are more flexible than portions deeper within the beta-barrel.     

A data mining approach for analyzing density maps representing macromolecular structures

Results of electron microscopy-based three-dimensional reconstructions of macromolecules or their complexes are usually stored as density maps. Each point ("voxel") in the map represents a density value and one approach for studying details of the map is to display an isosurface enclosing areas of interest. We have taken a data mining approach not only focusing on the areas of immediate interest but determining all possible separate entities ("blobs") from a density map. After the entire density map is analyzed with our mining program BLOBBER, properties of all detected blobs can be browsed and sets of blobs can be visualized using our VIZBLOB program. Since BLOBBER analyzes density maps using only density information and relates it to spatial relationships, BLOBBER can be used to analyze symmetrical or asymmetrical density maps from any source. To test our program we have analyzed published bacteriophage PRD1 reconstructions. We identified various structural details ranging from individual proteins to major complexes such as the whole capsid shell and more elaborate details of possible connections between membrane interfaces. This approach can also be a useful preprocessing tool for visualizing reconstructions.     

Ranking valid topologies of the secondary structure elements using a constraint graph

Electron cryo-microscopy is a fast advancing biophysical technique to derive three-dimensional structures of large protein complexes. Using this technique, many density maps have been generated at intermediate resolution such as 6-10 ? resolution. Although it is challenging to derive the backbone of the protein directly from such density maps, secondary structure elements such as helices and β-sheets can be computationally detected. Our work in this paper provides an approach to enumerate the top-ranked possible topologies instead of enumerating the entire population of the topologies. This approach is particularly practical for large proteins. We developed a directed weighted graph, the topology graph, to represent the secondary structure assignment problem. We prove that the problem of finding the valid topology with the minimum cost is NP hard. We developed an O(N(2)2(N)) dynamic programming algorithm to identify the topology with the minimum cost. The test of 15 proteins suggests that our dynamic programming approach is feasible to work with proteins of much larger size than we could before. The largest protein in the test contains 18 helical sticks detected from the density map out of 33 helices in the protein.     

Electron cryomicroscopy of biological machines at subnanometer resolution

Advances in electron cryomicroscopy (cryo-EM) have made possible the structural determination of large biological machines in the resolution range of 6-9 angstroms. Rice dwarf virus and the acrosomal bundle represent two distinct types of machines amenable to cryo-EM investigations at subnanometer resolutions. However, calculating the density map is only the first step, and much analysis remains to extract structural insights and the mechanism of action in these machines. This paper will review the computational and visualization methodologies necessary for analysis (structure mining) of the computed cryo-EM maps of these machines. These steps include component segmentation, averaging based on local symmetry among components, density connectivity trace, incorporation of bioinformatics analysis, and fitting of high-resolution component data, if available. The consequences of these analyses can not only identify accurately some of the secondary structure elements of the molecular components in machines but also suggest structural mechanisms related to their biological functions.     

Cryo‐EM map interpretation and protein model‐building using iterative map segmentation

A procedure for building protein chains into maps produced by single‐particle electron cryo‐microscopy (cryo‐EM) is described. The procedure is similar to the way an experienced structural biologist might analyze a map, focusing first on secondary structure elements such as helices and sheets, then varying the contour level to identify connections between these elements. Since the high density in a map typically follows the main‐chain of the protein, the main‐chain connection between secondary structure elements can often be identified as the unbranched path between them with the highest minimum value along the path. This chain‐tracing procedure is then combined with finding side‐chain positions based on the presence of density extending away from the main path of the chain, allowing generation of a C_α model. The C_α model is converted to an all‐atom model and is refined against the map. We show that this procedure is as effective as other existing methods for interpretation of cryo‐EM maps and that it is considerably faster and produces models with fewer chain breaks than our previous methods that were based on approaches developed for crystallographic maps.     

Low-resolution density maps from atomic models: how stepping "back" can be a step "forward"

Atomic-resolution structures have had a tremendous impact on modern biological science. Much useful information also has been gleaned by merging and correlating atomic-resolution structural details with lower-resolution (15-40 A), three-dimensional (3D) reconstructions computed from images recorded with cryo-transmission electron microscopy (cryoTEM) procedures. One way to merge these structures involves reducing the resolution of an atomic model to a level comparable to a cryoTEM reconstruction. A low-resolution density map can be derived from an atomic-resolution structure by retrieving a set of atomic coordinates editing the coordinate file, computing structure factors from the model coordinates, and computing the inverse Fourier transform of the structure factors. This method is a useful tool for structural studies primarily in combination with 3D cryoTEM reconstructions. It has been used to assess the quality of 3D reconstructions, to determine corrections for the phase-contrast transfer function of the transmission electron microscope, to calibrate the dimensions and handedness of 3D reconstructions, to produce difference maps, to model features in macromolecules or macromolecular complexes, and to generate models to initiate model-based determination of particle orientation and origin parameters for 3D reconstruction.     

A machine learning approach for the identification of protein secondary structure elements from electron cryo-microscopy density maps

The accuracy of the secondary structure element (SSE) identification from volumetric protein density maps is critical for de-novo backbone structure derivation in electron cryo-microscopy (cryoEM). It is still challenging to detect the SSE automatically and accurately from the density maps at medium resolutions (～5-10 ?). We present a machine learning approach, SSELearner, to automatically identify helices and β-sheets by using the knowledge from existing volumetric maps in the Electron Microscopy Data Bank. We tested our approach using 10 simulated density maps. The averaged specificity and sensitivity for the helix detection are 94.9% and 95.8%, respectively, and those for the β-sheet detection are 86.7% and 96.4%, respectively. We have developed a secondary structure annotator, SSID, to predict the helices and β-strands from the backbone Cα trace. With the help of SSID, we tested our SSELearner using 13 experimentally derived cryo-EM density maps. The machine learning approach shows the specificity and sensitivity of 91.8% and 74.5%, respectively, for the helix detection and 85.2% and 86.5% respectively for the β-sheet detection in cryoEM maps of Electron Microscopy Data Bank. The reduced detection accuracy reveals the challenges in SSE detection when the cryoEM maps are used instead of the simulated maps. Our results suggest that it is effective to use one cryoEM map for learning to detect the SSE in another cryoEM map of similar quality.     

A database method for automated map interpretation in protein crystallography.

A significant portion of new protein structures contain folds that are related to those seen before. During the development of a computer program that can accurately position, in electron density maps, large protein domains with large structural deviations, it became apparent that the redundancy in protein folds could be used in a non trivial manner during a protein structure determination. As a result a computational procedure, Database Assisted Density Interpretation (DADI), was developed and tested to aid in the building of models in protein crystallography and to assist in interpreting electron density maps. The initial tests of the DADI procedure using a small database of protein domains are described. The philosophy is to first work with entire domains then with the secondary structure elements of these domains and finally with individual residues of the secondary structure elements via Monte Carlo, "chopping" and "clipping" procedures, respectively. The first test case was a traceable 3.2 A multiple isomorphous replacement with anomalous scattering (MIRAS) electron density map of a human topoisomerase I-DNA complex. The second test case uses poor electron density for the third domain of the diphtheria toxin repressor resulting from a molecular replacement solution with the first two domains. Despite the fact that a fairly small database was employed in these test cases, the DADI procedure was able to find a large portion of the protein backbone with very few errors. In the first case nearly 45% of the backbone and more than 80% of the secondary structure was placed automatically. In the second test case nearly 50% of the third domain was automatically detected. A particular encouraging result was that in both cases more than 75% of the beta sheet secondary structure was found automatically by the DADI procedure. Clearly, the procedures employed are promising avenues to exploit the current explosion of protein structures for the determination of future structures. Proteins 1999;36:526-541.     

Low-Resolution Density Maps from Atomic Models: How Stepping “Back” Can Be a Step “Forward”

Atomic-resolution structures have had a tremendous impact on modern biological science. Much useful information also has been gleaned by merging and correlating atomic-resolution structural details with lower-resolution (15–40 Å), three-dimensional (3D) reconstructions computed from images recorded with cryo-transmission electron microscopy (cryoTEM) procedures. One way to merge these structures involves reducing the resolution of an atomic model to a level comparable to a cryoTEM reconstruction. A low-resolution density map can be derived from an atomic-resolution structure by retrieving a set of atomic coordinates editing the coordinate file, computing structure factors from the model coordinates, and computing the inverse Fourier transform of the structure factors. This method is a useful tool for structural studies primarily in combination with 3D cryoTEM reconstructions. It has been used to assess the quality of 3D reconstructions, to determine corrections for the phase-contrast transfer function of the transmission electron microscope, to calibrate the dimensions and handedness of 3D reconstructions, to produce difference maps, to model features in macromolecules or macromolecular complexes, and to generate models to initiate model-based determination of particle orientation and origin parameters for 3D reconstruction.     

alpha-helix formation: discontinuous molecular dynamics on an intermediate-resolution protein model.

An intermediate-resolution model of small, homogeneous peptides is introduced, and discontinuous molecular dynamics simulation is applied to study secondary structure formation. Physically, each model residue consists of a detailed three-bead backbone and a simplified single-bead side-chain. Excluded volume and hydrogen bond interactions are constructed with discontinuous (i.e., hard-sphere and square-well) potentials. Simulation results show that the backbone motion of the model is limited to realistic regions of Phi-Psi conformational space. Model polyalanine chains undergo a locally cooperative transition to form alpha-helices that are stabilized by backbone hydrogen bonding, while model polyglycine chains tend to adopt nonhelical structures. When side-chain size is increased beyond a critical diameter, steric interactions prevent formation of long alpha-helices. These trends in helicity as a function of residue type have been well documented by experimental, theoretical, and simulation studies and demonstrate the ability of the intermediate-resolution model developed in this work to accurately mimic realistic peptide behavior. The efficient algorithm used permits observation of the complete helix-coil transition within 15 min on a single-processor workstation, suggesting that simulations of very long times are possible with this model.     

Bridging the information gap: computational tools for intermediate resolution structure interpretation

Due to large sizes and complex nature, few large macromolecular complexes have been solved to atomic resolution. This has lead to an under-representation of these structures, which are composed of novel and/or homologous folds, in the library of known structures and folds. While it is often difficult to achieve a high-resolution model for these structures, X-ray crystallography and electron cryomicroscopy are capable of determining structures of large assemblies at low to intermediate resolutions. To aid in the interpretation and analysis of such structures, we have developed two programs: helixhunter and foldhunter. Helixhunter is capable of reliably identifying helix position, orientation and length using a five-dimensional cross-correlation search of a three-dimensional density map followed by feature extraction. Helixhunter's results can in turn be used to probe a library of secondary structure elements derived from the structures in the Protein Data Bank (PDB). From this analysis, it is then possible to identify potential homologous folds or suggest novel folds based on the arrangement of alpha helix elements, resulting in a structure-based recognition of folds containing alpha helices. Foldhunter uses a six-dimensional cross-correlation search allowing a probe structure to be fitted within a region or component of a target structure. The structural fitting therefore provides a quantitative means to further examine the architecture and organization of large, complex assemblies. These two methods have been successfully tested with simulated structures modeled from the PDB at resolutions between 6 and 12 A. With the integration of helixhunter and foldhunter into sequence and structural informatics techniques, we have the potential to deduce or confirm known or novel folds in domains or components within large complexes.