摘要
随着基因组计划的实施，分子生物信息迅速的增长。以核酸序列数据库为代表的分子生物信息数据正以指数增加，而对于这些实验数据在计算机上的存储检索却远远跟不上这种发展。因此我们需要对原来的生物学数据处理工具进行研究和改进。本文介绍了当前最为流行的核酸序列数据库检索程序——Blast，分析了制约Blast性能的原因，最后实现了对串行Blast进行并行化，通过在曙光2000上的测试，证实了这种优化工作大大改进Blast的检索性能。
关键字：分子生物信息处理，基因序列数据库，基因序列数据库检索工具， 模式匹配算法，并行程序设计 1. NCBI 和 Blast 工具
NCBI（National Centre for Biotechnology Information），成立于1988年，其主要目标是“生成生物学，生物化学，生物基因学的信息自动化系统，生成分析、解释和处理分子生物学数据的先进工具”。Blast是NCBI研制的一个生物基因数据库系统，该系统对于生物基因序列数据在计算机中的表达和处理作了许多的研究，提供了一个快速的基于碱基数据的搜索引擎。由于Blast功能强大，检索速度快，所以Blast工具流行于世界上几乎所有的生物信息中心。
Blast作为一个快速的基因数据库检索工具，提供如下检索功能：
功能名称 Blastn> Blastp Blastx
Tblastx
功能
用核酸序列授索核酸序列数据库
用蛋白质序列授索蛋白质序列数据库
用核酸翻译的蛋白质序列授索蛋白质序列数据库 用蛋白质序列授索核酸翻译的蛋白质序列数据库> 用核酸翻译的蛋白质序列授索核酸翻译的蛋白质序列数据库
表-1 Blast提供的检索功能
Blast提供两种类型的数据库，即核酸序列数据库和蛋白质序列数据库，这两种数据库的结构一样，所用的数据检索方法也一样，所不同的是核酸数据库和蛋白质数据库的序列数据编码单位不一样。
2. 生物基因序列数据和Blast中的数据结构
2.1. 生物基因序列数据
生物学中最重要的两种物质有：DNA和蛋白质。众所周知，DNA是一种由碱基按一定规则排列而成的双链结构生物大分子。这种碱基排列顺序就构成了生物的遗传信息。蛋白质是由DNA根据链结构上的某些功能碱基序列复制而成的具有特殊功能的生物大分子。生物基因包括DNA链上的碱基及其排列顺序。虽然碱基的数目只有四种Adenine(A)、Cytosine(C)、Guanine(G)、Thymine(T)，而它们在DNA上做各种有序的排列形成了生物的多样性。所以对这种碱基序列进行测序、编码和研究是生物学研究最重要的工作。生物基因序列数据就是对于某一生物基因采用某种编码方式编码产生的数据。
2.2. Blast中的数据结构
Blast使用ASN数据描述语言定义了一种基因序列数据模型。随着Blast的广泛流行，这种基因序列数据模型也成为该行业的标准。数据结构Bioseq（Biological Sequence），就是Blast中对基因序列数据的定义。 Bioseq的定义如下：
Bioseq::= SEQUENCE {
id SET OF Seq_id，
descr Seq-descr OPTIONAL, inst Seq-inst,
annot SET OF Seq-annot OPTIONAL
1
生物秀论坛——学术交流、资源共享、互助社区 www.bbioo.com/bbs生物秀—专心做生物【www.bbioo.com】 易生物—实验室问题解决伙伴【www.ebioe.com】Bioseq定义为如下四个元素的有序序列，id、descr、inst和annot。其中descr和annot包含一些描述性的信息，是可选项。id是一个标识符集合，他允许一个Bioseq有多个标识符，允许以多种标识从数据库中检索Bioseq，当然一个Bioseq多个id并不意味着多个Bioseq拥有同一个ID。Inst是Bioseq的序列数据。由于基因序列数据具有太多的类型可供选择，所以Blast不得不也为inst定义一个数据模型——Seq_inst。其简要定义如下：
Seq_inst::= SEQUENCE { ......
seq-data Seq-data OPTIONAL , ext Seq-ext OPTIONAL , hist Seq-hist OPTIONAL }
其中seq_data就是基因序列编码在计算机中的表示。对于核酸基因序列，由于组成他们的只有四种碱基，所以对核酸基因序列碱基的编码如下： 碱基——编码 Adenine(A)——00， Cytosine(C)——01， Guanine(G)——10， Thymine(T)——11，
在计算机中一个ASCII码的字符可以表示一个由四个碱基组成的核酸基因序列片段。
3. 碱基匹配算法和Blast中的检索方法
对于一个已知的基因序列片段如何在数据库中找出与之相近的记录，并标识出该片段在记录中的位置，是Blast中最关键的部分。由于Blast数据库中含有成千上万条基因序列记录，而每一条序列记录又含有成千上万个碱基，这些碱基以一定的编码方式存储在数据库文件之中，所以这种检索操作也是Blast中最为耗时的操作。
在Blast进行检索时，首先需要将数据库名称、需检索的基因序列数据以及以何种方式进行检索通知Blast，在获得这些参数之后，Blast将需检索的序列数据读人一个Bioseq的结构中，将数据库中所有的记录采用MAP方式映象到内存中，然后从数据库的第一条记录开始到最后一条记录逐条进行比较。在这种比较的过程中，Blast采用了一种窗口算法来进行这种匹配。这种算法描述如下：
第一步，对匹配基因序列数据进行计算。我们假定匹配序列如下（采用核酸基因序列）： >test
AATAATAAAATAGGGCGTGC
则对应的核酸基因序列编码（Encode）如下：
00 00 11 00 00 11 00 00 00 00 11 00 10 10 10 01 10 11 10 01
定义一个16比特大小的窗口（Window），16比特大小表示从窗口来看一个二进制串，只能看到该串的一个连续的16bits子串。窗口可以在二进制串上左右移动，每次移动步长为1byte，窗口的值为二进制子串的值，窗口的位置为窗口最后一位在二进制串上的位置。对于一个确定的二进制串和窗口来说，窗口的每一个位置都对应一个16bits的二进制整数值。下表计算出Encode上Window的所有窗口位置和相应的窗口值：
Position of Window Value of Window Binary String of Window 8 3120 0000110000110000 9 12480 0011000011000000 10 49920 1100001100000000 11 3075 0000110000000011 12 12300 0011000000001100 13 49202 1100000000110010 14 202 0000000011001010 15 810 0000001100101010 16 3241 0000110010101001 17 12966 0011001010100110 18 51867 1100101010011011 19 10862 0010101001101110 20 43449 1010100110111001
第二步，对数据库中的每一个记录序列数据定义同样的窗口，在匹配时顺序计算其窗口值，如果数据库序列数据的某一窗口值与匹配序列的窗口值列表中的某一项相等，则比较序列数据的前后部分，如果前后都相等，则找出了一个符合条件的子串，否则窗口在数据库序列数据中后移16bits，再顺序计算其窗口值。假定数据库的一个记录序列数据（核酸序列数据）如下： >Database Sequence
ACTTTCAATAATAAAATAGGGCGTGCAACT
2
生物秀论坛——学术交流、资源共享、互助社区 www.bbioo.com/bbs生物秀—专心做生物【www.bbioo.com】 易生物—实验室问题解决伙伴【www.ebioe.com】则对应的核酸基因序列编码（Encodebase）如下： 00 01 11 11 11 01 00 00 11 00 00 11 00 00 00 00 11 00 10 10 10 01 10 11 10 01 00 00 01 00 00 01
定义如同匹配串的窗口（windowbase），开始计算窗口在位置8时的窗口值为2036，没有一个匹配串的窗口值与之相等；windowbase窗口下移16bits，再计算位置为16的窗口值为12480，他和匹配串窗口位置9的窗口值相等，这时比较前后剩下的序列数据发现该数据库序列数据包含一个与待匹配序列完全相同的序列片段。如此类推直到找出所有满足条件的记录。
4. Blast检索速度的优化
随着生物学的发展，blast数据库的规模也越来越大，数据库的更新速度也越来越快，越来越多的人希望使用blast数据库。但是Blast系统由于数据库的庞大具有三个最大的弱点： 1）、检索速度慢；
2）、对系统的I/O的要求高； 3）、程序消耗内存大
由于blast数据库大，检索时需要进行匹配的序列数据多，检索速度不可避免会慢，并且随着数据库的进一步膨胀，Blast的速度将会使用户不可忍受。同时，每一种生物的基因序列数据都是一个极其庞大的数据，必须将它分解成几个基因序列数据库。一般典型的基因序列数据库大小在100MB~500MB之间，Blast需要将数据库序列数据映象到内存中，这将会消耗大量的时间用于数据库数据的I/O操作，并且在运行中消耗大量的内存资源。而现在人们对生物学进行研究时，对生物基因序列数据却越来越依赖。随着Blast数据库的增大，Blast的检索速度会越来越慢，所以必须对Blast进行改进。
现在，在模式匹配算法上进行性能改进的空间不大，即使有改进，它所需要的时间及改进所取得的效果不可能满足blast数据库膨胀对Blast系统的要求。Blast是一个对数据库进行检索的工具，这种检索程序一般在时间和空间上的数据相关性是比较小的，对于Blast性能问题可以采用并行机制对其进行改进。
4.1. Blast串行程序的性能
Blast的检索程序是一个结构非常简单明了的串行程序，其大致执行流程如图-1。
在实验中我们采用了三个核酸序列数据库，Fun、Htg和Ecoil。Fun数据库的基因序列数据为13.7MB，Htg数据库的大小为67.4MB，Ecoil数据库的大小为287.6MB。采用串行Blast对这三个数据库进行检索，其时间结果如下： 数据库 FUN 13.7MB HTG 64.7MB ECOIL 287.6MB
表-2 Blast串行程序的性能数据
（时间单位为ms，已经排除数据库数据驻留内存对第二次测试的影响。） 次数 步骤1消耗时间 步骤2消耗时间 步骤3消耗时间 1 17.7 3756.0 575.2 2 13.9 3937.9 611.0
3788.9 611.4 3 13.9
1
2 3 33.1 32.8 34.2 26477.2 27620.3 26283.9 727.0 671.6 663.2
1 2 3 52.4 56.8 48.3 645683.7 724813.0 685812.4 617.2 625.8 643.9
3
生物秀论坛——学术交流、资源共享、互助社区 www.bbioo.com/bbs生物秀—专心做生物【www.bbioo.com】 易生物—实验室问题解决伙伴【www.ebioe.com】
图-1 Blast串行检索程序流程
4.2. Blast的并行化
由串行Blast的工作流程可以清楚的发现，Blast在进行检索时采用的方法是循环匹配所有的记录。我们只需将这种循环匹配平均地分配到并行系统的各个节点上，各个节点分别执行各自的匹配操作，最后将匹配的结果统计起来就可以初步实现Blast程序的并行操作。对Blast实行并行化实际上就是将整个检索空间分解成若干个子空间，为各个子节点分配一个子空间，子节点在各自的子空间进行检索，检索完成后，由主控节点归纳统计各个子节点上的结果，然后生成并打印最后的统计结果。
由于Blast程序中牵涉到许多的与生物学相关的计算，检索结果的数据中包含各种在检索过程中生成的数据，有些数据的值和检索的空间范围有关系。如果采取每个子节点生成自己的检索结果的方法，由于每个子节点的结果会由于搜索的集合不同而有所不同，在最后主控节点综合所有结果时，需要归纳所有子节点的结果，这样就干涉了Blast程序的内部计算。同时各个子节点需要向主节点传递检索结果，而检索结果中包含大量的指针。
有一种比较好的并行方法，为各个子节点分配一个记录检索空间，子节点将可能满足条件的记录标记出来，然后传送给主控节点，主控节点再在这个可能的检索空间上进行一次检索，获得检索结果。这种方法只需要将各个子节点检索结果中的记录序号传递给主节点，主节点在搜集到所有子节点上的记录序号后，再在这个记录序号集上进行一次检索，就可以直接在主节点中生成完全正确的检索结果。虽然这种方法由于在子节点完成检索后，主节点还要进行一次检索，在时间上可能会慢一些。但是它大大减少了子节点和主节点之间的通讯量，并且不需要干涉检索结果具体的生成过程，便于程序的并行实现。 Blast程序并行方法的示意图如下：
4
生物秀论坛——学术交流、资源共享、互助社区 www.bbioo.com/bbs生物秀—专心做生物【www.bbioo.com】 易生物—实验室问题解决伙伴【www.ebioe.com】
图-2 Blast的并行方法
4.3. Blast并行程序的实现和性能 4.3.1. Blast并行程序的实现
Blast的并行化采用MPI并行开发环境在曙光2000实现，实现过程如下：
1. 由主节点读取数据库信息，根据参与查询节点的数目将数据库的记录分解成与节点匹配的几个查询范围，然后将待查询的序列数据和数据库名称以及查询的记录范围，传递给各个子节点；
2. 修改BioseqBlastEngine函数，在该函数中加入两个参数，用来接受数据库查询的记录范围，各个子节点开始在自己的范围内开始查询，查询完成后生成查询结果——RESEARCH结构数据；
3. 增加处理查询结果的函数，HandleSubResult，这个函数在每个子节点上运行处理各自的查询结果，从结果中读取符合条件的记录序号，并将序列序号传递给主节点；
4. 主节点获取所有子节点的查询结果后，在查询结果的范围中再进行一次查询，筛选出最符合条件的若干记录，并重新生成查询结果——RESEARCH结构数据，并打印该数据。 Blast并行程序的流程如下：
5
生物秀论坛——学术交流、资源共享、互助社区 www.bbioo.com/bbs生物秀—专心做生物【www.bbioo.com】 易生物—实验室问题解决伙伴【www.ebioe.com】
图-3 Blast并行程序流程图
4.3.2. Blast并行程序的性能
我们采用与Blast串行程序相同的数据进行了并行程序的测试，测试使用曙光2000中的四个节点，其中一个节点既作为主节点又用做子节点。其测试结果如下：
数据库 FUN 13.7MB HTG 64.7MB ECOIL 287.6MB
表-3 并行Blast程序的性能时间表
由表-2和表-3的对比可以看出，当数据库的规模达到一定的大小时，并行Blast程序能够大大的降低检索时间，在四个节点的情况下，可以降低大约50%的检索时间。
5. 结束语
6
次数 步骤1消耗时间 步骤2消耗时间 步骤3消耗时间 1 142.3 8641.8 641.3 2 139.0 7986.9 622.0 3 139.9 8312.9 641.4
1 2 3 182.1 184.6 179.3 18560.7 20194.3 18910.9 688.2 675.4 681.3
1 2 3 194.6 201.8 197.6 385781.7 367914.5 387761.4 693.9 698.2 711.4
生物秀论坛——学术交流、资源共享、互助社区 www.bbioo.com/bbs 随着生物技术的发展，生物信息处理技术必须进行改进以适应这种形式。而对于象生物信息数据库这种大数据量的处理，采取并行技术是其必然的趋势，本文所做的介绍以及优化工作只是这种工作的一个开始，以后将会有更多的应用及研究成果出现。 参考文献：
[1] Altschul.F.F., Gish.W., Miller.W., Myers.E.W., and Lipman.D.J.(1990) Basic local alignment search tool. J.Mol.Biol., 215, 403-412
[2] Altschul.S.F., Madden.T.L., Schaffer.A.A., Zhang.J., Zhang.Z., Miller.W. and Lipman.D.J., (1997) Gapped BLAST and PSI BLAST: a new generation of protein database search programs. Nucl. Acids Res., 25, 3389-3402.
[3] Introduction To Computational Biology by Michael S. Waterman, 1995
[4] W.R.Pearson(1990) “Rapid and Sensitive Sequence Comparison with FASTP and FASTA” Methods in Enzymology 183:63-98 [5] http://cbi.pku.edu.cn/
[6] The Design and Analysis of Parallel Algorithms by Selim G. Akl, 1996
7
因篇幅问题不能全部显示，请点此查看更多更全内容