Novel approach for alpha-helical topology prediction in globular proteins: generation of interhelical restraints

The protein folding problem represents one of the most challenging problems in computational biology. Distance constraints and topology predictions can be highly useful for the folding problem in reducing the conformational space that must be searched by deterministic algorithms to find a protein structure of minimum conformational energy. We present a novel optimization framework for predicting topological contacts and generating interhelical distance restraints between hydrophobic residues in alpha-helical globular proteins. It should be emphasized that since the model does not make assumptions about the form of the helices, it is applicable to all alpha-helical proteins, including helices with kinks and irregular helices. This model aims at enhancing the ASTRO-FOLD protein folding approach of Klepeis and Floudas (Journal of Computational Chemistry 2003;24:191-208), which finds the structure of global minimum conformational energy via a constrained nonlinear optimization problem. The proposed topology prediction model was evaluated on 26 alpha-helical proteins ranging from 2 to 8 helices and 35 to 159 residues, and the best identified average interhelical distances corresponding to the predicted contacts fell below 11 A in all 26 of these systems. Given the positive results of applying the model to several protein systems, the importance of interhelical hydrophobic-to-hydrophobic contacts in determining the folding of alpha-helical globular proteins is highlighted.     

Chaotic Artificial Bee Colony algorithm: A new approach to the problem of minimization of energy of the 3D protein structure

Prediction of the three-dimensional structure of a protein from its amino acid sequence can be considered as a global optimization problem. In this paper, the Chaotic Artificial Bee Colony (CABC) algorithm was introduced and applied to 3D protein structure prediction. Based on the 3D off-lattice AB model, the CABC algorithm combines global search and local search of the Artificial Bee Colony (ABC) algorithm with the chaotic search algorithm to avoid the problem of premature convergence and easily trapping the local optimum solution. The experiments carried out with the popular Fibonacci sequences demonstrate that the proposed algorithm provides an effective and high-performance method for protein structure prediction.     

基于遗传算法的蛋白质结构预测方法

遗传算法源于自然界的进化规律,是一种自适应启发式概率性迭代式全局搜索算法。本文主要介绍了GA的基本原理,算法及优点;总结GA在蛋白质结构预测中建立模型和执行策略,以及多种算法相互结合预测蛋白质结构的研究进展。     

Atomic structure of a CK2alpha human kinase by microfocus diffraction of extra-small microcrystals grown with nanobiofilm template

Extra-small microcrystals of a human kinase CK2alpha were obtained for the first time by the optimization of a recent protein crystallization method based on highly packed protein nanofilm template. Protein crystal induction and growth appear indeed optimal at high surface pressure of the film template yielding high protein orientation and packing. The resulting extra-small CK2alpha microcrystals (of about 20 microm in diameter) was subsequently used for synchrotron radiation diffraction data collection, which proves possible by means of the Microfocus Beamline at the ESRF Synchrotron in Grenoble. The quality of the resulting crystal diffraction patterns and of its resulting atomic structure at 2.4 A resolution proves the unique validity of the above two combined frontier technologies in defining a new approach to structural proteomics capable to solve the atomic structure of proteins so far never been crystallized and of pharmaceutical relevance. Physical explanation in terms of template dipole moments and possibility of generalization of this method to the wide class of proteins not yet crystallized are finally discussed. The structure of our CK2alpha mutant is in the Protein Data Bank (PDB ID Code 1NA7, deposited on 27 November 2002).     

NMR restraint analysis of transforming growth factor alpha: a key component for NMR structure refinement.

Structures of the protein, transforming growth factor alpha (TGF-alpha), have been derived from NMR data using distance geometry and subsequent energy refinement. Analysis of the sequential NOE distance bounds using a template algorithm provides a check for consistency in the calculation of bounds, stereospecific assignment of prochiral centers, and secondary structure assignment. Application of the template algorithm to the long range NOEs found within the NMR data sets collected at pH 6.3 and pH 3.4 is used to assess the confidence levels for the accuracy of the structures obtained from modeling. The method also provides critical insight in differentiating regions of the structure that are well defined from those that are not. Use of the restraint analysis protocol is shown to be a powerful adjunct to currently used methods for the assignment of protein structures from NMR data.     

