基于P2HP平台的蛋白质折叠分布式计算

第３４卷　

ＶｏＬ３４　第９期　

Ｎｏ．９　计算机工程　

Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　２００８年５月　

Ｍａｙ　２００８　

・软件技术与数据库・　文章编号：１００　＿３４２８（２００８）０　－－０１０　－－０３　文献标识码：Ａ　中图分类号：ＴＰ３１１　

基于Ｐ２ＨＰ平台的蛋白质折叠分布式计算　

刘宇　，吕志鹏２，罗飞　

（１．武汉科技大学计算机学院，武汉４３００８１；２．华中科技大学计算机学院，武汉４３００７４）　

摘要：通过对基于格点模型的ＰＥＲＭ算法进行定性分析，提出并行化计算ＰＥＲＭ算法的策略。该策略保存了ＰＥＲＭ算法中最关键的平　均权重向量，并分发至多个计算单元进行模拟运算，从而达到减少计算时间、提高运算结果精确度的目的　以Ｐ２ＨＰ为计算平台，对多条　

蛋自质序列进行模拟运算。实验结果表明，基于ＰＥＲＭ的蛋白质折叠并行计算方法能够在Ｐ２ＨＰ平台上获得较优的性能。　

关键诃：蛋白质折叠；分布式计算；对等网络　

Ｄｉｓｔｒｉｂｕｔｅｄ　Ｃｏｍｐｕｔｉｎｇ　ｏｆ　Ｐｒｏｔｅｉｎ　Ｆｏｌｄｉｎｇ　Ｂａｓｅｄ　ｏｎ　Ｐ２ＨＰ　

ＬＩＵ　Ｙｕ　，ＬＶ　Ｚｈｉ．ｐｅｎｇ２，ＬＵＯ　Ｆｅｉ　

（１．Ｄｅｐａｒｔｍｅｎｔ　ｏｆＣｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ，ＷｕｈａｎＵｎｉｖｅｒｓｉｔｙ　ｏｆＳｃｉｅｎｃｅ　ａｎｄＴｅｃｈｎｏｌｏｇｙ，Ｗｕｈａｎ４３００８１；　

２．Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ．Ｈｕａｚｈｏｎｇ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｗｕｈａｎ　４３００７４）　

ＩＡｂｓｔｒａｃｔ］Ｂｙ　ａｎａｌｙｚｉｎｇ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｏｆ　ＰＥＲＭ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｌａｔｔｉｃｅ　ｍｏｄｅｌ，ａ　ｓｔｒａｔｅｇｙ　ｏｆ　ｈｏｗ　ｔＯ　ｐａｒａｌｌｅｌｉｚｅ　ＰＥＲＭ　ｉｓ　ｉｎｔｒｏｄｕｃｅｄ：Ｔｈｅ　ｓｔｒａｔｅｇｙ　ｓｔｏｒｅｓ　ｔｈｅ　ａｖｅｒａｇｅ　ｗｅｉｇｈｔ　ｖｅｃｔｏｒ，ｔｈｅ　ｍｏｓｔ　ｉｍｐｏｒｔａｎｔ　ｐａｒｔ　ｉｎ　ＰＥＲＭ．ａｓ　ｔｈｅ　ｍｉｄｄｌｅ　ｉｎｆｏｒｍ撕ｏｎ　ａｎｄ　ｄｉｓｔｒｉｂｕｔｅｓ　ｔｈｉｓ　ｉｎｆｏｒｍａｔｉｏｎ　ｔＯ　ｓｅｖｅｒａｌ　ｃｏｍｐｕｔｉｎｇ　

ｃｅｌｌｓ　ｆｏｒ　ｓｏｍｅ　Ｓｉｍｕｌａｔｉｏｎ　ｃｏｍｐｕｔｉｎｇ．Ｓｏ　ｉｔ　Ｃａｎ　ｉｍｐｒｏｖｅ　ｔｈｅ　ｓｐｅｅｄ　ｏｆ　ｃｏｍｐｕｔｉｎｇ　ａｎｄ　ａｃｈｉｅｖｅ　ｔｈｅ　ｍｏｒｅ　ａｃｃｕｒａｔｅ　ｒｅｓｕｌｔｓ．Ｐ２Ｐ—ｂａｓｅｄ　Ｈｉｇｈ　Ｐｅｒｆｏｒｍａｎｃｅ　

