Structural search and retrieval using a tableau representation of protein folding patterns

Comparison and classification of folding patterns from a database of protein structures is crucial to understand the principles of protein architecture, evolution and function. Current search methods for proteins with similar folding patterns are slow and computationally intensive. The sharp growth in the number of known protein structures poses severe challenges for methods of structural comparison. There is a need for methods that can search the database of structures accurately and rapidly. We provide several methods to search for similar folding patterns using a concise tableau representation of proteins that encodes the relative geometry of secondary structural elements. Our first approach allows the extraction of identical and very closely-related protein folding patterns in constant-time (per hit). Next, we address the hard computational problem of extraction of maximally-similar subtableaux, when comparing two tableaux. We solve the problem using Quadratic and Linear integer programming formulations and demonstrate their power to identify subtle structural similarities, especially when protein structures significantly diverge. Finally, we describe a rapid and accurate method for comparing a query structure against a database of protein domains, TableauSearch. TableauSearch is rapid enough to search the entire structural database in seconds on a standard desktop computer. Our analysis of TableauSearch on many queries shows that the method is very accurate in identifying similarities of folding patterns, even between distantly related proteins. AVAILABILITY: A web server implementing the TableauSearch is available from http://hollywood.bx.psu.edu/TabSearch.     

A new representation for protein secondary structure prediction based on frequent patterns

MOTIVATION: A new representation for protein secondary structure prediction based on frequent amino acid patterns is described and evaluated. We discuss in detail how to identify frequent patterns in a protein sequence database using a level-wise search technique, how to define a set of features from those patterns and how to use those features in the prediction of the secondary structure of a protein sequence using support vector machines (SVMs). RESULTS: Three different sets of features based on frequent patterns are evaluated in a blind testing setup using 150 targets from the EVA contest and compared to predictions of PSI-PRED, PHD and PROFsec. Despite being trained on only 940 proteins, a simple SVM classifier based on this new representation yields results comparable to PSI-PRED and PROFsec. Finally, we show that the method contributes significant information to consensus predictions. AVAILABILITY: The method is available from the authors upon request.     

Weak correlation between predictive power of individual sequence patterns and overall prediction accuracy in proteins

Patterns in amino acid properties (polar, hydrophobic, etc.) that characterize secondary structure motifs are derived from a database containing 75 protein structures, with the aim of circumventing the limitations due to data base size so as to increase structure prediction score. Many such sequence-structure associations with high intrinsic predictive power are found, which turn out to be correct 78% of the time when applied individually to proteins outside the learning set. Based on these associations, a prediction method is developed, which reaches the score of 62% on the 3 states alpha-helix, beta-strand, and loop, without using additional constraints. Though this score is quite good compared to that of other available prediction methods, it is much lower than could be expected from the high intrinsic predictive power of the associations used. The reasons underlying this surprising result, which indicate that prediction score and intrinsic predictive power are only weakly coupled, are discussed. It is also shown that the size of the present database still seriously limits prediction scores, even when property patterns are used, and that higher scores are expected in large databases. Clues are provided on the relative influence of neglecting spatial interactions on prediction efficiency, suggesting that, in sufficiently large databases, predicted secondary structures would correspond to those formed early in the folding process. This hypothesis is tested by confronting present predictions with available experimental data on early protein folding intermediates and on small peptides that adopt a relatively stable conformation in water. Although admittedly there are still too few such data, results suggest that the hypothesis might be well founded.     

A classification of disulfide patterns and its relationship to protein structure and function

We report a detailed classification of disulfide patterns to further understand the role of disulfides in protein structure and function. The classification is applied to a unique searchable database of disulfide patterns derived from the SwissProt and Pfam databases. The disulfide database contains seven times the number of publicly available disulfide annotations. Each disulfide pattern in the database captures the topology and cysteine spacing of a protein domain. We have clustered the domains by their disulfide patterns and visualized the results using a novel representation termed the "classification wheel." The classification is applied to 40,620 protein domains with 2-10 disulfides. The effectiveness of the classification is evaluated by determining the extent to which proteins of similar structure and function are grouped together through comparison with the SCOP and Pfam databases, respectively. In general, proteins with similar disulfide patterns have similar structure and function, even in cases of low sequence similarity, and we illustrate this with specific examples. Using a measure of disulfide topology complexity, we find that there is a predominance of less complex topologies. We also explored the importance of loss or addition of disulfides to protein structure and function by linking classification wheels through disulfide subpattern comparisons. This classification, when coupled with our disulfide database, will serve as a useful resource for searching and comparing disulfide patterns, and understanding their role in protein structure, folding, and stability. Proteins in the disulfide clusters that do not contain structural information are prime candidates for structural genomics initiatives, because they may correspond to novel structures.     

How do potentials derived from structural databases relate to “true” potentials?

