A genetic algorithm that seeks native states of peptides and proteins

MOLS sampling and its applications in structural biophysics

This review describes the MOLS method and its applications. This computational method has been developed in our laboratory primarily to explore the conformational space of small peptides and identify features of interest, particularly the minima, i.e., the low energy conformations. A systematic "brute-force" search through the vast conformational space for such features faces the insurmountable problem of combinatorial explosion, whilst other techniques, e.g., Monte Carlo searches, are somewhat limited in their region of exploration and may be considered inexhaustive. The MOLS method, on the other hand, uses a sampling technique commonly employed in experimental design theory to identify a small sample of the conformational space that nevertheless retains information about the entire space. The information is extracted using a technique that is a variant of the self-consistent mean field technique, which has been used to identify, for example, the optimal set of side-chain conformations in a protein. Applications of the MOLS method to understand peptide structure, predict the structures of loops in proteins, predict three-dimensional structures of small proteins, and arrive at the best conformation, orientation, and positions of a small molecule ligand in a protein receptor site have all yielded satisfactory results.

Exploring conformational space using a mean field technique with MOLS sampling

The computational identification of all the low energy structures of a peptide given only its sequence is not an easy task even for small peptides,due to the multiple-minima problem and combinatorial explosion. We have developed an algorithm, called the MOLS technique,that addresses this problem, and have applied it to a number of different aspects of the study of peptide and protein structure. Conformational studies of oligopeptides, including loop sequences in proteins have been carried out using this technique. In general the calculations identified all the folds determined by previous studies,and in addition picked up other energetically favorable structures. The method was also used to map the energy surface of the peptides. In another application, we have combined the MOLS technique, using it to generate a library of low energy structures of an oligopeptide, with a genetic algorithm to predict protein structures. The method has also been applied to explore the conformational space of loops in protein structures.Further, it has been applied to the problem of docking a ligand in its receptor site, with encouraging results.

Ab initio protein fold prediction using evolutionary algorithms: influence of design and control parameters on performance

True ab initio prediction of protein 3D structure requires only the protein primary structure, a physicochemical free energy model, and a search method for identifying the free energy global minimum. Various characteristics of evolutionary algorithms (EAs) mean they are in principle well suited to the latter. Studies to date have been less than encouraging, however. This is because of the limited consideration given to EA design and control parameter issues. A comprehensive study of these issues was, therefore, undertaken for ab initio protein fold prediction using a full atomistic protein model. The performance and optimal control parameter settings of twelve EA designs where first established using a 15-residue polyalanine molecule-design aspects varied include the encoding alphabet, crossover operator, and replacement strategy. It can be concluded that real encoding and multipoint crossover are superior, while both generational and steady-state replacement strategies have merits. The scaling between the optimal control parameter settings and polyalanine size was also identified for both generational and steady-state designs based on real encoding and multipoint crossover. Application of the steady-state design to met-enkephalin indicated that these scalings are potentially transferable to real proteins. Comparison of the performance of the steady state design for met-enkephalin with other ab initio methods indicates that EAs can be competitive provided the correct design and control parameter values are used.

Protein structure prediction using mutually orthogonal Latin squares and a genetic algorithm

We combine a new, extremely fast technique to generate a library of low energy structures of an oligopeptide (by using mutually orthogonal Latin squares to sample its conformational space) with a genetic algorithm to predict protein structures. The protein sequence is divided into oligopeptides, and a structure library is generated for each. These libraries are used in a newly defined mutation operator that, together with variation, crossover, and diversity operators, is used in a modified genetic algorithm to make the prediction. Application to five small proteins has yielded near native structures.

A genetic algorithm with conformational memories for structure prediction of polypeptides

We have developed an iterative hybrid algorithm (HA) to predict the 3D structure of peptides starting from their amino acid sequence. The HA is made of a modified genetic algorithm (GA) coupled to a local optimizer. Each HA iteration is carried out in two phases. In the first phase several GA runs are performed upon the entire peptide conformational space. In the second phase we used the manifestation of what we have called conformational memories, that arises at the end of the first phase, as a way of reducing the peptide conformational space in subsequent HA iterations. Use of conformational memories speeds up and refines the localization of the structure at the putative Global Energy Minimum (GEM) since conformational barriers are avoided. The algorithm has been used to predict successfully the putative GEM for Met- and Leu-enkephalin, and to obtain useful information regarding the 3D structure for the 8mer of polyglycine and the 16 residue (AAQAA)(3)Y peptide. The number of fitness function evaluations needed to locate the putative GEMs are fewer than those reported for other heuristic methods. This study opens the possibility of using Genetic Algorithms in high level predictions of secondary structure of polypeptides.

Ab initio protein structure prediction using physicochemical potentials and a simplified off-lattice model

