Study Of Multi-agent Simulated Annealing Algorithm For Protein Structure Prediction

Protein engineering is one of the important issues on the post-genomic era, andalso is the frontier of the development of modern biotechnology. Solving the proteinstructure prediction problem is not only one of the most basic goal of proteinengineering, but also is a necessary means of protein design assumptions, furthermoreis one of the very challenging topic in the field of bioinformatics. The ab initioprediction method of protein structure prediction with thermodynamic hypothesis "thenatural conformation of protein is the conformation with the lowest free energy " asthe theoretical basis, by calculating the lowest free energy value in protein we canpredict the protein structure. Therefore, we can attribute using ab initio predictionmethod for protein structure prediction to a global optimization problem for themodel.According to the concept of protein structure prediction and the theoretical basisof protein structure prediction, we have introduced one of the most simplifiedcontinuous polymer model for protein structure prediction-AB Off-Lattice Model, theprotein structure prediction problem is transformed into a mathematical continuousfunction on a global optimization problems. This model is closer to the real structureof proteins,and is more important to predict the real structure of proteins in practicalsignificance for our research. The protein folding problem based on the AB off-latticemodel is a typical NP-hard problem in computational biology, so looking for aneffective global optimization algorithm is the key to solving this problem.The simulated annealing algorithm (SA) and particle swarm optimizationalgorithm (PSO) are both classical intelligent optimization algorithms, each algorithmhas its strengths and weaknesses. PSO algorithm has good intensification ability, but itis easy to be trapped into local optima. On the contrary, SA algorithm has good abilityto escape from local optima, but it is extremely slow in terms of convergence. In orderto take the advantages of the learning ability of PSO algorithm and the hill-climbingability of SA algorithm, we propose a multi-agent simulated annealing algorithm(MSA In MSA, movement equation of PSO algorithm is used to produce candidate solution by SA algorithm. This strategy can balance the intensification ability anddiversification ability of MSA algorithm more efficiently. We implemented the MSAalgorithm and tested its performance on four benchmark functions. Simulation resultsshow that MSA algorithm can effectively improve the iterative efficiency andcomputing performance.The proposed MSA algorithm was applied to predicting protein structure intwo-dimensional AB off-lattice model., Simulation experiments were carried on anumber of short artificial protein sequences (short Fibonacci test sequence), four longartificial protein sequences (long Fibonacci test sequence), simulation results showthat the multi-agent simulated annealing algorithm (MSA) have favorableperformance for the protein folding problem, and can get the lowest free energyconformation to protein folding well. Then we predicted the lowest free energyconformation of four short real protein sequences and two long real protein sequences,and compared with simulated results of a variety of other algorithms in the literature,the results show that multi-agent simulated annealing algorithm (MSA) has reallyimproved the performance of protein structure prediction problem, and can formsignificant hydrophobic core of the protein structure, and also can show that to someextent it can reflect out the natural characteristics of the real proteins which said"hydrophilic amino acid residues are always around with hydrophobic amino acidresidues, and in the formation of clusters".