生物计算(或生物信息学)是一门研究如何将计算方法(计算机科技)用于解决生物学问题,特别是分子生物学问题的新兴的前沿学科。生命的基本构成是蛋白质,而蛋白质又由20种不同的氨基酸组成。我们身体中来自父母的遗传信息存储在DNA中,这些信息被用来复制DNA,还通过DNA传递给RNA,再由RNA传递给蛋白质,从而组装出特定的蛋白质。DNA主要由4种碱基组成,它们是腺嘌呤(Adenine,简写为A)、鸟嘌呤(Guanine,简写为G)、胞嘧啶(Cytosine,简写为C)、胸腺嘧啶(Thymine,简写为T)。RNA的组成与DNA很相似,只是由尿嘧啶(Uridine ,简写为U)代替胸腺嘧啶T。DNA和RNA的一个属性是碱基相互配对,这样的配对就构成特定的序列。国际社会通过努力成功地将这些序列信息搜集起来存放到一个地方方便人们查询。对DNA来讲,目前国际上已有三个组织相互合作以从事这项工作,它们一个在日本,一个在欧洲,一个在美国,相应的数据库是DDBJ、EMBL和GenBank。这些数据库经常相互交换数据,所以查询其中的一个数据库就相当于查询着三个数据库。问题是这些数据库相当庞大,使得我们必须高效率的将我们自己的序列与这海量数目的其他序列相比较。一些程序,诸如BLAST 和FASTA,被编写用以在数据库中高速查询某一序列。Smith -Waterman算法是目前最重要的一种局部联配算法,该算法先用迭代方法计算出两个序列的所有可能相似性比较的分值,然后通过动态规划的方法回溯寻找最优相似性比较。但将此算法用于同源长序列的局部联配时,经常会出现马赛克问题(相似度很低的保守区域夹在两个相似度很高的区域中间)。在分析问题成因的基础上,提出利用动态加速扣分策略解决马赛克问题,即在计算得分矩阵的过程中,如果存在保守区域,则加大扣分的力度,争取在离开保守区域前让得分为0,从而将保守区域切断。实验结果表明,在基本不改变原Smith -Waterman算法的前提下,动态加速扣分策略顺利解决了序列局部联配中的马赛克问题,并且没有显著增加算法的复杂度(时间复杂度和空间复杂度)。 基本局部联配查询工具(BLAST)是一种序列快速比较方法,属于启发式算法。该算法集中于发现具有较高的相似性的局部联配,即记录最大片段对(MSP)的分数,且局部联配中不能含有空位。位点特异迭代BLAST(PSI-BLAST)延伸一个选中字串的长度标准,在序列的联配中允许出现空位,搜索速度是原始算法的三倍。设计并实现了采用并行化方法来优化BLAST,并行计算平台采用MPI。主节点按负载均衡策略为各个从节点划分搜索子空间并将分配结果传送给它们。从节点再在各自的搜索空间进行序列检索,并将检索结果传回主节点。主节点收集各从节点的检索结果,并对结果空间进行重新联配,最后输出联配结果。文章还分析了软件的并行加速比和并行效率等性能,最后给出了测试结果。