Backbone cluster identification in proteins by a graph theoretical method

A graph theoretical algorithm has been developed to identify backbone clusters of residues in proteins. The identified clusters show protein sites with the highest degree of interactions. An adjacency matrix is constructed from the non-bonded connectivity information in proteins. The diagonalization of such a matrix yields eigenvalues and eigenvectors, which contain the information on clusters. In graph theory, distinct clusters can be obtained from the second lowest eigenvector components of the matrix. However, in an interconnected graph, all the points appear as one single cluster. We have developed a method of identifying highly interacting centers (clusters) in proteins by truncating the vector components of high eigenvalues. This paper presents in detail the method adopted for identifying backbone clusters and the application of the algorithm to families of proteins like RNase-A and globin. The objective of this study was to show the efficiency of the algorithm as well as to detect conserved or similar backbone packing regions in a particular protein family. Three clusters in topologically similar regions in the case of the RNase-A family and three clusters around the porphyrin ring in the globin family were observed. The predicted clusters are consistent with the features of the family of proteins such as the topology and packing density. The method can be applied to problems such as identification of domains and recognition of structural similarities in proteins.     

Clusters in alpha/beta barrel proteins: implications for protein structure, function, and folding: a graph theoretical approach

The alpha/beta barrel fold is adopted by most enzymes performing a variety of catalytic reactions, but with very low sequence similarity. In order to understand the stabilizing interactions important in maintaining the alpha/beta barrel fold, we have identified residue clusters in a dataset of 36 alpha/beta barrel proteins that have less than 10% sequence identity within themselves. A graph theoretical algorithm is used to identify backbone clusters. This approach uses the global information of the nonbonded interaction in the alpha/beta barrel fold for the clustering procedure. The nonbonded interactions are represented mathematically in the form of an adjacency matrix. On diagonalizing the adjacency matrix, clusters and cluster centers are obtained from the highest eigenvalue and its corresponding vector components. Residue clusters are identified in the strand regions forming the beta barrel and are topologically conserved in all 36 proteins studied. The residues forming the cluster in each of the alpha/beta protein are also conserved among the sequences belonging to the same family. The cluster centers are found to occur in the middle of the strands or in the C-terminal of the strands. In most cases, the residues forming the clusters are part of the active site or are located close to the active site. The folding nucleus of the alpha/beta fold is predicted based on hydrophobicity index evaluation of residues and identification of cluster centers. The predicted nucleation sites are found to occur mostly in the middle of the strands. Proteins 2001;43:103-112.     

Minimalist representations and the importance of nearest neighbor effects in protein folding simulations

In order to investigate the level of representation required to simulate folding and predict structure, we test the ability of a variety of reduced representations to identify native states in decoy libraries and to recover the native structure given the advanced knowledge of the very broad native Ramachandran basin assignments. Simplifications include the removal of the entire side-chain or the retention of only the Cbeta atoms. Scoring functions are derived from an all-atom statistical potential that distinguishes between atoms and different residue types. Structures are obtained by minimizing the scoring function with a computationally rapid simulated annealing algorithm. Results are compared for simulations in which backbone conformations are sampled from a Protein Data Bank-based backbone rotamer library generated by either ignoring or including a dependence on the identity and conformation of the neighboring residues. Only when the Cbeta atoms and nearest neighbor effects are included do the lowest energy structures generally fall within 4 A of the native backbone root-mean square deviation (RMSD), despite the initial configuration being highly expanded with an average RMSD > or = 10 A. The side-chains are reinserted into the Cbeta models with minimal steric clash. Therefore, the detailed, all-atom information lost in descending to a Cbeta-level representation is recaptured to a large measure using backbone dihedral angle sampling that includes nearest neighbor effects and an appropriate scoring function.     

TOUCHSTONE II: a new approach to ab initio protein structure prediction

We have developed a new combined approach for ab initio protein structure prediction. The protein conformation is described as a lattice chain connecting C(alpha) atoms, with attached C(beta) atoms and side-chain centers of mass. The model force field includes various short-range and long-range knowledge-based potentials derived from a statistical analysis of the regularities of protein structures. The combination of these energy terms is optimized through the maximization of correlation for 30 x 60,000 decoys between the root mean square deviation (RMSD) to native and energies, as well as the energy gap between native and the decoy ensemble. To accelerate the conformational search, a newly developed parallel hyperbolic sampling algorithm with a composite movement set is used in the Monte Carlo simulation processes. We exploit this strategy to successfully fold 41/100 small proteins (36 approximately 120 residues) with predicted structures having a RMSD from native below 6.5 A in the top five cluster centroids. To fold larger-size proteins as well as to improve the folding yield of small proteins, we incorporate into the basic force field side-chain contact predictions from our threading program PROSPECTOR where homologous proteins were excluded from the data base. With these threading-based restraints, the program can fold 83/125 test proteins (36 approximately 174 residues) with structures having a RMSD to native below 6.5 A in the top five cluster centroids. This shows the significant improvement of folding by using predicted tertiary restraints, especially when the accuracy of side-chain contact prediction is >20%. For native fold selection, we introduce quantities dependent on the cluster density and the combination of energy and free energy, which show a higher discriminative power to select the native structure than the previously used cluster energy or cluster size, and which can be used in native structure identification in blind simulations. These procedures are readily automated and are being implemented on a genomic scale.     

Automatic recognition of hydrophobic clusters and their correlation with protein folding units.

A method is described to objectively identify hydrophobic clusters in proteins of known structure. Clusters are found by examining a protein for compact groupings of side chains. Compact clusters contain seven or more residues, have an average of 65% hydrophobic residues, and usually occur in protein interiors. Although smaller clusters contain only side-chain moieties, larger clusters enclose significant portions of the peptide backbone in regular secondary structure. These clusters agree well with hydrophobic regions assigned by more intuitive methods and many larger clusters correlate with protein domains. These results are in striking contrast with the clustering algorithm of J. Heringa and P. Argos (1991, J Mol Biol 220:151-171). That method finds that clusters located on a protein's surface are not especially hydrophobic and average only 3-4 residues in size. Hydrophobic clusters can be correlated with experimental evidence on early folding intermediates. This correlation is optimized when clusters with less than nine hydrophobic residues are removed from the data set. This suggests that hydrophobic clusters are important in the folding process only if they have enough hydrophobic residues.     

Analysis of homodimeric protein interfaces by graph-spectral methods

The quaternary structures impart structural and functional credibility to proteins. In a multi-subunit protein, it is important to understand the factors that drive the association or dissociation of the subunits. It is a well known fact that both hydrophobic and charged interactions contribute to the stability of the protein interface. The interface residues are also known to be highly conserved. Though they are buried in the oligomer, these residues are either exposed or partially exposed in the monomer. It is felt that a systematic and objective method of identifying interface clusters and their analysis can significantly contribute to the identification of a residue or a collection of residues important for oligomerization. Recently, we have applied the techniques of graph-spectral methods to a variety of problems related to protein structure and folding. A major advantage of this methodology is that the problem is viewed from a global protein topology point of view rather than localized regions of the protein structure. In the present investigation, we have applied the methods of graph-spectral analysis to identify side chain clusters at the interface and the centers of these clusters in a set of homodimeric proteins. These clusters are analyzed in terms of properties such as amino acid composition, accessibility to solvent and conservation of residues. Interesting results such as participation of charged and aromatic residues like arginine, glutamic acid, histidine, phenylalanine and tyrosine, consistent with earlier investigations, have emerged from these analyses. Important additional information is that the residues involved are a part of a cluster(s) and that they are sequentially distant residues which have come closer to each other in the three-dimensional structure of the protein. These residues can easily be detected using our graph-spectral algorithm. This method has also been used to identify important residues ('hot spots') in dimerization and also to detect dimerization sites on the monomer. The residues predicted using the present algorithm have correlated well with the experiments indicating the efficacy of this method in predicting residues involved in dimer stability.     

Stabilizing interactions in the dimer interface of alpha-subunit in Escherichia coli RNA polymerase: a graph spectral and point mutation study

The formation of alpha(2) dimer in Escherichia coli core RNA polymerase (RNAP) is thought to be the first step toward the assembly of the functional enzyme. A large number of evidences indicate that the alpha-subunit dimerizes through its N-terminal domain (NTD). The crystal structures of the alpha-subunit NTD and that of a homologous Thermus aquaticus core RNAP are known. To identify the stabilizing interactions in the dimer interface of the alpha-NTD of E. coli RNAP, we identified side-chain clusters by using the crystal structure coordinates of E. coli alpha-NTD. A graph spectral algorithm was used to identify side-chain clusters. This algorithm considers the global nonbonded side-chain interactions of the residues for the clustering procedure and is unique in identifying residues that make the largest number of interactions among the residues that form clusters in a very quantitative way. By using this algorithm, a nine-residue cluster consisting of polar and hydrophobic residues was identified in the subunit interface adjacent to the hydrophobic core. The residues forming the cluster are relatively rigid regions of the interface, as measured by the thermal factors of the residues. Most of the cluster residues in the E. coli enzyme were topologically and sequentially conserved in the T. aquaticus RNAP crystal structure. Residues 35F and 46I were predicted to be important in the stability of the alpha-dimer interface, with 35F forming the center of the cluster. The predictions were tested by isolating single-point mutants alpha-F35A and alpha-I46S on the dimer interface, which were found to disrupt dimerization. Thus, the identified cluster at the edge of the dimer interface seems to be a vital component in stabilizing the alpha-NTD.     

Clustering of non-polar contacts in proteins.

MOTIVATION: Hydrophobic or non-polar contacts in proteins are important for protein folding, protein stability and protein-protein interactions. In particular, in the interior of a protein, in the hydrophobic core, a large number of such contacts are found. The residues involved in these contacts often form a tightly packed cluster of atoms. It is useful for the understanding of protein structure to be able to identify and analyse such clusters. RESULTS: Tools for hierarchical cluster analysis of non-polar contacts in proteins are described. These tools allow for efficient identification of clusters of non-polar interactions in proteins, both internal clusters and clusters involved in protein-protein contacts. The non-polar contacts are represented by a dendrogram structure, which is a simple approach for flexible identification of clusters by visual inspection. The tools are demonstrated on the structure of crambin, the structure of the complex between human growth hormone and the human growth hormone binding protein, and a pair of lipase/esterase structures. Availability: On request from the author.     

Localized, stereochemically sensitive hydrophobic packing in an early folding intermediate of dihydrofolate reductase from Escherichia coli

Mutational analysis was performed to probe the development of hydrophobic clusters during the early events in the folding of dihydrofolate reductase. Replacements were made in several hydrophobic subdomains to examine the roles of hydrophobicity and stereochemistry in the formation of kinetic intermediates. Amide protons in two of these clusters, including residues I91, I94, and I155, have been shown to be protected against solvent exchange within 13 ms of folding. Additional hydrophobic clusters were probed by substitutions at residues I2, I61, and L112; these residues are not protected from exchange until later in the folding reaction. Valine and leucine replacements at positions I91, I94, and I155 significantly diminish the formation of the burst phase kinetic intermediate, relative to the wild-type protein. In contrast, I2 and I61 are insensitive to these substitutions in the first 5 ms of the folding reaction, as is the replacement of L112 with either isoleucine or valine. These results demonstrate that the tightly packed core of dihydrofolate reductase is acquired in a non-uniform fashion, beginning in the submillisecond time frame. The progressive development of specific side-chain packing in localized hydrophobic clusters may be a common theme for complex protein folding reactions.     

Identification of domains and domain interface residues in multidomain proteins from graph spectral method

We present a novel method for the identification of structural domains and domain interface residues in proteins by graph spectral method. This method converts the three-dimensional structure of the protein into a graph by using atomic coordinates from the PDB file. Domain definitions are obtained by constructing either a protein backbone graph or a protein side-chain graph. The graph is constructed based on the interactions between amino acid residues in the three-dimensional structure of the proteins. The spectral parameters of such a graph contain information regarding the domains and subdomains in the protein structure. This is based on the fact that the interactions among amino acids are higher within a domain than across domains. This is evident in the spectra of the protein backbone and the side-chain graphs, thus differentiating the structural domains from one another. Further, residues that occur at the interface of two domains can also be easily identified from the spectra. This method is simple, elegant, and robust. Moreover, a single numeric computation yields both the domain definitions and the interface residues.     

