GA And ACO For Protein Structure Prediction Using The 2D HP Lattice Model

With the accomplished of human genome sequencing project, data about protein molecular sequence growth in geometric progression. We can predict the function of proteins after the research and analysis the protein folding structure according molecular sequence. The research about protein folding structure is of great significance for the development of bioinformatics and medical. Even it is a simplified model of protein folding, HP model is very important for our research. This paper use a variety of heuristic algorithms and HP model do in-depth research about protein folding structure. Given improved Genetic algorithm and ant colony algorithm, those algorithms can effectively obtain optimal solution for the HP model; and the efficiency is superior to the traditional algorithm.In this paper, we started from the traveling salesman problem, described the ant colony algorithm detailed, including development, content, methods, applications area and improve methods. For the ant colony algorithm itself, we also thorough studied and proposed approach for improvement.Through the research of PREM and HP model, we described the protein folding problem detailed. Then we introduced of a new mutation operator for mutation operation for Genetic algorithm, the introduction expanded the scope of the search, also prevent the search plunge into a local optimal solution, thus the algorithm can search to the global optimal solution. We choose some HP sequence for the experiment. And experiment proved that the improvement was resultful.In this paper, we detailed analyzed the protein folding problem using ant colony algorithm and HP lattice model. And we present a new method using ant colony algorithm to obtain the best result of protein folding problem. We introduced elimination and clone operation at the solution building phrase into the existing ant colony algorithm. The traditional operation will adopt roll back, and wasted a lot of time. The elimination and clone operation will reduce the computing time remarkable. In order to prevent the algorithm stop search and run to a local optimal solution and keep the wide search of ant, during the local search phases, we introduced long range move; selective local search; greedy ant colony strategy. And we introduced the Max– Min ant colony theory during the pheromone update phases. We choose some HP sequence for the experiment. The result proved the improvement of the ant colony algorithm solved the protein folding problem successful, better than GA. Not only guarantee the quality of result, further more, the algorithm has higher efficient.