刘　羽　熊壬浩

1(桂林理工大学机械与控制工程学院　广西 桂林 541004)

2(桂林理工大学信息科学与工程学院　广西 桂林 541004)



带有停滞检测的蚁群算法在2D HP格点模型中的应用

刘羽1熊壬浩2

1(桂林理工大学机械与控制工程学院广西 桂林 541004)

2(桂林理工大学信息科学与工程学院广西 桂林 541004)

摘要为了提高蛋白质折叠结构预测的求解效率，针对2D HP格点模型，研究蚁群ACO(Ant Colony Optimization)算法在该问题上的应用。采用四元组表示绝对的折叠方向，并建立构象和解的一一对应关系。通过实验对算法各阶段的常用策略、方法进行比较分析。为了防止搜索陷入停滞，引入位置信息素停滞比和序列信息素停滞比两个参数，使用一种新的停滞检测机制。实验结果表明，改进的算法在保证预测质量的前提下，显著地提升了收敛速度。

关键词HP模型蛋白质折叠蚁群算法停滞检测遗传算法

APPLICATION OF ANT COLONY OPTIMISATION ALGORITHM WITH STAGNATION DETECTION IN 2D HP LATTICE MODEL

Liu Yu1Xiong Renhao2

1(School of Mechanical and Control Engineering,Guilin University of Technology,Guilin 541004,Guangxi,China)2(School of Information Science and Engineering,Guilin University of Technology,Guilin 541004,Guangxi,China)

AbstractAiming at 2D HP lattice model we studied the application of ant colony optimisation algorithm on protein folding structure prediction in order to improve the efficiency of its solution. We used the quadruple to express absolute folding direction, and established the one-to-one correspondence between conformation and solution. Through experiment we made the comparative analyses on common strategies and methods in each stage of the algorithm. To prevent the search from going to stagnation, we introduced two parameters, the position pheromone stagnation ratio and the sequence pheromone stagnation ratio, and applied a new stagnation detection mechanism as well. Experimental results showed that the improved algorithm remarkably accelerated the convergence speed on the premise of ensuring prediction quality.

KeywordsHP modelProtein foldingAnt colony optimisationStagnation detectionGenetic algorithm

0引言

蛋白质是一种复杂的有机化合物，是由氨基酸经脱水缩合反应形成多肽链，然后在空间进行折叠后形成的。蛋白质是细胞的基本构成物质，是生命的物质基础，在生物细胞中起着关键的生物和化学作用。蛋白质折叠问题的研究在医学及生物工程等领域具有重大的科学价值和实用价值，其规律尚未被完全揭示。目前蛋白质折叠结构研究的主要方法包括实验方法以及理论预测两类。X射线晶体学方法等生物化学实验方法对样本的要求高、耗资大、周期长，人们逐渐将注意力转移到理论预测方法上来。……