Molecular dynamics simulations of a beta-hairpin fragment of protein G: balance between side-chain and backbone forces

How is the native structure encoded in the amino acid sequence? For the traditional backbone centric view, the dominant forces are hydrogen bonds (backbone) and phi-psi propensity. The role of hydrophobicity is non-specific. For the side-chain centric view, the dominant force of protein folding is hydrophobicity. In order to understand the balance between backbone and side-chain forces, we have studied the contributions of three components of a beta-hairpin peptide: turn, backbone hydrogen bonding and side-chain interactions, of a 16-residue fragment of protein G. The peptide folds rapidly and cooperatively to a conformation with a defined secondary structure and a packed hydrophobic cluster of aromatic side-chains. Our strategy is to observe the structural stability of the beta-hairpin under systematic perturbations of the turn region, backbone hydrogen bonds and the hydrophobic core formed by the side-chains, respectively. In our molecular dynamics simulations, the peptides are solvated. with explicit water molecules, and an all-atom force field (CFF91) is used. Starting from the original peptide (G41EWTYDDATKTFTVTE56), we carried out the following MD simulations. (1) unfolding at 350 K; (2) forcing the distance between the C(alpha) atoms of ASP47 and LYS50 to be 8 A; (3) deleting two turn residues (Ala48 and Thr49) to form a beta-sheet complex of two short peptides, GEWTYDD and KTFTVTE; (4) four hydrophobic residues (W43, Y45, F52 and T53) are replaced by a glycine residue step-by-step; and (5) most importantly, four amide hydrogen atoms (T44, D46, T53, and T55, which are crucial for backbone hydrogen bonding), are substituted by fluorine atoms. The fluorination not only makes it impossible to form attractive hydrogen bonding between the two beta-hairpin strands, but also introduces a repulsive force between the two strands due to the negative charges on the fluorine and oxygen atoms. Throughout all simulations, we observe that backbone hydrogen bonds are very sensitive to the perturbations and are easily broken. In contrast, the hydrophobic core survives most perturbations. In the decisive test of fluorination, the fluorinated peptide remains folded under our simulation conditions (5 ns, 278 K). Hydrophobic interactions keep the peptide folded, even with a repulsive force between the beta-strands. Thus, our results strongly support a side-chain centric view for protein folding.     

Refinement of the 7 Fe ferredoxin from Azotobacter vinelandii at 1.9 A resolution

The recently redetermined structure of the 7 Fe ferredoxin from Azotobacter vinelandii has been refined against a new 1.9 A data set. The crystallographic R-factor is 0.215 for all 9586 observed reflections 8.0 to 1.9 A. The model contains 106 amino acid residues, two Fe-S clusters and 21 water molecules. The root-mean-square deviations from ideality of bonds and angles are 0.014 A and 3.3 degrees, respectively. The refinement confirms the presence of two free cysteines: the thiol of C11 is in association with the side-chain of K100; the thiol of C24 is 3.35 A from inorganic sulfur of the [4 Fe-4 S] cluster. The refinement confirms a [3 Fe-4 S] model for the 3 Fe cluster. The two Fe-S clusters have similar bond distances and angles. The structure of the protein for residues 1 to 57 superposes within 0.85 A on residues 1 to 53 of the 8 Fe ferredoxin structure for main-chain N, CA and C atoms, if residues 9, 10, 29 and 30 of 7 Fe ferredoxin are omitted. These residues are part of two loops in contact with residues of the extended C-terminal chain of 7 Fe ferredoxin.     

The folding thermodynamics and kinetics of crambin using an all-atom Monte Carlo simulation

