blast工具的介绍和并行优化

《blast工具的介绍和并行优化》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、生物秀—专心做生物【www.bbioo.com】易生物—实验室问题解决伙伴【www.ebioe.com】Blast工具的介绍和并行优化摘要随着基因组计划的实施，分子生物信息迅速的增长。以核酸序列数据库为代表的分子生物信息数据正以指数增加，而对于这些实验数据在计算机上的存储检索却远远跟不上这种发展。因此我们需要对原来的生物学数据处理工具进行研究和改进。本文介绍了当前最为流行的核酸序列数据库检索程序——Blast，分析了制约Blast性能的原因，最后实现了对串行Blast进行并行化，通过在曙光2000上

2、的测试，证实了这种优化工作大大改进Blast的检索性能。关键字：分子生物信息处理，基因序列数据库，基因序列数据库检索工具，模式匹配算法，并行程序设计1.NCBI和Blast工具NCBI（NationalCentreforBiotechnologyInformation），成立于1988年，其主要目标是“生成生物学，生物化学，生物基因学的信息自动化系统，生成分析、解释和处理分子生物学数据的先进工具”。Blast是NCBI研制的一个生物基因数据库系统，该系统对于生物基因序列数据在计算机中的表达和处理作了

3、许多的研究，提供了一个快速的基于碱基数据的搜索引擎。由于Blast功能强大，检索速度快，所以Blast工具流行于世界上几乎所有的生物信息中心。Blast作为一个快速的基因数据库检索工具，提供如下检索功能：功能名称功能Blastn>用核酸序列授索核酸序列数据库Blastp用蛋白质序列授索蛋白质序列数据库Blastx用核酸翻译的蛋白质序列授索蛋白质序列数据库用蛋白质序列授索核酸翻译的蛋白质序列数据库>Tblastx用核酸翻译的蛋白质序列授索核酸翻译的蛋白质序列数据库表-1Blast提供的检索功能Blas

4、t提供两种类型的数据库，即核酸序列数据库和蛋白质序列数据库，这两种数据库的结构一样，所用的数据检索方法也一样，所不同的是核酸数据库和蛋白质数据库的序列数据编码单位不一样。2.生物基因序列数据和Blast中的数据结构2.1.生物基因序列数据生物学中最重要的两种物质有：DNA和蛋白质。众所周知，DNA是一种由碱基按一定规则排列而成的双链结构生物大分子。这种碱基排列顺序就构成了生物的遗传信息。蛋白质是由DNA根据链结构上的某些功能碱基序列复制而成的具有特殊功能的生物大分子。生物基因包括DNA链上的碱基及其

5、排列顺序。虽然碱基的数目只有四种Adenine(A)、Cytosine(C)、Guanine(G)、Thymine(T)，而它们在DNA上做各种有序的排列形成了生物的多样性。所以对这种碱基序列进行测序、编码和研究是生物学研究最重要的工作。生物基因序列数据就是对于某一生物基因采用某种编码方式编码产生的数据。2.2.Blast中的数据结构Blast使用ASN数据描述语言定义了一种基因序列数据模型。随着Blast的广泛流行，这种基因序列数据模型也成为该行业的标准。数据结构Bioseq（Biological

6、Sequence），就是Blast中对基因序列数据的定义。Bioseq的定义如下：Bioseq::=SEQUENCE{idSETOFSeq_id，descrSeq-descrOPTIONAL,instSeq-inst,annotSETOFSeq-annotOPTIONAL1生物秀论坛——学术交流、资源共享、互助社区www.bbioo.com/bbs生物秀—专心做生物【www.bbioo.com】易生物—实验室问题解决伙伴【www.ebioe.com】Bioseq定义为如下四个元素的有序序列，id、d

7、escr、inst和annot。其中descr和annot包含一些描述性的信息，是可选项。id是一个标识符集合，他允许一个Bioseq有多个标识符，允许以多种标识从数据库中检索Bioseq，当然一个Bioseq多个id并不意味着多个Bioseq拥有同一个ID。Inst是Bioseq的序列数据。由于基因序列数据具有太多的类型可供选择，所以Blast不得不也为inst定义一个数据模型——Seq_inst。其简要定义如下：Seq_inst::=SEQUENCE{......seq-dataSeq-data

8、OPTIONAL,extSeq-extOPTIONAL,histSeq-histOPTIONAL}其中seq_data就是基因序列编码在计算机中的表示。对于核酸基因序列，由于组成他们的只有四种碱基，所以对核酸基因序列碱基的编码如下：碱基——编码Adenine(A)——00，Cytosine(C)——01，Guanine(G)——10，Thymine(T)——11，在计算机中一个ASCII码的字符可以表示一个由四个碱基组成的核酸基因序列片段。3.碱基匹配算法和Blast