关键词: 强化学习, HP模型, 结构预测

Abstract: Protein structure prediction is an important factor in the area of bioinformatics. Predicting the two-dimensional structure of proteins based on the Hydrophobic Polarity model（HP model） is a typical Non-deterministic Polynomial（NP）-hard problem. Currently, HP model optimization methods include the greedy algorithm, particle swarm optimization, genetic algorithm, ant colony algorithm and the Monte-Carlo simulation method. However, the robustness of these methods are not sufficient, and it is easy to fall into a local optimum. Therefore, a HP model optimization method, based on reinforcement learning is proposed. In the full state space, a reward function based on energy function is designed and a rigid overlap detection rule is introduced. By using the characteristics of the continuous Markov optimal decision and maximizing global cumulative return, the global evolutionary relationship in biological sequences is fully exploited, and effective and stable predictions are retrieved. Eight classical sequences from publications and Uniref50 are selected as experimental objects. The robustness, convergence and running time are compared with the greedy algorithm and particle swarm optimization algorithm, respectively. Both reinforcement method and swarm optimization method can find all the lowest energy structures for these eight sequences, while the greedy algorithm only detects 62.5%. Compared with particle swarm optimization, the running time of the reinforcement method is 63.9% lower than that of particle swarm optimization.

Key words: reinforcement learning, Hydrophobic Polarity（HP） model, structure prediction