Knowledge-based potentials are used widely in protein folding and inverse folding algorithms. Two kinds of derivation methods are used. (1) The interactions in a database of known protein structures are assumed to obey a Boltzmann distribution. (2) The stability of the native folds relative to a manifold of misfolded structures is optimized. Here, a set of previously derived contact and secondary structure propensity potentials, taken as the "true" potentials, are employed to construct an artificial protein structural database from protein fragments. Then, new sets of potentials are derived to see how they are related to the true potentials. Using the Boltzmann distribution method, when the stability of the structures in the database lies within a certain range, both contact potentials and secondary structure propensities can be derived separately with remarkable accuracy. In general, the optimization method was found to be less accurate due to errors in the "excess energy" contribution. When the excess energy terms are kept as a constraint, the true potentials are recovered exactly.     

Influence of protein structure databases on the predictive power of statistical pair potentials

A long standing goal in protein structure studies is the development of reliable energy functions that can be used both to verify protein models derived from experimental constraints as well as for theoretical protein folding and inverse folding computer experiments. In that respect, knowledge-based statistical pair potentials have attracted considerable interests recently mainly because they include the essential features of protein structures as well as solvent effects at a low computing cost. However, the basis on which statistical potentials are derived have been questioned. In this paper, we investigate statistical pair potentials derived from protein three-dimensional structures, addressing in particular questions related to the form of these potentials, as well as to the content of the database from which they are derived. We have shown that statistical pair potentials depend on the size of the proteins included in the database, and that this dependence can be reduced by considering only pairs of residue close in space (i.e., with a cutoff of 8 Å). We have shown also that statistical potentials carry a memory of the quality of the database in terms of the amount and diversity of secondary structure it contains. We find, for example, that potentials derived from a database containing α-proteins will only perform best on α-proteins in fold recognition computer experiments. We believe that this is an overall weakness of these potentials, which must be kept in mind when constructing a database. Proteins 31:139–149, 1998. © 1998 Wiley-Liss, Inc.     

Backbone dynamics, fast folding, and secondary structure formation in helical proteins and peptides

We discuss the construction of a simple, off-lattice model protein with a comparatively detailed representation of the protein backbone, and use it to address some general aspects of the folding kinetics of a small helical protein and two peptide fragments. The model makes use of an associative memory hamiltonian to smoothly interpolate between the limits of a native contact only, or Go, potential and a statistical pair potential derived from a database of known structures. We have observed qualitatively different behavior in these two limits. In the Go limit, we see apparently barrier-less folding. As we increase the roughness of the model energy landscape, we can observe the emergence of the characteristic activated temperature dependence previously seen in lattice studies and analytical theories. We are also able to study the dependence of the folding kinetics on local interactions such as hydrogen bonds, and we discuss the implications of these results for the formation of secondary structure at intermediate stages of the folding reaction.     

Local structure-based sequence profile database for local and global protein structure predictions

MOTIVATION: A large body of evidence suggests that protein structural information is frequently encoded in local sequences-sequence-structure relationships derived from local structure/sequence analyses could significantly enhance the capacities of protein structure prediction methods. In this paper, the prediction capacity of a database (LSBSP2) that organizes local sequence-structure relationships encoded in local structures with two consecutive secondary structure elements is tested with two computational procedures for protein structure prediction. The goal is twofold: to test the folding hypothesis that local structures are determined by local sequences, and to enhance our capacity in predicting protein structures from their amino acid sequences. RESULTS: The LSBSP2 database contains a large set of sequence profiles derived from exhaustive pair-wise structural alignments for local structures with two consecutive secondary structure elements. One computational procedure makes use of the PSI-BLAST alignment program to predict local structures for testing sequence fragments by matching the testing sequence fragments onto the sequence profiles in the LSBSP2 database. The results show that 54% of the test sequence fragments were predicted with local structures that match closely with their native local structures. The other computational procedure is a filter system that is capable of removing false positives as possible from a set of PSI-BLAST hits. An assessment with a large set of non-redundant protein structures shows that the PSI-BLAST + filter system improves the prediction specificity by up to two-fold over the prediction specificity of the PSI-BLAST program for distantly related protein pairs. Tests with the two computational procedures above demonstrate that local sequence-structure relationships can indeed enhance our capacity in protein structure prediction. The results also indicate that local sequences encoded with strong local structure propensities play an important role in determining the native state folding topology.     

A computer model to dynamically simulate protein folding: studies with crambin

