【摘要】 本发明公开了一种基于蚁群算法的蛋白质折叠优化方法。运用亲疏水格点 模型，首先将蚂蚁放置于左右两个起始方格中。然后让蚂蚁根据信息素和启发 式信息将蛋白质中的氨基酸放置在网格中，蚂蚁每走一步执行一次局部信息素 的更新，如果发生了停滞状况，则对相应的路径进行修补。最后，当所有蚂蚁 都完成蛋白质折叠路径的构造后，执行全局信息素的更新。不断重复这些步骤 以得到自由能最小的蛋白质结构。提出的方法与用于求解蛋白质折叠问题的已 有算法相比，具有高效、快速等优点。。： 【专利类型】发明授权 【申请人】中山大学 【申请人类型】学校 【申请人地址】510275广东省广州市海珠区新港西路135号 【申请人地区】中国 【申请人城市】广州市 【申请人区县】海珠区 【申请号】CN200810026477.1 【申请日】2008-02-27 【申请年份】2008 【公开公告号】CN100590649C 【公开公告日】2010-02-17 【公开公告年份】2010 【授权公告号】CN100590649C 【授权公告日】2010-02-17 【授权公告年份】2010.0 【IPC分类号】G06N3/00 【发明人】张军; 胡晓敏; 黄韬 【主权项内容】1、一种基于蚁群算法的蛋白质折叠优化方法，其特征在于，该方法包括以下步骤： (1)读入蛋白质序列并初始化各个参数；其中蛋白质序列以亲水性氨基酸P和疏水性氨基酸H的序列表示； (2)每一只蚂蚁都是在网格中央从蛋白质序列的中间开始构造路径的；对于带有n个氨基酸的蛋白质序列{s0，s1，...，sn-1}，sj∈{P，H}，j＝0，...，n-1，每只蚂蚁都是从(n+2)×(n+2)大小的网格模板的中央的两个水平方格处开始路径的构造的；模板中的方格从左上到右下依次编号为0到(n+2)2-1；于是，左右两个起始方格的编号分别为 和 位于网格模板中央靠左的水平方格称为左起始方格，靠右的水平方格称为右起始方格；蚂蚁开始构造路径时，首先将氨基酸 放置在左起始方格中，氨基酸 放置在右起始方格中；蛋白质的子序列 从左起始方格开始构建，称为“左路径”，而另一个子序列 则从右起始方格开始构建，称为“右路径”；蚂蚁随机选择从子序列 或 开始构造，每走一步就将下一个未放置的氨基酸放置在相应的方格内； (3)所有蚂蚁开始根据蛋白质序列建立可行的折叠结构；如果蚂蚁当前处于方格i，下一个要放置的氨基酸为sj，那么选择下一个方向d的概率如下 其中，λid和ηjd分别为信息素和启发式信息的取值，β为启发式信息的加强参数；在算法中，信息素是放置在连接相邻两个方格的虚边上的；在一个方格中，这样的虚边实质上就是指向与其相邻的方格的四个方向，分为上(U)、下(D)、左(L)和右(R)；蚂蚁每移动一步都要执行局部信息素的更新，降低刚刚经过的两个相邻方格之间的信息素 τid←δ·τid 其中i是蚂蚁当前所在方格的序号，d是蚂蚁选择放置下一个氨基酸的方格所在的方向；δ＝(m-1)/m＜1称为局部蒸发率，m是蚂蚁的总数；设置信息素的最 低取值为τmin，当信息素低于这个值时将会重置；在启发式信息方面，算法中的疏水性和亲水性两种氨基酸的启发式信息是不同的；疏水性的氨基酸的启发式信息定义为 ηjd＝hjd+1 其中，hjd是把氨基酸sj放置在相邻的方格中将会新产生的H-H键的数量，d代表蚂蚁移动的方向；亲水性的氨基酸的启发式信息为，下一个可能被选择的方格周围的空格和亲水性氨基酸的总和加一，也就是 ηjd＝vjd+h′jd+1 其中，vjd和h′jd分别为sj下一个可能位置周围的空格和亲水性氨基酸的数量； (4)统计每只蚂蚁构建出来的H-H键数量，所述H-H键表示两个蛋白质序列中非相连而在格点中邻接的疏水性氨基酸的邻接方式，并选出本次迭代中的最优蚂蚁； (5)执行全局信息素的更新；首先蒸发所有相邻方格之间的信息素 τid←ρ·τid 其中，ρ是全局信息素蒸发率，i＝0，1，2，...，(n+2)2-1；然后，加强本次循环中找到的最好的折叠路径上的信息素 其中，i′∈{最优蚂蚁所经过的方格}，d为蚂蚁从方格i′移向下一个方格的方向，ε是在本次循环中最大的H-H键数量， 是在HP格点模型中近似的最小自由能； (6)如果达到结束条件就终止整个算法，否则返回步骤(2)。 【当前权利人】中山大学 【当前专利权人地址】广东省广州市海珠区新港西路135号 【统一社会信用代码】121000004558631445 【引证次数】3.0 【被引证次数】3 【他引次数】3.0 【被他引次数】3.0 【家族引证次数】3.0 【家族被引证次数】12
