A. Katikireddy and C.M. Johnson (USA)
Genetic Algorithms, HP Model, Protein Structure Prediction.
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 “Grand Challenge Problems” 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 paper, we propose a simple genetic algorithm for finding the optimal conformation of a protein using the three-dimensional square HP model. 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.
Important Links:
Go Back
