Blast工具的介绍和并行优化
发信人: palomino (~快马加鞭~), 信区: Bioinformatics
标 题: Blast工具的介绍和并行优化
发信站: 北大未名站 (2002年03月14日16:12:42 星期四), 转信
Blast工具的介绍和并行优化
摘要
随着基因组计划的实施，分子生物信息迅速的增长。以核酸序列数据库为代表
的分子生物信息数据正以指数增加，而对于这些实验数据在计算机上的存储检索却
远远跟不上这种发展。因此我们需要对原来的生物学数据处理工具进行研究和改进
。本文介绍了当前最为流行的核酸序列数据库检索程序——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
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
则对应的核酸基因序列编码（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对这三个数据库进行检索，其时间结果如下：
数据库
次数
步骤1消耗时间
步骤2消耗时间
步骤3消耗时间
FUN
13.7MB
1
17.7
3756.0
575.2
2
13.9
3937.9
611.0
3
13.9
3788.9
611.4
HTG
64.7MB
1
33.1
26477.2
727.0
2
32.8
27620.3
671.6
3
34.2
26283.9
663.2
ECOIL
287.6MB
1
52.4
645683.7
617.2
2
56.8
724813.0
625.8
3
48.3
685812.4
643.9
表-2 Blast串行程序的性能数据
（时间单位为ms，已经排除数据库数据驻留内存对第二次测试的影响。）
4.2. Blast的并行化
由串行Blast的工作流程可以清楚的发现，Blast在进行检索时采用的方法是循
环匹配所有的记录。我们只需将这种循环匹配平均地分配到并行系统的各个节点上
，各个节点分别执行各自的匹配操作，最后将匹配的结果统计起来就可以初步实现
Blast程序的并行操作。对Blast实行并行化实际上就是将整个检索空间分解成若干
个子空间，为各个子节点分配一个子空间，子节点在各自的子空间进行检索，检索
完成后，由主控节点归纳统计各个子节点上的结果，然后生成并打印最后的统计结
果。
由于Blast程序中牵涉到许多的与生物学相关的计算，检索结果的数据中包含
各种在检索过程中生成的数据，有些数据的值和检索的空间范围有关系。如果采取
每个子节点生成自己的检索结果的方法，由于每个子节点的结果会由于搜索的集合
不同而有所不同，在最后主控节点综合所有结果时，需要归纳所有子节点的结果，
这样就干涉了Blast程序的内部计算。同时各个子节点需要向主节点传递检索结果
，而检索结果中包含大量的指针。
有一种比较好的并行方法，为各个子节点分配一个记录检索空间，子节点将可
能满足条件的记录标记出来，然后传送给主控节点，主控节点再在这个可能的检索
空间上进行一次检索，获得检索结果。这种方法只需要将各个子节点检索结果中的
记录序号传递给主节点，主节点在搜集到所有子节点上的记录序号后，再在这个记
录序号集上进行一次检索，就可以直接在主节点中生成完全正确的检索结果。虽然
这种方法由于在子节点完成检索后，主节点还要进行一次检索，在时间上可能会慢
一些。但是它大大减少了子节点和主节点之间的通讯量，并且不需要干涉检索结果
具体的生成过程，便于程序的并行实现。
4.3. Blast并行程序的实现和性能
4.3.1. Blast并行程序的实现
Blast的并行化采用MPI并行开发环境在曙光2000实现，实现过程如下：
1. 由主节点读取数据库信息，根据参与查询节点的数目将数据库的记录
分解成与节点匹配的几个查询范围，然后将待查询的序列数据和数据库名称以及查
询的记录范围，传递给各个子节点；
2. 修改BioseqBlastEngine函数，在该函数中加入两个参数，用来接受数
据库查询的记录范围，各个子节点开始在自己的范围内开始查询，查询完成后生成
查询结果——RESEARCH结构数据；
3. 增加处理查询结果的函数，HandleSubResult，这个函数在每个子节点
上运行处理各自的查询结果，从结果中读取符合条件的记录序号，并将序列序号传
递给主节点；
4. 主节点获取所有子节点的查询结果后，在查询结果的范围中再进行一
次查询，筛选出最符合条件的若干记录，并重新生成查询结果——RESEARCH结构数
据，并打印该数据。
4.3.2. Blast并行程序的性能
我们采用与Blast串行程序相同的数据进行了并行程序的测试，测试使用曙光2000
中的四个节点，其中一个节点既作为主节点又用做子节点。其测试结果如下：
数据库
次数
步骤1消耗时间
步骤2消耗时间
步骤3消耗时间
FUN
13.7MB
1
142.3
8641.8
641.3
2
139.0
7986.9
622.0
3
139.9
8312.9
641.4
HTG
64.7MB
1
182.1
18560.7
688.2
2
184.6
20194.3
675.4
3
179.3
18910.9
681.3
ECOIL
287.6MB
1
194.6
385781.7
693.9
2
201.8
367914.5
698.2
3
197.6
387761.4
711.4
表-3 并行Blast程序的性能时间表
由表-2和表-3的对比可以看出，当数据库的规模达到一定的大小时，并行Blast程
序能够大大的降低检索时间，在四个节点的情况下，可以降低大约50%的检索时间
。
5. 结束语
随着生物技术的发展，生物信息处理技术必须进行改进以适应这种形式。而对
于象生物信息数据库这种大数据量的处理，采取并行技术是其必然的趋势，本文所
做的介绍以及优化工作只是这种工作的一个开始，以后将会有更多的应用及研究成
果出现。
参考文献：
[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
--
_ _____ ___ _ _ ___ ___ __
( ) ( _ ) ( _`\ ( ) ( ) ( _`\ ( _`\ | |
| | | ( ) | | ( (_) | |/'/' | (_(_) | | ) | | |
| | _ | | | | | | _ | , < | _)_ | | | ) | |
| |_( ) | (_) | | (_( ) | |\`\ | (_( ) | |_) | |==|
(____/' (_____) (____/' (_) (_) (____/' (____/' |__|
※ 来源:·北大未名站 bbs.pku.edu.cn·[FROM: 162.105.14.57]
[返回] 中文XML论坛 - 专业的XML技术讨论区 →
计算机技术与应用 → 『 生物信息学 』 → Blast工具的介绍和并行优化
(订阅本版)
2004/9/23 2:05:00
新浪微博
Blast工具的介绍和并行优化