We present a novel Monte Carlo simulation of protein folding, in which all heavy atoms are represented as interacting hard spheres. This model includes all degrees of freedom relevant to folding, all side-chain and backbone torsions, and uses a Go potential. In this study, we focus on the 46 residue alpha/beta protein crambin and two of its structural components, the helix and helix hairpin. For a wide range of temperatures, we recorded multiple folding events of these three structures from random coils to native conformations that differ by less than 1 A C(alpha) dRMS from their crystal structure coordinates. The thermodynamics and kinetic mechanism of the helix-coil transition obtained from our simulation shows excellent agreement with currently available experimental and molecular dynamics data. Based on insights obtained from folding its smaller structural components, a possible folding mechanism for crambin is proposed. We observed that the folding occurs via a cooperative, first order-like process, and that many folding pathways to the native state exist. One particular sequence of events constitutes a "fast-folding" pathway where kinetic traps are avoided. At very low temperatures, a kinetic trap arising from the incorrect packing of side-chains was observed. These results demonstrate that folding to the native state can be observed in a reasonable amount of time on desktop computers even when an all-atom representation is used, provided the energetics sufficiently stabilize the native state.     

Partial atomic charges of amino acids in proteins

Using a semiempirical quantum mechanical procedure (FCPAC) we have calculated the partial atomic charges of amino acids from 494 high-resolution protein structures. To analyze the influence of the protein's environment, we considered each residue under two conditions: either as the center of a tripeptide with PDB structure geometry (free) or as the center of 13-16 amino acid clusters extracted from the PDB structure (buried). The partial atomic charges from residues in helices and in sheets were separated. The FCPAC partial atomic charges of the Cbeta and Calpha of most residues correlate with their helix propensity, positively for Cbeta and negatively for Calpha (r2 = 0.76 and 0.6, respectively). The main consequence of burying residues in proteins is the polarization of the backbone C=O bond, which is more pronounced in helices than in sheets. The average shift of the oxygen partial charges that results from burying is -0.120 in helix and -0.084 in sheet with the charge of the proton as unit. Linear correlations are found between the average NMR chemical shifts and the average FCPAC partial charges of Calpha (r2 = 0.8-0.85), N (r3 = 0.67-0.72), and Cbeta (r2 = 0.62) atoms. Correlations for helix and beta-sheet FCPAC partial charges show parallel regressions, suggesting that the charge variations due to burying in proteins differentiate between the dihedral angle effects and the polarization of backbone atoms.     

Local interactions drive the formation of nonnative structure in the denatured state of human alpha-lactalbumin: a high resolution structural characterization of a peptide model in aqueous solution.

There are a small number of peptides derived from proteins that have a propensity to adopt structure in aqueous solution which is similar to the structure they possess in the parent protein. There are far fewer examples of protein fragments which adopt stable nonnative structures in isolation. Understanding how nonnative interactions are involved in protein folding is crucial to our understanding of the topic. Here we show that a small, 11 amino acid peptide corresponding to residues 101-111 of the protein alpha-lactalbumin is remarkably structured in isolation in aqueous solution. The peptide has been characterized by 1H NMR, and 170 ROE-derived constraints were used to calculate a structure. The calculations yielded a single, high-resolution structure for residues 101-107 that is nonnative in both the backbone and side-chain conformations. In the pH 6.5 crystal structure, residues 101-105 are in an irregular turn-like conformation and residues 106-111 form an alpha-helix. In the pH 4.2 crystal structure, residues 101-105 form an alpha-helix, and residues 106-111 form a loopike structure. Both of these structures are significantly different from the conformation adopted by our peptide. The structure in the peptide model is primarily the result of local side-chain interactions that force the backbone to adopt a nonnative 310/turn-like structure in residues 103-106. The structure in aqueous solution was compared to the structure in 30% trifluoroethanol (TFE), and clear differences were observed. In particular, one of the side-chain interactions, a hydrophobic cluster involving residues 101-105, is different in the two solvents and residues 107-111 are considerably more ordered in 30% TFE. The implications of the nonnative structure for the folding of alpha-lactalbumin is discussed.     

Solution conformation of cytochrome c-551 from Pseudomonas stutzeri ZoBell determined by NMR.