Ｃｏｍｐｕｔｉｎｇ　Ｐｌａｔｆｏｒｍ（Ｐ２ＨＰ）ｉｓ　ｅｍｐｌｏｙｅｄ　ａｓ　ｔｈｅ　ｅｘｐｅｒｉｍｅｎｔａｌ　ｅｎｖｉｒｏｎｍｅｎｔ．Ｓｏｍｅ　ｄｉｆｅｒｅｎｔ　ｐｒｏｔｅｉｎ　ｓｅｑｕｅｎｃｅｓ　ａｒｅ　ｃｏｍｐｕｔｅｄ．Ｔｈｅ　ｒｅｓｕｌｔｓ　ｏｆ　ｅｘｐｅｒｉｍｅｎｔ　ｓｈｏｗ　ｔｈｅ　ｐａｒａｌｌｅｌ　ｃｏｍｐｕｔｉｎｇ　ｍｅｔｈｏｄ　ｂａｓｅｄ　ｏｎ　ＰＥＲＭ　Ｃａｎ　ａｃｈｉｅｖｅ　ｔｈｅ　ｂｅ￣ｅｒ　ｐｅｒｆｏｒｍａｎｃｅ　ｏｎ　Ｐ２ＨＥ　

ＩＫｅｙ　ｗｏｒｄｓ］ｐｒｏｔｅｉｎ　ｆｏｌｄｉｎｇ；ｄｉｓｔｒｉｂｕｔｅｄ　ｃｏｍｐｕｔｉｎｇ；Ｐ２Ｐ　ｎｅｔｗｏｒｋ　

１概述　

格点模型是一种分析和计算均较简单的模型。该模型考　

虑了在蛋白质结构的形成过程中，亲水性（Ｐｏｌａｒ，用Ｐ表示）　

和疏水性（Ｈｙｄｒｏｐｈｏｂｉｃ，用Ｈ表示）起的至关重要的作用，将　

蛋白质序列表示为由Ｈ，Ｐ组成的字符串。将此类序列无重叠　

地放置到三维单位正方体网格格点空间上，且定义在序列中　不相邻但在空间上相邻的２个Ｈ元素之间的能量为一１，其他　

情况为０。按照此思路，对蛋白质折叠问题的求解就可转换　

为搜寻蛋白质序列的最低能量空间结构。　

能量公式如式（１）所示。尽管格点模型已在很大程度上减　少了折叠问题所需要考虑的因素，但对相应问题的求解依然　

是ＮＰ难度的。　

…　ｉ一１若ｉ，　为日且空间距离为１　Ｅ　

，知勺　其中　ｊ０否则　（１）　

ｚ＜　＿Ｊ　人们已经提出了多种基于格点模型的算法，比如：　ＰＥＲＭ［　，基因算法　】，群蚁算法ｔ３　等。其中，ＰＥＲＭ算法是　

目前研究得最多、获得效果最好的算法之一，但是同样存在　

计算时间较长、所需计算资源较多的问题。针对该问题，本　

文在ＰＥＲＭ算法的基础上提出了并行化该算法的解决方案，　并在Ｐ２ＨＰ（４］高性能计算平台上进行了实现。　

２　ＰＥＲＭ算法及其并行化　

２．１定义　定义１格局：对于长度为Ｎ的蛋白质序列，已放入格点　

空间的前，ｚ（２≤，ｚ≤．Ⅳ）个球所形成的结构称为格局。　定义２自由度：在已放入ｎ一１个球的格局中，第ｎ个球的　

放入称为一个动作，并称合法动作的数目为第ｎ个球的自由　度，记为　。　

定义３格局的权重：对于已放入ｎ个球的格局而言，所形　

成空间结构的优劣程度称为该格局的权重，记作　，具体定　

义如下：　

ｆ　：　：１　ｊ　（２）　【　＝　ｌｅ　舶ｅ　其中，△　为第ｎ个球放入后新增的能量值；Ｔ为温度常数，　

取值范围为Ｔ∈【０．２５，０，３５］。　

