A Tabu Search Algorithm for the Protein Folding Problem

Protein folding problem is one of the central problems in the cross-discipline field involving biology, computational physics and computer science. In this paper, based on the heuristic physical model, a three-dimensional AB mode-based protein folding problem is converted from a nonlinear constraint-satisfied problem to an unconstrained optimization problem, which can be solved by the gradient method. However, in the course of solution using the gradient method, it is often possible for the calculation of gradient method to fall into the trap of local minimum. To jump out of the trap of local minimum and guide the search to the points with better prospects, we proposed a heuristic Tabu search method. The computational results show that our algorithm can outperform nPERM algorithm and HSA algorithm in terms of finding states with lower energy for the four benchmark sequences.