Protein Structure Prediction (PSP) aims at determining the three-dimensional shape of a protein molecule from its amino acid sequence. This problem is known to be NP-Complete and has been declared one of the \223Grand Challenge Problems\224 of biochemistry. A simple and widely studied abstraction used in PSP is the hydrophobic-hydrophilic (HP) model in which the protein conformation is restricted to self-avoiding paths when embedded onto a lattice. In this thesis, a simple genetic algorithm for finding the optimal conformation of a protein using the three-dimensional square HP model is explored. A backtracking procedure is used to resolve the positional collisions and illegal conformations that occur during the course of genetic search. Backtracking is shown to be a simple and efficient means of collision repair that requires little overhead. Empirical results show that a genetic algorithm using backtracking can obtain the lowest energy structure of an amino acid sequence in fewer energy evaluations than earlier approaches.

Pizza and soda will be served for those attending!