Research on HP Model Optimization Method Based on Reinforcement Learning

doi:10.3778/j.issn.1002-8331.1811-0059

Abstract

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

摘要： 蛋白质结构预测问题一直是生物信息学中的重要问题。基于疏水极性模型的蛋白质二维结构预测问题是一个典型的NP难问题。目前疏水极性模型优化的方法有贪心算法、粒子群算法、遗传算法、蚁群算法和蒙特卡罗模拟方法等，但这些方法成功收敛的鲁棒性不高，容易陷入局部最优。由此提出一种基于强化学习的HP模型优化方法，利用其连续马尔可夫最优决策与最大化全局累计回报的特点，在全状态空间中，构建基于能量函数的奖赏函数，引入刚性重叠检测规则，充分挖掘生物序列中的全局进化关系，从而进行有效与稳定的预测。以3条经典论文序列和5条Uniref50序列为实验对象，与贪心算法和粒子群算法分别进行了鲁棒性、收敛性与运行时间的比较。贪心算法只能在62.5%的序列上进行收敛，该文方法能在5万次训练后稳定的在所有序列上达到了收敛。与粒子群算法相比，两者都能找到最低能量结构，但该文的运行时间较粒子群算法降低了63.9%。

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

WU Hongjie1，2, YANG Ru1, FU Qiming1, CHEN Jianping1, LU Weizhong1. Research on HP Model Optimization Method Based on Reinforcement Learning[J]. Computer Engineering and Applications, 2019, 55(12): 132-139.

吴宏杰1，2，杨茹1，傅启明1，陈建平1，陆卫忠1. 基于强化学习的HP模型优化方法研究[J]. 计算机工程与应用, 2019, 55(12): 132-139.

[1]	WANG Xiao, TANG Lun, HE Xiaoyu, CHEN Qianbin. Multi-dimensional Resource Optimization of Service Function Chain Based on Deep Reinforcement Learning [J]. Computer Engineering and Applications, 2021, 57(4): 68-76.
[2]	LAI Jun, WEI Jingyi, CHEN Xiliang. Overview of Hierarchical Reinforcement Learning [J]. Computer Engineering and Applications, 2021, 57(3): 72-79.
[3]	MA Zhihao, ZHU Xiangbin. Research on Quasi-hyperbolic Momentum Gradient for Adversarial Deep Reinforcement Learning [J]. Computer Engineering and Applications, 2021, 57(24): 90-99.
[4]	LI Baoshuai, YE Chunming. Job Shop Scheduling Problem Based on Deep Reinforcement Learning [J]. Computer Engineering and Applications, 2021, 57(23): 248-254.
[5]	WANG Jun, CAO Lei, CHEN Xiliang, LAI Jun, ZHANG Legui. Overview on Reinforcement Learning of Multi-agent Game [J]. Computer Engineering and Applications, 2021, 57(21): 1-13.
[6]	CHENG Yi, HAO Mimi. Path Planning for Indoor Mobile Robot with Improved Deep Reinforcement Learning [J]. Computer Engineering and Applications, 2021, 57(21): 256-262.
[7]	KUANG Liqun, LI Siyuan, FENG Li, HAN Xie, XU Qingyu. Application of Deep Reinforcement Learning Algorithm on Intelligent Military Decision System [J]. Computer Engineering and Applications, 2021, 57(20): 271-278.
[8]	KONG Songtao, LIU Chichi, SHI Yong, XIE Yi, WANG Kun. Review of Application Prospect of Deep Reinforcement Learning in Intelligent Manufacturing [J]. Computer Engineering and Applications, 2021, 57(2): 49-59.
[9]	LI Hao, NING Haoyu, KANG Yan, LIANG Wentao, HUO Wen. SMRFGAN Model for Text Emotion Transfer [J]. Computer Engineering and Applications, 2021, 57(2): 170-176.
[10]	ZHANG Rongxia, WU Changxu, SUN Tongchao, ZHAO Zengshun. Progress on Deep Reinforcement Learning in Path Planning [J]. Computer Engineering and Applications, 2021, 57(19): 44-56.
[11]	YANG Xueyu, CHEN Jianping, FU Qiming, LU You, WU Hongjie. Deep Deterministic Policy Gradient Algorithm Based on Stochastic Variance Reduction Method [J]. Computer Engineering and Applications, 2021, 57(19): 104-111.
[12]	SONG Haonan, ZHAO Gang, WANG Xingfen. Knowledge Reasoning Method Combining Knowledge Representation with Deep Reinforcement Learning [J]. Computer Engineering and Applications, 2021, 57(19): 189-197.
[13]	WANG Keyin, SHI Zhen, YANG Zhengcai, YANG Yahui, WANG Sishan. Path Planning for Mobile Robot Using Improved Reinforcement Learning Algorithm [J]. Computer Engineering and Applications, 2021, 57(18): 270-274.
[14]	ZHANG Jun, ZHU Qingwei, YAN Junjie, WEN Bo. UAV Indoor 3D Track Planning Based on Improved Reinforcement Learning Algorithm [J]. Computer Engineering and Applications, 2021, 57(16): 175-181.
[15]	CHE Xiangbei, KANG Wenqian, OUYANG Yuhong, YANG Kehan, LI Jian. SDN Routing Optimization Algorithm Based on Reinforcement Learning [J]. Computer Engineering and Applications, 2021, 57(12): 93-98.

Research on HP Model Optimization Method Based on Reinforcement Learning

基于强化学习的HP模型优化方法研究

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics