The Research Of Threshold Accepting Algorithm On Protein Structure Prediction

Due to its high computational complexity, Protein Structure Prediction (PSP) has been considered as an extremely challenging task in bioinformatics. Ab initio prediction method is a kind of common theory-based PSP methods. In this paper, Ab initio prediction of 2D protein structure of non-lattice AB model was studied. In Ab initio methods, based on the assumption that protein conformation is most stable when free energy is lowest, PSP problem is transferred into function optimization problem.Threshold accepting (TA) algorithm is an improved simulated annealing (SA) algorithm, which is mainly used in combinatorial optimization problems. In this paper, we study TA for continuous space optimization problems, and we use it to 2-Dimensional PSP of the AB model. The main study of this paper includes following two aspects:TA based on the ADaptive neighborhood (AD) is proposed, which uses AD to generate candidate solutions. AD is characterized by nearly covering the entire space in the initial stage of the algorithm, the latter in a local area, which can balance the exploration of solution space and mining of key area. Single agent TA algorithms by taking advantage of the self-adaptive ability from AD are analyzed and demonstrated on 12 benchmarks and protein sequences. The numerical results show that the AD can significantly improve the performance of TA. Further experiments with expanding search areas are made, the results show that even larger the variable fields 1000 times, the results remained good. Theoretical analysis and experiments show that adaptive neighborhood based sampling has good performance.Additionally, Multi-agent TA (MTA) based on Particle Swarm Optimization (PSO) algorithm, which uses the velocity and position update formulas of PSO algorithm to generate candidate solutions, is proposed. Each agent can memorize the best position it ever visited, enabling the algorithm to search in the optimized areas. Simulated experiments are performed on 12 benchmarks and protein sequences. Experiments show that PSO-based sampling performs better than AD-based sampling on benchmark functions. When simulation is performed on four long Fibonacci sequences, four short and three long real protein sequences, MTA with AD-based sampling outperforms than, or at least comparable to MTA with different sampling schemes or several state-of-the-art algorithms for PSP.