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

NCBI和Blast工具

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

Blast作为一个快速的基因数据库检索工具，提供多种检索功能，包括用核酸序列检索核酸序列数据库、用蛋白质序列检索蛋白质序列数据库等，如表1所示。

表1 Blast提供的检索功能

Blast提供两种类型的数据库，即核酸序列数据库和蛋白质序列数据库，这两种数据库的结构相同，所用的数据检索方法也相同，不同的是核酸数据库和蛋白质数据库的序列数据编码单位不一样。

生物基因序列数据和Blast中的数据结构

生物学中最重要的两种物质是DNA和蛋白质。DNA是一种由碱基按一定规则排列而成的双链结构生物大分子，其碱基排列顺序构成了生物的遗传信息。蛋白质是由DNA根据链结构上的某些功能碱基序列复制而成的具有特殊功能的生物大分子。生物基因包括DNA链上的碱基及其排列顺序。虽然碱基的数目只有四种（Adenine(A)、Cytosine(C)、Guanine(G)、Thymine(T)），但它们在DNA上做各种有序的排列形成了生物的多样性。因此，对这种碱基序列进行测序、编码和研究是生物学研究最重要的工作。生物基因序列数据就是对于某一生物基因采用某种编码方式编码产生的数据。

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。Inst是Bioseq的序列数据。

碱基匹配算法和Blast中的检索方法

在Blast进行检索时，首先需要将数据库名称、需检索的基因序列数据以及以何种方式进行检索通知Blast。Blast采用了一种窗口算法来进行匹配。这种算法通过定义一个固定大小的窗口，在二进制序列上滑动，计算窗口值的哈希值，并与待匹配序列的哈希值进行比较，从而快速定位匹配区域。

Blast检索速度的优化

随着生物学的发展，Blast数据库的规模越来越大，数据库的更新速度也越来越快，越来越多的人希望使用Blast数据库。然而，Blast系统由于数据库的庞大具有三个最大的弱点：检索速度慢、对系统的I/O要求高、程序消耗内存大。

为了优化Blast的检索速度，可以采用并行机制对其进行改进。Blast是一个对数据库进行检索的工具，这种检索程序一般在时间和空间上的数据相关性比较小，因此适合并行化处理。