A genetic algorithm with backtracking for protein structure prediction

Abstract

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.