基于蚁群算法的蛋白质折叠优化方法

摘要

本发明公开了一种基于蚁群算法的蛋白质折叠优化方法。运用亲疏水格点模型，首先将蚂蚁放置于左右两个起始方格中。然后让蚂蚁根据信息素和启发式信息将蛋白质中的氨基酸放置在网格中，蚂蚁每走一步执行一次局部信息素的更新，如果发生了停滞状况，则对相应的路径进行修补。最后，当所有蚂蚁都完成蛋白质折叠路径的构造后，执行全局信息素的更新。不断重复这些步骤以得到自由能最小的蛋白质结构。提出的方法与用于求解蛋白质折叠问题的已有算法相比，具有高效、快速等优点。

主权项

1、一种基于蚁群算法的蛋白质折叠优化方法，其特征在于，该方法包括以下步骤：(1)读入蛋白质序列并初始化各个参数。其中蛋白质序列以亲水性氨基酸(P)和疏水性氨基酸(H)的序列表示。(2)每一只蚂蚁都是在网格中央从蛋白质序列的中间开始构造路径的。对于带有n个氨基酸的蛋白质序列{s₀，s₁，...，s_n-1}(s_j∈{P，H}，j＝0，...，n-1)，每只蚂蚁都是从(n+2)×(n+2)大小的网格模板的中央的两个水平方格处开始路径的构造的。位于网格模板中央靠左的水平方格称为左起始方格，靠右的水平方格称为右起始方格。蚂蚁开始构造路径时，首先将氨基酸s_n/2放置在左起始方格中，氨基酸s_n/2+1放置在右起始方格中。蛋白质的子序列{s₀，...，s_n/2}从左起始方格开始构建，称为“左路径”，而另一个子序列{s_n/2+1，...，s_n-1}则从右起始方格开始构建，称为“右路径”。蚂蚁随机选择从蛋白质序列的左端或者右端开始走下一步。(3)所有蚂蚁开始根据蛋白质序列建立可行的折叠结构。如果蚂蚁当前处于方格i，下一个要放置的氨基酸为s_j，那么选择下一个方向d的概率如下其中，τ_id和η_jd分别为信息素和启发式信息的取值，β为启发式信息的加强参数。蚂蚁每移动一步都要执行局部信息素的更新，降低刚刚经过的两个相邻方格之间的信息素                       τ_id←δ·τ_id其中i是蚂蚁当前所在方格的序号，d是蚂蚁选择放置下一个氨基酸的方格所在的方向。δ＝(m-1)/m＜1称为局部蒸发率，m是蚂蚁的总数。设置信息素的最低取值为τ_min，当信息素低于这个值时将会重置。(4)统计每只蚂蚁构建出来的蛋白质在网格模板中形成的处于相邻方格但不在蛋白质序列相邻的H-H键数量，并选出本次迭代中的最优蚂蚁。(5)执行全局信息素的更新。首先蒸发所有相邻方格之间的信息素                       τ_id←ρ·τ_id其中，ρ是全局信息素蒸发率，i＝0，1，2，...，(n+2)²-1。然后，加强本次循环中找到的最好的折叠路径上的信息素${\tau }_{i^{\prime }d}\leftarrow {\tau }_{i^{\prime }d}+ϵ/(-E_{\min }^{*})$其中，i′∈{最优蚂蚁所经过的方格}，d为蚂蚁从方格i′移向下一个方格的方向，ε是在本次循环中最大的H-H键数量，$E_{\min }^{*}<0$是在HP格点模型中近似的最小自由能。(6)如果达到结束条件就终止整个算法，否则返回步骤(2)。