Accession Number : ADA320695

Title :   Refined Genetic Algorithms for Polypeptide Structure Prediction.

Descriptive Note : Master's thesis,

Corporate Author : AIR FORCE INST OF TECH WRIGHT-PATTERSON AFB OH

Personal Author(s) : Kaiser, Charles E., Jr

PDF Url : ADA320695

Report Date : DEC 1996

Pagination or Media Count : 125

Abstract : Accurate and reliable prediction of macromolecular structures has eluded researchers for nearly 40 years. Prediction via energy minimization assumes the native conformation has the globally minimal energy potential. An exhaustive search is impossible since for molecules of normal size, the size of the search space exceeds the size of the universe. Domain knowledge sources, such as the Brookhaven PDB can be mined for constraints to limit the search space. Genetic algorithms (GAs) are stochastic, population based, search algorithms of polynomial (P) time complexity that can produce semi-optimal solutions for problems of nondeterministic polynomial (NP) time complexity such as PSP. Three three refined GAs are presented: A farming model parallel hybrid GA (PHGA) preserves the effectiveness of the serial algorithm with substantial speed up. Portability across distributed and MPP platforms is accomplished with the Message Passing Interface (MPI) communications standard. A Real-valved GA system, real-valued Genetic Algorithm, Limited by constraints (REGAL), exploiting domain knowledge. Experiments with the pentapeptide Met-enkephalin have identified conformers with lower energies (CHARMM) than the accepted optimal conformer (Scheraga, et al), -31.98 vs -28.96 kcals/mol. Analysis of exogenous parameters yields additional insight into performance. A parallel version (Para-REGAL), an island model modified to allow different active constraints in the distributed subpopulations and novel concepts of Probability of Migration and Probability of Complete Migration.

Descriptors :   *ALGORITHMS, *OPTIMIZATION, *MOLECULAR STRUCTURE, MATHEMATICAL MODELS, STOCHASTIC PROCESSES, DATA MANAGEMENT, DISTRIBUTED DATA PROCESSING, COMPUTER COMMUNICATIONS, PEPTIDES, PROTEINS, ANALYSIS OF VARIANCE, THESES, PARALLEL PROCESSING, POLYNOMIALS, HEURISTIC METHODS, COMPUTER APPLICATIONS, MACROMOLECULES, MONOMERS, SYSTEMS ANALYSIS, MOLECULAR ENERGY LEVELS.

Subject Categories : Computer Programming and Software
      Biochemistry

Distribution Statement : APPROVED FOR PUBLIC RELEASE