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.

A graph-theoretic algorithm for comparative modeling of protein structure

The interconnected nature of interactions in protein structures appears to be the major hurdle in preventing the construction of accurate comparative models. We present an algorithm that uses graph theory to handle this problem. Each possible conformation of a residue in an amino acid sequence is represented using the notion of a node in a graph. Each node is given a weight based on the degree of the interaction between its side-chain atoms and the local main-chain atoms. Edges are then drawn between pairs of residue conformations/nodes that are consistent with each other (i.e. clash-free and satisfying geometrical constraints). The edges are weighted based on the interactions between the atoms of the two nodes. Once the entire graph is constructed, all the maximal sets of completely connected nodes (cliques) are found using a clique-finding algorithm. The cliques with the best weights represent the optimal combinations of the various main-chain and side-chain possibilities, taking the respective environments into account. The algorithm is used in a comparative modeling scenario to build side-chains, regions of main chain, and mix and match between different homologs in a context-sensitive manner. The predictive power of this method is assessed by applying it to cases where the experimental structure is not known in advance.

Determination of the conformation of folding initiation sites in proteins by computer simulation

Experimental evidence and theoretical models both suggest that protein folding begins by specific short regions of the polypeptide chain intermittently assuming conformations close to their final ones. The independent folding properties and small size of these folding initiation sites make them suitable subjects for computational methods aimed at deriving structure from sequence. We have used a torsion space Monte Carlo procedure together with an all-atom free energy function to investigate the folding of a set of such sites. The free energy function is derived by a potential of mean force analysis of experimental protein structures. The most important contributions to the total free energy are the local main chain electrostatics, main chain hydrogen bonds, and the burial of nonpolar area. Six proposed independent folding units and four control peptides 11-14 residues long have been investigated. Thirty Monte Carlo simulations were performed on each peptide, starting from different random conformations. Five of the six folding units adopted conformations close to the experimental ones in some of the runs. None of the controls did so, as expected. The generated conformations which are close to the experimental ones have among the lowest free energies encountered, although some less native like low free energy conformations were also found. The effectiveness of the method on these peptides, which have a wide variety of experimental conformations, is encouraging in two ways: First, it provides independent evidence that these regions of the sequences are able to adopt native like conformations early in folding, and therefore are most probably key components of the folding pathways. Second, it demonstrates that available simulation methods and free energy functions are able to produce reasonably accurate structures. Extensions of the methods to the folding of larger portions of proteins are suggested.