This study describes a computational method for ab inito protein structure prediction. Protein conformation has been modeled by using six optimized backbone torsion angles and fixed side chains approximating rotationally averaged real side chains. The approximations aim to keep complexity of the structure description to a minimum without seriously compromising the accuracy of the structural representation. An evolutionary Monte Carlo algorithm has been developed to search through this restricted conformational space to locate low-energy protein structures. A simple physicochemical force field has been developed to assess the energies of different conformations within this structural description. The corresponding residue interaction energies are based on hydrophobic, hydrophilic, steric, and hydrogen-bonding potentials. The search procedure has been used to locate native energy minima from primary sequence alone. The 3-D structures of polypeptides up to 38 residues with both beta and alpha secondary structural elements have been accurately predicted. The search procedure has been found to be highly efficient and follows an energetically and structurally plausible pathway to locate native populations. The simple force field described in the study has been compared with a more complex all-atom model and been found to be similarly effective in predicting the structures of proposed independent folding units. Proteins 2001;43:186-202.

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.

Low-resolution structures of proteins in solution retrieved from X-ray scattering with a genetic algorithm

Small-angle x-ray solution scattering (SAXS) is analyzed with a new method to retrieve convergent model structures that fit the scattering profiles. An arbitrary hexagonal packing of several hundred beads containing the problem object is defined. Instead of attempting to compute the Debye formula for all of the possible mass distributions, a genetic algorithm is employed that efficiently searches the configurational space and evolves best-fit bead models. Models from different runs of the algorithm have similar or identical structures. The modeling resolution is increased by reducing the bead radius together with the search space in successive cycles of refinement. The method has been tested with protein SAXS (0.001 < S < 0.06 A(-1)) calculated from x-ray crystal structures, adding noise to the profiles. The models obtained closely approach the volumes and radii of gyration of the known structures, and faithfully reproduce the dimensions and shape of each of them. This includes finding the active site cavity of lysozyme, the bilobed structure of gamma-crystallin, two domains connected by a stalk in betab2-crystallin, and the horseshoe shape of pancreatic ribonuclease inhibitor. The low-resolution solution structure of lysozyme has been directly modeled from its experimental SAXS profile (0.003 < S < 0.03 A(-1)). The model describes lysozyme size and shape to the resolution of the measurement. The method may be applied to other proteins, to the analysis of domain movements, to the comparison of solution and crystal structures, as well as to large macromolecular assemblies.

Progress in protein structure prediction

If protein structure prediction methods are to make any impact on the impending onerous task of analyzing the large numbers of unknown protein sequences generated by the ongoing genome-sequencing projects, it is vital that they make the difficult transition from computational 'gedankenexperiments' to practical software tools. This has already happened in the field of comparative modelling and is currently happening in the threading field. Unfortunately, there is little evidence of this transition happening in the field of ab initio tertiary-structure prediction.

Empirical potentials and functions for protein folding and binding

Simplified models and empirical potentials are being increasingly used for the analysis of proteins, frequently augmenting or replacing molecular mechanics approaches. Recent folding simulations have employed potentials that, in addition to terms assuring proper polypeptide geometry, include only two noncovalent effects-hydrogen bonding and hydrophobicity, with extremely simple approximations to the latter. The potentials that have been used in the free-energy ranking of protein-ligand complexes have generally been more involved. These potentials have more detailed solvation models and account for both local (hydrophobic and polar) solute-solvent phenomena and long range electrostatic solvation effects. The models of solvation that have been used most frequently are surface area related atomic parameters, knowledge-based models extracted from protein-structure data, and continum electrostatics with an additional area-related parameter. The knowledge-based approaches to solvation, although convenient and accurate enough, are suspect of double counting certain free-energy terms.

Application of a genetic algorithm in the conformational analysis of methylene-acetal-linked thymine dimers in DNA: comparison with distance geometry calculations

The three-dimensional spatial structure of a methylene-acetal-linked thymine dimer present in a 10 basepair (bp) sense-antisense DNA duplex was studied with a genetic algorithm designed to interpret NOE distance restraints. Trial solutions were represented by torsion angles. This means that bond angles for the dimer trial structures are kept fixed during the genetic algorithm optimization. Bond angle values were extracted from a 10 bp sense-antisense duplex model that was subjected to energy minimization by means of a modified AMBER force field. A set of 63 proton-proton distance restraints defining the methylene-acetal-linked thymine dimer was available. The genetic algorithm minimizes the difference between distances in the trial structures and distance restraints. A large conformational search space could be covered in the genetic algorithm optimization by allowing a wide range of torsion angles. The genetic algorithm optimization in all cases led to one family of structures. This family of the methylene-acetal-linked thymine dimer in the duplex differs from the family that was suggested from distance geometry calculations. It is demonstrated that the bond angle geometry around the methylene-acetal linkage plays an important role in the optimization.

Evolutionary algorithms in computer-aided molecular design

In recent years, search and optimisation algorithms inspired by evolutionary processes have been applied with marked success to a wide variety of problems in diverse fields of study. In this review, we survey the growing application of these 'evolutionary algorithms' in one such area: computer-aided molecular design. In the course of the review, we seek to summarise the work to date and to indicate where evolutionary algorithms have met with success and where they have not fared so well. In addition to this, we also attempt to discern some future trends in both the basic research concerning these algorithms and their application to the elucidation, design and modelling of chemical and biochemical structures.