1H NMR spectroscopy and solution structure computations have been used to examine ferrocytochrome c-551 from Pseudomonas stutzeri ZoBell (ATCC 14405). Resonance assignments are proposed for all main-chain and most side-chain protons. Stereospecific assignments were also made for some of the beta-methylene protons and valine methyl protons. Distance constraints were determined based upon nuclear Overhauser enhancements between pairs of protons. Dihedral angle constraints were determined from estimates of scalar coupling constants and intra-residue NOEs. Twenty structures were calculated by distance geometry and refined by energy minimization and simulated annealing on the basis of 1012 interproton distance and 74 torsion angle constraints. Both the main-chain and side-chain atoms are well defined except for two terminal residues, and some side-chain atoms located on the molecular surface. The average root mean squared deviation in the position for equivalent atoms between the 20 individual structures and the mean structure obtained by averaging their coordinates is 0.56 +/- 0.10 A for the main-chain atoms, and 0.95 +/- 0.09 A for all nonhydrogen atoms of residue 3 to 80 plus the heme group. The average structure was compared with an analogous protein, cytochrome c-551 from pseudomonas stutzeri. The main-chain folding patterns are very consistent, but there are some differences, some of which can be attributed to the loss of normally conserved aromatic residues in the ZoBell c-551.     

The fe2+ site of photosynthetic reaction centers probed by multiple scattering x-ray absorption fine structure spectroscopy: improving structure resolution in dry matrices

We report on the x-ray absorption fine structure of the Fe(2+) site in photosynthetic reaction centers from Rhodobacter sphaeroides. Crystallographic studies show that Fe(2+) is ligated with four N(epsilon) atoms from four histidine (His) residues and two O(epsilon) atoms from a Glu residue. By considering multiple scattering contributions to the x-ray absorption fine structure function, we improved the structural resolution of the site: His residues were split into two groups, characterized by different Fe-N(epsilon) distances, and two distinct Fe-O(epsilon) bond lengths resolved. The effect of the environment was studied by embedding the reaction centers into a polyvinyl alcohol film and into a dehydrated trehalose matrix. Incorporation into trehalose caused elongation in one of the two Fe-N(epsilon) distances, and in one Fe-O(epsilon) bond length, compared with the polyvinyl alcohol film. The asymmetry detected in the cluster of His residues and its response to incorporation into trehalose are ascribed to the hydrogen bonds between two His residues and the quinone acceptors. The structural distortions observed in the trehalose matrix indicate a strong interaction between the reaction-centers surface and the water-trehalose matrix, which propagates deeply into the interior of the protein. The absence of matrix effects on the Debye-Waller factors is brought back to the static heterogeneity and rigidity of the ligand cluster.     

Protein Structure Classification Based on Conserved Hydrophobic Residues

Protein folding is frequently guided by local residue interactions that form clusters in the protein core. The interactions between residue clusters serve as potential nucleation sites in the folding process. Evidence postulates that the residue interactions are governed by the hydrophobic propensities that the residues possess. An array of hydrophobicity scales has been developed to determine the hydrophobic propensities of residues under different environmental conditions. In this work, we propose a graph-theory-based data mining framework to extract and isolate protein structural features that sustain invariance in evolutionary-related proteins, through the integrated analysis of five well-known hydrophobicity scales over the 3D structure of proteins. We hypothesize that proteins of the same homology contain conserved hydrophobic residues and exhibit analogous residue interaction patterns in the folded state. The results obtained demonstrate that discriminatory residue interaction patterns shared among proteins of the same family can be employed for both the structural and the functional annotation of proteins. We obtained on the average 90 percent accuracy in protein classification with a significantly small feature vector compared to previous results in the area. This work presents an elaborate study, as well as validation evidence, to illustrate the efficacy of the method and the correctness of results reported.     

Applications of graph theory in protein structure identification

There is a growing interest in the identification of proteins on the proteome wide scale. Among different kinds of protein structure identification methods, graph-theoretic methods are very sharp ones. Due to their lower costs, higher effectiveness and many other advantages, they have drawn more and more researchers' attention nowadays. Specifically, graph-theoretic methods have been widely used in homology identification, side-chain cluster identification, peptide sequencing and so on. This paper reviews several methods in solving protein structure identification problems using graph theory. We mainly introduce classical methods and mathematical models including homology modeling based on clique finding, identification of side-chain clusters in protein structures upon graph spectrum, and de novo peptide sequencing via tandem mass spectrometry using the spectrum graph model. In addition, concluding remarks and future priorities of each method are given.