Predicting Protein Structure Using Parallel Genetic Algorithms

The protein folding problem is a biochemistry Grand Challenge problem. The challenge is to reliably predict natural three-dimensional structures of polypeptides. Genetic algorithms (GAs) are robust, semi-optimal search techniques modeling natural evolutionary processes. Fast messy GAs (fmGAs) are variants of messy GAs that reduce the exponential time complexity to polynomial. This investigation evaluates the merits of parallel SGAs and fmGAs for minimizing the potential energy of a pentapeptide, (Met)-enkephalin. AFIT\u27s energy model is compared to a similar model in a commercial package called QUANTA. Differences between the two models are identified and resolved to enhance GAs\u27 abilities to correctly fold molecules. The steps required to unify the behavior of the two implementations is presented. The effectiveness of SGAs while minimizing the potential energy of (Met)-enkephalin is shown to be highly dependent on the choice of population size and mutation rate. It is also demonstrated that choosing parameters from the Schaffer\u27s proposed guidelines cause SGAs to realize near-optimal performance on this particular application. Parallel SGAs are capable of finding near-optimal conformations of (Met)-enkephalin. Parallel fmGAS should ultimately find better solutions in less time. The experiments performed in this investigation determine limitations of parallel SGAs and fmGAs applied to polypeptide energy minimization