２．２　ＰＥＲＭ算法　ＰＥＲＭ是一种增长型算法，其主要思想如下：将蛋白质　序列按照编号顺序，由小到大依次将各个元素放入空间结构，　

直至序列上的所有元素被放入为止。在放入元素的过程中，　

除了要保证序列在空间上的无重叠性，还要遵循一定的策略。　

虽然人们已提出了多种策略，但是基本的思想并没有改变，　

具体步骤如下：　（１）计算放置第ｎ个球的各合法动作ａ的优劣程度。　

（２）计算格局权重预测值Ⅵ　及门限值Ⅵ　，Ⅵ　。　

（３）ＮＷ　与　，　进行比较，选择动作：　

１）若Ⅵ　∈『Ⅵ　，Ⅵ　］，则依概率随机地选一合法动作　

来做，然后计算权重　．，进入新格局。　

２）若　＜Ⅵ　，则以ｌ／２￣Ｊ概率停止生长，另以１／２概率存　

作者筒介：刘宇（１９８０－－），男，助教、硕士，主研方向：分布式计　算；吕志鹏，博士；罗飞，博士研究生　收稿日期：２００７—０９—１２　Ｅ－ｍａｌｌ：ｍｉｎｄ＿ｒｅｖｏｌｕｔｉｏｎ＠１２６．ｃ

ｏｍ　维普资讯 http://www.cqvip.com 活并依概率随机地选一动作ａ来做，权重加倍，进入新格局。　

３）若　＞　，则选择由ｋ个不同的动作构成的动作集　

Ａ＝｛　…，　１做各动作，分别计算权重并进入新格局。　

在部分链上递归地执行这些步骤，直到完成一轮对蛋自　

质分子结构的搜索。在ＰＥＲＭ算法中，计算上、下门限值需　

要用到ｚ　和　向量。其中，ｚ　为此前出现过的所有长度　

为ｎ的部分链构象的权重的算术平均值，ｃ　为此前出现过的　

所有长度为ｎ的部分链构形的个数。在ＰＥＲＭ算法运行之初，　

设定ｗ　和ｗｃ分别为枷和０，生成一合法空间结构，得到　

ｚ　和ｃ　的初始值。随后，利用ｚ　和　的初始值执行上述　

递归步骤，同时实时更新ｚ　和　向量，直到所有的结构要　

么被遗弃，要么生长成完整的蛋自质分子并在格点空间中形　

成结构。此时，能量最低的结构便是算法所要搜索的蛋自质　

分子空间结构。　

２．３　ＰＥＲＭ算法的并行计算策略　根据以上介绍可知，ｚ　和Ｃｎ对于ＰＥＲＭ算法而言是非　常重要的。ＰＥＲＭ算法利用Ｚｎ和Ｃｎ向量制定剪枝和繁殖的　

标准，并综合考虑当前的局部结构决定如何进行下一步的处　

理。随着ＰＥＲＭ算法的运行，Ｚｎ和Ｃｎ向量将被不断地更新，　

逐步缩小搜索空间的范围，同时在此范围内对更多的可能性　

进行判断，从而更加易于找到能量最低的结构。然而，仅仅　

运行一轮ＰＥＲＭ算法所获得的结果并不是最优，因此，可以　采取将每一轮空间搜索完成后的ｚ　和Ｃｎ向量的最终值作为　

中间参数保存下来的方法，用于新一轮的ＰＥＲＭ算法计算。　

比如，表１中的３条ＨＰ序列在第一轮搜索完成后，获得的　

能量分别为一６３，一４２，一６２，均大于目前所搜索到的最低能量值。　

表１　３条ＨＰ序列以及目酋搜索到的最低能量　

本文提出的分布式计算蛋自质折叠的关键也集中在ｚ　

和Ｃｎ向量上，其基本思想具体如下：　

（１）生成一合法空间结构，从而完成对ｚ　和Ｃｎ向量的初　

始化。　

（２）将ＨＰ序列和Ｚｎ，Ｃｎ向量发布到多个计算单元上，并　

启动运算。　（３）收集各个计算单元所计算出的蛋自质空间结构和中　

间参数Ｚｎ和Ｃｎ向量。　（４）在事先设定好的时间到达后，算法将对已经计算出来　

的结果进行分析，挑选出能量最低的结构。如果已经达到了　