New joint prediction algorithm (Q7-JASEP) improves the prediction of protein secondary structure

The classical problem of secondary structure prediction is approached by a new joint algorithm (Q7-JASEP) that combines the best aspects of six different methods. The algorithm includes the statistical methods of Chou-Fasman, Nagano, and Burgess-Ponnuswamy-Scheraga, the homology method of Nishikawa, the information theory method of Garnier-Osgurthope-Robson, and the artificial neural network approach of Qian-Sejnowski. Steps in the algorithm are (i) optimizing each individual method with respect to its correlation coefficient (Q7) for assigning a structural type from the predictive score of the method, (ii) weighting each method, (iii) combining the scores from different methods, and (iv) comparing the scores for alpha-helix, beta-strand, and coil conformational states to assign the secondary structure at each residue position. The present application to 45 globular proteins demonstrates good predictive power in cross-validation testing (with average correlation coefficients per test protein of Q7, alpha = 0.41, Q7, beta = 0.47, Q7,c = 0.41 for alpha-helix, beta-strand, and coil conformations). By the criterion of correlation coefficient (Q7) for each type of secondary structure, Q7-JASEP performs better than any of the component methods. When all protein classes are included for training and testing (by cross-validation), the results here equal the best in the literature, by the Q7 criterion. More generally, the basic algorithm can be applied to any protein class and to any type of structure/sequence or function/sequence correlation for which multiple predictive methods exist.     

An automatic search for similar spatial arrangements of alpha-helices and beta-strands in globular proteins

A fast search algorithm to reveal similar polypeptide backbone structural motifs in proteins is proposed. It is based on the vector representation of a polypeptide chain fold in which the elements of regular secondary structures are approximated by linear segments (Abagyan and Maiorov, J. Biomol. Struct. Dyn. 5, 1267-1279 (1988)). The algorithm permits insertions and deletions in the polypeptide chain fragments to be compared. The fast search algorithm implemented in FASEAR program is used for collecting beta alpha beta supersecondary structure units in a number of alpha/beta proteins of Brookhaven Data Bank. Variation of geometrical parameters specifying backbone chain fold is estimated. It appears that the conformation of the majority of the fragments, although almost all of them are right-handed, is quite different from that of standard beta alpha beta units. Apart from searching for specific type of secondary structure motif, the algorithm allows automatically to identify new recurrent folding patterns in proteins. It may be of particular interest for the development of tertiary template approach for prediction of protein three-dimensional structure as well for constructing artificial polypeptides with goal-oriented conformation.     

Enhanced hybrid search algorithm for protein structure prediction using the 3D-HP lattice model

The problem of protein structure prediction in the hydrophobic-polar (HP) lattice model is the prediction of protein tertiary structure. This problem is usually referred to as the protein folding problem. This paper presents a method for the application of an enhanced hybrid search algorithm to the problem of protein folding prediction, using the three dimensional (3D) HP lattice model. The enhanced hybrid search algorithm is a combination of the particle swarm optimizer (PSO) and tabu search (TS) algorithms. Since the PSO algorithm entraps local minimum in later evolution extremely easily, we combined PSO with the TS algorithm, which has properties of global optimization. Since the technologies of crossover and mutation are applied many times to PSO and TS algorithms, so enhanced hybrid search algorithm is called the MCMPSO-TS (multiple crossover and mutation PSO-TS) algorithm. Experimental results show that the MCMPSO-TS algorithm can find the best solutions so far for the listed benchmarks, which will help comparison with any future paper approach. Moreover, real protein sequences and Fibonacci sequences are verified in the 3D HP lattice model for the first time. Compared with the previous evolutionary algorithms, the new hybrid search algorithm is novel, and can be used effectively to predict 3D protein folding structure. With continuous development and changes in amino acids sequences, the new algorithm will also make a contribution to the study of new protein sequences.     

Determination of three-dimensional protein structures from nuclear magnetic resonance data using fragments of known structures

