噬菌体基因文库控制元件测定的并行处理方法

《噬菌体基因文库控制元件测定的并行处理方法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、∞lO年lOft沈阳航空工业学院学报第27卷第5期JournalofShenyangInstituteofAeronauticalEngineeringOet．2010VoI．27No．5文章编号：1007—1385(2010)05—0063—05噬菌体基因文库控制元件测定的并行处理方法孙伟东h2王微微2马宗民1(I．东北大学信息科学与工程学院，辽宁沈阳110004；2．沈阳航空航天大学计算机学院，辽宁沈阳110136)摘要：在噬菌体基因文库的研究中，理解基因的表达机制占有重要的地位，其中最为重要的一个环节是控制元件的测定，目前大部分控制

2、元件测定方法都是基于基因结构的概率模型。介绍了一种不依赖于任何实验数据和先验数据的噬菌体基因文库控制元件测定方法，采用字符串模式匹配算法扫描噬菌体基因序列，发现并提取出重复频度高的子序列(可能的控制元件)，但该方法计算复杂度为O(胪)。为了提高对基因序列的控制元件测定效率，进一步提出了该算法在局域网环境下的并行处理解决方案，实验表明这种基于数据分割的并行处理方法极大的加快了序列处理速度，进而扩大了算法的应用范围。关键词：噬菌体基因文库；并行处理；控制元件测定；序列分析中图分类号：TP311文献标识码：Adoi：10．3969／j．issn

3、．1007—1385．2010．05．014随越来越多的基因文库测序的完成，如何从这些海量的信息中找到基因序列并确定它们的结构和功能，正在成为生物学领域和信息处理领域研究的主要方向¨j。而确定基因序列的所要解决的第一个问题就是要找到控制基因转录的控制元件，为了解决这一问题，已经提出了许多基于概率模型的控制元件测定算法，这些算法大都需要实验数据或先验数据的支持【2。4]。噬菌体基因文库相对于其它基因文库具有体积小、结构紧凑的特点”J，这就意味着控制元件出现的频率相对较高。本文首先介绍了一种不依赖于任何实验数据和先验数据的噬菌体基因文库控制元

4、件测定方法，直接通过字符串模式匹配算法扫描噬菌体基因序列，发现并提取出重复频度高的子序列(可能的控制元件)，这是一种比较客观的噬菌体控制元件测试方法∞J。但该算法的时间复杂度为D(Ⅳ2)，对于体积较大的噬菌体基因文库，处理时间可能长达几小时，甚至几天，使用起来不是很方便。为了解决这一问题，本文提出了一种基于并行处理的噬菌体基因文库控制元件测定方法，即在网络环境下采用并行处理的方法实现对噬菌体基因文库中控制元件的测定，使收稿日期：2010—07—14作者简介：孙伟东(1974一)，男，黑龙江哈尔滨人，博士生，副教授，主要研究方向：分布式与并

5、行处理，E—mail：sunweidong@syi一∞．edu．ello得计算机网络中的某一节点(管理节点)可以利用网络中其它节点(工作节点)的计算资源，提高处理速度。1控制元件测定算法该算法首先根据需要进行处理的基因文库G(主要由A、C、G和T等一系列字符组成的字符串序列)、待比较的子序列长工计算出基因文库中包含的待比较的子序列个数，v，N=长度IGI一￡+l，并提取出这些子序列，提取过程如图1所示；然后把每种可能出现的控制元件与基因文库进行比较，根据用户设置的失配字符数D(允许不匹配的字符数)，计算出所有可能出现的控制元件(失配字符数

6、小于等于D的子序列)，并用结构数组尺[Ⅳ]同时记录下该控制元件的出现位置和出现数目；最后统计每种控制元件出现的次数，即控制元件的出现频率，以及它在哪个范围内出现的频度高，这些结果将用于对控制元件的测定与分析，从而摆脱先验数据的限制。该算法需要比较的子序列为N木(Ⅳ一1)木1／2，时间复杂度为D(Ⅳ2)，单台计算机很难处理较大规模的噬菌体基因文库，因此可考虑采用数据并行计算的方法MJ。2并行化方法对噬菌体基因文库中控制元件的测定过程，沈阳航空工业学院学报第27卷图1子序列提取过程就是在给定参数的基础上顺序扫描噬菌体基因文库并进行字符串模式匹

7、配，把匹配成功的、可能为控制元件的数据信息记录下来，进而发现并提取出那些保存度很高的控制元件(较高的重复出现概率)。由于处理过程涉及网络中的多个计算节点，这就需要设计多个节点之间的网络通信协议和任务调度程序，以便使它们能相互协同工作来完成高强度密集计算任务。本系统采用了管理者一工作者并行处理模型【7]，具体组织结构如图2所示，基本功能包括：(1)管理者节点与工作节点之间能够传送命令、数据文件及结果文件；(2)各工作节点都能对基因文库进行字符串模式识别；(3)管理者节点根据需求对任务进行分解，并把子任务分配给工作节点；(4)管理者节点能对各

8、工作节点得到的计算结果进行汇总，并按要求输出最终结果。图2系统组织结构管理者节点与工作节点的通信采用面向连接的TCP协议，以便保证通信的可靠、及时和便捷。系统中的程序可分为两大类，即工作程序(