结束要求（如所获得结构的能量比目前已知的最低能量还要　

低）则停止运算；否则保存上述能量最低结构所对应的ｚ　和　

向量，将其分发至多个计算单元上（返回至（２）），并继续进　

行计算。　

为了实现上述基本思想，用于分布式计算蛋自质折叠的　

系统至少包含２个角色：控制单元和计算单元。控制单元负　

责以下几项任务：初始化Ｚｎ和Ｃｎ向量；发布Ｚｎ和Ｃｎ向　

量；收集运算结果；分析运算结果；终止计算。控制单元的　执行伪代码如下所示：　ｖｏｉｄ　ｍｏｎｉｔｏＬｒｕｎｎｉｎｇ（ｓｅｑ）　｛　ｖｅｃｔｏｒ　Ｚｎ，Ｃｍ，，定义全局的Ｚｎ和Ｃｎ向量　，，根据序列生成初始化结构和ＺＩ１，ｃｎ向量　

ｂｅｓｔ＿ｓｍｔｃｔｕｒｅ＝ｉｎｉｔｉａｌ＿ｓｍｔｃｔｕｒｅ（ｓｅｑ，Ｚｎ，Ｃｎ）；　ｄＯ　｛　一　ｄｅｌａｙ＝Ｏ：　ｆｉｎｄ　ｉｄｌｅ　ｃｏｍｐｕｔｅｒｓ（）；，，查询系统中空闲的计算单元　ｄｉｓｔｒｉｂｕｔｅ（ｓｅｑ，Ｚｎ，ｃｎ）；，，爿辱序列，ｚｎ和ｃｎ发布到上述空闲单元　ｗａｉｔ（Ｔ）；，，等待一段时问Ｔ　

ｃｏｌｌｅｃｔｒｅｓｕｌｔｓ０；，，从各个计算单元收集计算结果　ｔｅｍｐ＿ｓｍｍｔｕｒｅ＝ａｎａｌｙｚｅｒｅｓｕｌｔｓ０；　／／找到能量最低结构并赋值　ｉｆ（ｅｎｅｒｇｙ（ｔｅｍｐ＿ｓｍｔｃｍｒｅ）＜ｅｎｅｒｇｙ（ｂｅｓｔ＿ｓｍｔｃｔｍｅ）：））　｛　ｂｅｓｔｓｍｔｃｔｔｔｒｅ＝ｔｅｍｐ＿ｓｔｒｔｔｃｔｕｒｅ；　／／以能量最低结果的Ｚｎ和Ｃｎ向量更新全局的ｚｎ和Ｃｎ向量　ｕｐｄａｔｅｐａｒａ（Ｚｎ，Ｃｎ）；　）　）　ｗｈｉｌｅ（！ｓａｔｉｓｆｙＣｏｅｓｔ＿ｓｔｕｒｃｔｕｒｅ、）、）／／如果结果满足了要求则退出　）　相对而言，计算单元所需处理的工作较简单，主要为：　

获取计算任务；处理计算任务；返回计算结果。　

假设系统中共有４个计算单元和１个控制单元，则分布　

式计算将按照图１所展示的流程进行运行。首先，控制单元　

根据蛋自质序列生成初始结构，并将相应的Ｚｎ和Ｃｎ向量发　

布到各个计算单元上。计算单元接收到序列、Ｚｎ和Ｃｎ向量　

后，将立即启动运算。经过一段时间后，控制单元将收集各　

个计算单元所计算的结果。假设共有３个计算单元获得了结　

果，控制单元将比较初始结构与上述３个结果结构的能量大　小，并将能量最低结构所对应的Ｚｎ和Ｃｎ向量重新发布到已　

空闲的３个计算单元上，且将能量最低结构所对应的ｚ　和　

Ｃｎ向量进行记录，用于后续比较。当下一轮更新时，假设同　

样有３个计算单元计算出了结果。控制单元在收集和分析结　果后，会将能量最低结构所对应的Ｚｎ和Ｃｎ向量再次发布到　

空闲节点上。如此往复，直到计算结果满足结束条件为止。　

上述的计算模式需要大量的计算资源进行反复运算，以取得　最优的结果，因此适合在分布式的网络计算环境进行运作。