A method to build a three-dimensional protein model from nuclear magnetic resonance (NMR) data using fragments from a data base of crystallographically determined protein structures is presented. The interproton distances derived from the nuclear Overhauser effect (NOE) data are compared to the precalculated distances in the known protein structures. An efficient search algorithm is used, which arranges the distances in matrices akin to a C alpha diagonal distance plot, and compares the NOE distance matrices for short sequential zones of the protein to the data base matrices. After cluster analysis of the fragments found in this way, the structure is built by aligning fragments in overlapping zones. The sequentially long-range NOEs cannot be used in the initial fragments search but are vital to discriminate between several possible combinations of different groups of fragments. The method has been tested on one simulated NOE data set derived from a crystal structure and one experimental NMR data set. The method produces models that have good local structure, but may contain larger global errors. These models can be used as the starting point for further refinement, e.g., by restrained molecular dynamics or interactive graphics.     

SANA: an algorithm for sequential and non-sequential protein structure alignment

Protein structure alignment algorithms play an important role in the studies of protein structure and function. In this paper, a novel approach for structure alignment is presented. Specifically, core regions in two protein structures are first aligned by identifying connected components in a network of neighboring geometrically compatible aligned fragment pairs. The initial alignments then are refined through a multi-objective optimization method. The algorithm can produce both sequential and non-sequential alignments. We show the superior performance of the proposed algorithm by the computational experiments on several benchmark datasets and the comparisons with the well-known structure alignment algorithms such as DALI, CE and MATT. The proposed method can obtain accurate and biologically significant alignment results for the case with occurrence of internal repeats or indels, identify the circular permutations, and reveal conserved functional sites. A ranking criterion of our algorithm for fold similarity is presented and found to be comparable or superior to the Z-score of CE in most cases from the numerical experiments. The software and supplementary data of computational results are available at .     

Protein structure prediction in a 210-type lattice model: parameter optimization in the genetic algorithm using orthogonal array

We have applied the orthogonal array method to optimize the parameters in the genetic algorithm of the protein folding problem. Our study employed a 210-type lattice model to describe proteins, where the orientation of a residue relative to its neighboring residue is described by two angles. The statistical analysis and graphic representation show that the two angles characterize protein conformations effectively. Our energy function includes a repulsive energy, an energy for the secondary structure preference, and a pairwise contact potential. We used orthogonal array to optimize the parameters of the population, mating factor, mutation factor, and selection factor in the genetic algorithm. By designing an orthogonal set of trials with representative combinations of these parameters, we efficiently determined the optimal set of parameters through a hierarchical search. The optimal parameters were obtained from the protein crambin and applied to the structure prediction of cytochrome B562. The results indicate that the genetic algorithm with the optimal parameters reduces the computing time to reach a converged energy compared to nonoptimal parameters. It also has less chance to be trapped in a local energy minimum, and predicts a protein structure which is closer to the experimental one. Our method may also be applicable to many other optimization problems in computational biology.     

Thermodynamic heuristics with case-based reasoning: combined insights for RNA pseudoknot secondary structure

The secondary structure of RNA pseudoknots has been extensively inferred and scrutinized by computational approaches. Experimental methods for determining RNA structure are time consuming and tedious; therefore, predictive computational approaches are required. Predicting the most accurate and energy-stable pseudoknot RNA secondary structure has been proven to be an NP-hard problem. In this paper, a new RNA folding approach, termed MSeeker, is presented; it includes KnotSeeker (a heuristic method) and Mfold (a thermodynamic algorithm). The global optimization of this thermodynamic heuristic approach was further enhanced by using a case-based reasoning technique as a local optimization method. MSeeker is a proposed algorithm for predicting RNA pseudoknot structure from individual sequences, especially long ones. This research demonstrates that MSeeker improves the sensitivity and specificity of existing RNA pseudoknot structure predictions. The performance and structural results from this proposed method were evaluated against seven other state-of-the-art pseudoknot prediction methods. The MSeeker method had better sensitivity than the DotKnot, FlexStem, HotKnots, pknotsRG, ILM, NUPACK and pknotsRE methods, with 79% of the predicted pseudoknot base-pairs being correct.     

