Blast工具的介绍和并行优化
 

摘要

    随着基因组计划的实施，分子生物信息迅速的增长。以核酸序列数据库为代表的分子生物信息数据正以指数增加，而对于这些实验数据在计算机上的存储检索却远远跟不上这种发展。因此我们需要对原来的生物学数据处理工具进行研究和改进。本文介绍了当前最为流行的核酸序列数据库检索程序——Blast，分析了制约Blast性能的原因，最后实现了对串行Blast进行并行化，通过在曙光2000上的测试，证实了这种优化工作大大改进Blast的检索性能。

关键字：分子生物信息处理，基因序列数据库，基因序列数据库检索工具，
       模式匹配算法，并行程序设计

1.    NCBI 和 Blast 工具

NCBI（National Centre for Biotechnology Information），成立于1988年，其主要目标是“生成生物学，生物化学，生物基因学的信息自动化系统，生成分析、解释和处理分子生物学数据的先进工具”。Blast是NCBI研制的一个生物基因数据库系统，该系统对于生物基因序列数据在计算机中的表达和处理作了许多的研究，提供了一个快速的基于碱基数据的搜索引擎。由于Blast功能强大，检索速度快，所以Blast工具流行于世界上几乎所有的生物信息中心。

Blast作为一个快速的基因数据库检索工具，提供如下检索功能：

表-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