The current work describes a simplified representation of protein structure with uses in the simulation of protein folding. The model assumes that a protein can be represented by a freely rotating rigid chain with a single atom approximating the effect of each side chain. Potentials describing the attraction or repulsion between different types of amino acids are determined directly from the distribution of amino acids in the database of known protein structures. The optimization technique of simulated annealing has been used to dynamically sample the conformations available to this simple model, allowing the protein to evolve from an extended, random coil into a compact globular structure. Many characteristics expected of true proteins, such as the sequence-dependent formation of secondary structure, the partitioning of hydrophobic residues, and specific disulfide pairing, are reproduced by the simulation, suggesting the model may accurately simulate the folding process.     

New classification of supersecondary structures of sandwich-like proteins uncovers strict patterns of strand assemblage

To describe the supersecondary structure (SSS) of beta sandwich-like proteins (SPs), we introduce a structural unit called the "strandon." A strandon is defined as a set of sequentially consecutive strands connected by hydrogen bonds in 3D structures. Representing beta-proteins as the assembly of strandons exposes the underlying similarities in their SSS and enables us to construct a novel classification scheme of SPs. Classification of all known SPs is based on shared supersecondary structural features and is presented in the SSS database (http://binfs.umdnj.edu/sssdb/). Analysis of the SSS reveals two common specific patterns. The first pattern defines the arrangement of strandons and was found in 95% of all examined SPs. The second pattern establishes the ordering of strands in the protein domain and was observed in 82% of the analyzed SPs. Knowledge of these two patterns that uncover the spatial arrangement of strands will likely prove useful in protein structure prediction.     

Physical principles of protein structure and protein folding

Physical principles determining the protein structure and protein folding are reviewed: (i) the molecular theory of protein secondary structure and the method of its prediction based on this theory; (ii) the existence of a limited set of thermodynamically favourable folding patterns of α- and β-regions in a compact globule which does not depend on the details of the amino acid sequence; (iii) the moderns approaches to the prediction of the folding patterns of α- and β-regions in concrete proteins; (iv) experimental approaches to the mechanism of protein folding. The review reflects theoretical and experimental works of the author and his collaborators as well as those of other groups.     

Database of homology-derived protein structures and the structural meaning of sequence alignment

The database of known protein three-dimensional structures can be significantly increased by the use of sequence homology, based on the following observations. (1) The database of known sequences, currently at more than 12,000 proteins, is two orders of magnitude larger than the database of known structures. (2) The currently most powerful method of predicting protein structures is model building by homology. (3) Structural homology can be inferred from the level of sequence similarity. (4) The threshold of sequence similarity sufficient for structural homology depends strongly on the length of the alignment. Here, we first quantify the relation between sequence similarity, structure similarity, and alignment length by an exhaustive survey of alignments between proteins of known structure and report a homology threshold curve as a function of alignment length. We then produce a database of homology-derived secondary structure of proteins (HSSP) by aligning to each protein of known structure all sequences deemed homologous on the basis of the threshold curve. For each known protein structure, the derived database contains the aligned sequences, secondary structure, sequence variability, and sequence profile. Tertiary structures of the aligned sequences are implied, but not modeled explicitly. The database effectively increases the number of known protein structures by a factor of five to more than 1800. The results may be useful in assessing the structural significance of matches in sequence database searches, in deriving preferences and patterns for structure prediction, in elucidating the structural role of conserved residues, and in modeling three-dimensional detail by homology.     

Analyzing the Interplay Between Secondary and Tertiary Structure Predictions in Folding Simulations with a Genetic Algorithm

Three different strategies to tackle mispredictions from incorrect secondary structure prediction are analysed using 21 small proteins (22-121 amino acids; 1-6 secondary structure elements) with known three dimensional structures: (1) Testing accuracy of different secondary structure predictions and improving them by combinations, (2) correcting mispredictions exploiting protein folding simulations with a genetic algorithm and (3) applying and combining experimental data to refine predictions both for secondary structure and tertiary fold. We demonstrate that predictions from secondary structure prediction programs can be efficiently combined to reduce prediction errors from missed secondary structure elements. Further, up to two secondary structure elements (helices, strands) missed by secondary structure prediction were corrected by the genetic algorithm simulation. Finally, we show how input from experimental data is exploited to refine the predictions obtained.Electronic Supplementary Material available.     

PFRES: protein fold classification by using evolutionary information and predicted secondary structure

MOTIVATION: The number of protein families has been estimated to be as small as 1000. Recent study shows that the growth in discovery of novel structures that are deposited into PDB and the related rate of increase of SCOP categories are slowing down. This indicates that the protein structure space will be soon covered and thus we may be able to derive most of remaining structures by using the known folding patterns. Present tertiary structure prediction methods behave well when a homologous structure is predicted, but give poorer results when no homologous templates are available. At the same time, some proteins that share twilight-zone sequence identity can form similar folds. Therefore, determination of structural similarity without sequence similarity would be beneficial for prediction of tertiary structures. RESULTS: The proposed PFRES method for automated protein fold classification from low identity (<35%) sequences obtains 66.4% and 68.4% accuracy for two test sets, respectively. PFRES obtains 6.3-12.4% higher accuracy than the existing methods. The prediction accuracy of PFRES is shown to be statistically significantly better than the accuracy of competing methods. Our method adopts a carefully designed, ensemble-based classifier, and a novel, compact and custom-designed feature representation that includes nearly 90% less features than the representation of the most accurate competing method (36 versus 283). The proposed representation combines evolutionary information by using the PSI-BLAST profile-based composition vector and information extracted from the secondary structure predicted with PSI-PRED. AVAILABILITY: The method is freely available from the authors upon request.     

Mimicking the action of folding chaperones in molecular dynamics simulations: Application to the refinement of homology-based protein structures

A novel method for the refinement of misfolded protein structures is proposed in which the properties of the solvent environment are oscillated in order to mimic some aspects of the role of molecular chaperones play in protein folding in vivo. Specifically, the hydrophobicity of the solvent is cycled by repetitively altering the partial charges on solvent molecules (water) during a molecular dynamics simulation. During periods when the hydrophobicity of the solvent is increased, intramolecular hydrogen bonding and secondary structure formation are promoted. During periods of increased solvent polarity, poorly packed regions of secondary structures are destabilized, promoting structural rearrangement. By cycling between these two extremes, the aim is to minimize the formation of long-lived intermediates. The approach has been applied to the refinement of structural models of three proteins generated by using the ROSETTA procedure for ab initio structure prediction. A significant improvement in the deviation of the model structures from the corresponding experimental structures was observed. Although preliminary, the results indicate computationally mimicking some functions of molecular chaperones in molecular dynamics simulations can promote the correct formation of secondary structure and thus be of general use in protein folding simulations and in the refinement of structural models of small- to medium-size proteins.     

Identifying the Tertiary Fold of Small Proteins with Different Topologies from Sequence and Secondary Structure using the Genetic Algorithm and Extended Criteria Specific for Strand Regions

Grid-free protein folding simulations based on sequence and secondary structure knowledge (using mostly experimentally determined secondary structure information but also analysing results from secondary structure predictions) were investigated using the genetic algorithm, a backbone representation, and standard dihedral angular conformations. Optimal structures are selected according to basic protein building principles. Having previously applied this approach to proteins with helical topology, we have now developed additional criteria and weights for β-strand- containing proteins, validated them on four small β-strand-rich proteins with different topologies, and tested the general performance of the method on many further examples from known protein structures with mixed secondary structural type and less than 100 amino acid residues.Topology predictions close to the observed experimental structures were obtained in four test cases together with fitness values that correlated with the similarity of the predicted topology to the observed structures. Root-mean-square deviation values of C^αatoms in the superposed predicted and observed structures, the latter of which had different topologies, were between 4.5 and 5.5 Å (2.9 to 5.1 Å without loops). Including 15 further protein examples with unique folds, root-mean-square deviation values ranged between 1.8 and 6.9 Å with loop regions and averaged 5.3 Å and 4.3 Å, including and excluding loop regions, respectively.     

Patterns,structures, and amino acid frequencies in structural building blocks,a protein secondary structure classification scheme

To study local structures in proteins, we previously developed an autoassociative artificial neural network (autoANN) and clustering tool to discover intrinsic features of macromolecular structures. The hidden unit activations computed by the trained autoANN are a convenient low-dimensional encoding of the local protein backbone structure. Clustering these activation vectors results in a unique classification of protein local structural features called Structural Building Blocks (SBBs). Here we describe application of this method to a larger database of proteins, verification of the applicability of this method to structure classification, and subsequent analysis of amino acid frequencies and several commonly occurring patterns of SBBs. The SBB classification method has several interesting properties: 1) it identifies the regular secondary structures, α helix and β strand; 2) it consistently identifies other local structure features (e.g., helix caps and strand caps); 3) strong amino acid preferences are revealed at some positions in some SBBs; and 4) distinct patterns of SBBs occur in the “random coil” regions of proteins. Analysis of these patterns identifies interesting structural motifs in the protein backbone structure, indicating that SBBs can be used as “building blocks” in the analysis of protein structure. This type of pattern analysis should increase our understanding of the relationship between protein sequence and local structure, especially in the prediction of protein structures. © 1997 Wiley-Liss, Inc.     

The relation between mRNA folding and protein structure

About 200 mRNA sequences of Escherichia coli and human with matching protein secondary structure data were studied. The mRNA folding for each native sequence and for corresponding randomized sequences was calculated through free energy minimization. We have found that the folding energy of mRNA segments in different protein secondary structures is significantly different. The average Z score is more negative for regular secondary structure (alpha-helix and beta-strand) than that for coil. This suggests that the codon choice in native mRNA sequence coding for protein regular structure contributes more to the mRNA folding stability.