Protein topology prediction through constraint-based search and the evaluation of topological folding rules.

An algorithm for predicting protein alpha/beta-sheet topologies from secondary structure and topological folding rules (constraints) has been developed and implemented in Prolog. This algorithm (CBS1) is based on constraint satisfaction and employs forward pruned breadth-first search and rotational invariance. CBS1 showed a 37-fold increase in efficiency over an exhaustive generate and test algorithm giving the same solution for a typical sheet of five strands whose topology was predicted from secondary structure with four topological folding constraints. Prolog specifications of a range of putative protein folding rules were then used to (i) replicate published protein topology predictions and (ii) validate these rules against known protein structures of nucleotide-binding domains. This demonstrated that (i) manual techniques for topology prediction can lead to non-exhaustive search and (ii) most of these protein folding principles were violated by specific proteins. Various extensions to the algorithm are discussed.     

MUSTA--a general, efficient, automated method for multiple structure alignment and detection of common motifs: application to proteins.

Here we present an algorithm designed to carry out multiple structure alignment and to detect recurring substructural motifs. So far we have implemented it for comparison of protein structures. However, this general method is applicable to comparisons of RNA structures and to detection of a pharmacophore in a series of drug molecules. Further, its sequence order independence permits its application to detection of motifs on protein surfaces, interfaces, and binding/active sites. While there are many methods designed to carry out pairwise structure comparisons, there are only a handful geared toward the multiple structure alignment task. Most of these tackle multiple structure comparison as a collection of pairwise structure comparison tasks. The multiple structural alignment algorithm presented here automatically finds the largest common substructure (core) of atoms that appears in all the molecules in the ensemble. The detection of the core and the structural alignment are done simultaneously. The algorithm begins by finding small substructures that are common to all the proteins in the ensemble. One of the molecules is considered the reference; the others are the source molecules. The small substructures are stored in special arrays termed combinatorial buckets, which define sets of multistructural alignments from the source molecules that coincide with the same small set of reference atoms (C(alpha)-atoms here). These substructures are initial small fragments that have congruent copies in each of the proteins. The substructures are extended, through the processing of the combinatorial buckets, by clustering the superpositions (transformations). The method is very efficient.     

Folding small proteins via annealing stochastic approximation Monte Carlo

Recently, the stochastic approximation Monte Carlo algorithm has been proposed by Liang et al. (2007) as a general-purpose stochastic optimization and simulation algorithm. An annealing version of this algorithm was developed for real small protein folding problems. The numerical results indicate that it outperforms simulated annealing and conventional Monte Carlo algorithms as a stochastic optimization algorithm. We also propose one method for the use of secondary structures in protein folding. The predicted protein structures are rather close to the true structures.     

The prediction of the structural class of protein: application of the measure of diversity.

Based on the concept that the structural class of a protein is mainly determined by its secondary structure sequence, a new algorithm for prediction of the structural class of a protein is proposed. By use of the number of alpha -helices, beta -strands, and betaalphabeta fragments, the structural class of a protein can be predicted by an algorithm based on the increment of diversity (ID), in which the sole prediction parameter-the increment of diversity is used as the index of prediction of structural class of a protein. The results indicate that the high rates of correct prediction are obtained for complete set (standard set) from Brookhaven Protein Data Bank-CD ROM (PDB) published in October 1995 and the test set newly released from Brookhaven Protein Data Bank-CD ROM (PDB) before July 1998, respectively.     

Reconstruction of protein conformations from estimated positions of the C alpha coordinates.

Protein C alpha coordinates are used to accurately reconstruct complete protein backbones and side-chain directions. This work employs potentials of mean force to align semirigid peptide groups around the axes that connect successive C alpha atoms. The algorithm works well for all residue types and secondary structure classes and is stable for imprecise C alpha coordinates. Tests on known protein structures show that root mean square errors in predicted main-chain and C beta coordinates are usually less than 0.3 A. These results are significantly more accurate than can be obtained from competing approaches, such as modeling of backbone conformations from structurally homologous fragments.