本站原创本文是一篇数据库论文范文,数据库方面毕业论文题目,关于搜索比对算法相关专科毕业论文范文。适合数据库及序列及算法方面的的大学硕士和本科毕业论文以及数据库相关开题报告范文和职称论文写作参考文献资料下载。
摘 要：在蛋白质结构预测算法中同源建模被认为是当前最成功的预测算法,文中指出了同源建模算法存在的缺陷,并且针对这一缺陷设计出改进算法.基于结构信息的目标模板比对算法,对搜索敏感度和比对准确度等方面有所提高.
关 键 词：同源建模；序列比对；结构比对
中图分类号：TP301文献标识码：A文章编号：1007-9599 （2012） 19-0000-02
1同源建模算法
同源建模算法的主要理论依据是高度保守的同源蛋白质结构,所以通过这点可以从已知蛋白质的空间结构推测出目标蛋白质的空间结构.同源建模可以概括为模板查找、目标-模板比对、建模和检查优化等四个步骤.
模板查找：要使用同源建模方法,我们至少需要知道一个已知三维结构的蛋白质作为目标序列的比对模板.我们将目标序列与从PDB（蛋白质数据库）中提取出的序列数据库进行比较来确定能否用同源建模方法来预测.这可以使用序列比较软件实现,如FastA、BLAST和PSI-BLAST等.
目标-模板比对：既然我们已经得到目标序列的比对模版,那么构造目标-模板的序列比对就是我们下一步需要得到的输入数据.而序列比对也作为研究很多其他问题的前提和基础,最终结果在很大程度上要受序列比对结果的影响,可以说它是同源建模方法的核心所在.而目前构建序列比对的方法大概有以下几类：双序列比对：指只从序列信息构造两条序列的比对算法,这类算法的代表有基于动态规划算法的局部比对算法（如Smith-Waterman）和全局比对算法（如Needleman-Wunch）、启发式算法（如BLAST、FASTA等）和基于隐马尔可夫模型（如HUMMER）等；多序列比对：是指三条以上的序列进行比对,由于同时进行多条序列比对是一个NP问题,所以目前大多数算法都是基于渐进比对的思想,对所有输入序列构造两两序列比对构建距离矩阵,之后根据距离矩阵构造序列之间的进化指导树,最后据指导树的拓扑由叶子节点到根节点逐步添加序列到比对中知道所有的序列都加入为止,由于还没有一个万能的程序,如何构造参考比对集合以及构造最终比对就成为该问题的研究热点.使用较为广泛的多序列比对软件有：T-Coffee、CLUSTALW等；基于特殊位点的比对：通过统计分析同源序列的序列构成,逐个计算每个位置上出现各种氨基酸的可能性,并给出替换分数,构造新的打分矩阵,这里与两两序列比对相同,可使用动态规划或者启发式算法来实现.构造profile可以有sequence-profile alignment（只对模板序列构造profile,并将它与目标序列进行比对）和profile-profile alignment（对模板序列和目标序列都分别构造profile,两个profile相结合得到最终比对）两种比对方式,而目前构造profile方法也是对profile alignment的研究的焦点所在,profile alignment的主要软件有profit、PSI-BLAST等.
建模：得到上面的比对结果,旋转平移模板结构,尽可能地使它们之间的位置重合,进而确定同源蛋白质的保守区（SCRs）和相应的框架（framework）结构.之后将同源体保守区的第一条序列与目标序列匹配,选取目标序列上的高相似度区域,定义为目标蛋白质的保守区SCRs；然后主链结构的建模,这主要有两种方法：刚体装配法：同源蛋白质族保守区的相应各片段,把与目标蛋白质保守区序列有最高相似度的片段选取为目标结构；加权平均法：采用加权方案,将构成基架的同源结构族的平均结构选取为目标结构.之后进行变异区（SVRs）（即非保守区）的主链建模.由于非保守区主链结构难以预测,数据库查询和系统搜索方法是目前的主要方法.最后侧链结构建模,侧链的建模方法大多是基于旋转构象库.当然除了旋转构象库的方法,还有基于微扰突变的遗传算法和基于神经网络的侧链结构预测等方法.
检查优化：对得到的原始蛋白质结构模型进行检查并且分子力学及分子动力学优化,以消除其中的不合理冲突.
2基于三维结构信息的目标-模板比对算法
搜索比对算法这一生物信息学中的经典问题,也有很多人做了相关研究,但是目前已有的算法多是根据序列相似度进行的,其结果准确性也受所选择的打分函数以及空位罚分机制所影响.profile比对虽然能够提高序列搜索的准确性,也能做到排除部分非同源序列,但它对拥有较高的结构相似度而有较低的序列相似度的同源序列搜索效果不好.由于结构域聚类数据库包含了大量的蛋白质结构信息和多维结构比对等属性,基于这些原理和结构域聚类数据库的这些属性,我们进而设计出了基于蛋白质结构信息的目标-模板搜索比对算法.
2.1算法思想概述
为便于算法思想的描述,我们作如下定义：
profile,即一个基于位置的打分矩阵S（p,a）,这个矩阵有N行21列（N表示多结构比对的长度）,这其中前20列代表20种氨基酸分别出现在位置p的得分,而最后一列代表在P位置出现插入和删除的罚分.S（p,a）可由下列公式计算得到：
其中,M：聚类中结构域的数目；n（b,p）：氨基酸b在位置p出现次数；W（p,b）：位置p出现氨基酸b的权重；Y（a,b）：传统的打分矩阵,如PAM250,而这里我们采用的是BLOSUM62进行计算.
算法流程图如下所示.我们首先从每个蛋白质结构域聚类中各抽取一个打分矩阵.当对应位置没有空位时则我们可以设置一个较高的值在profile（打分矩阵）的最后一列,而当允许空位或者是空位较多时我们可以设置一个较低的值在这个位置.如此构造出来的profile就可以描述每个结构域的特征,就可以对某个查询序列进行搜索和比对.比对匹配过程中,可以通过仿射罚分机制 来计算罚分,其中PEN：打分矩阵最后一列的值；OPEN：开始一个空位的罚分；EXT：延长空位的罚分；L：空位的数目.
2.2结果分析与性能比较
为了对结果进行分析和对算法性能进行评测,描述方便,在此我们作如下定义：
相似度：若L为结构域聚类结构比对的长度,某条序列与参考序列有n个相同位置的氨基酸残基,那么我们定义这两条序列相似度为S等于n/L.对每个结构域聚类,我们选择具有最小S值的序列作为测试序列,这里我们选取的测试集是数据库中2605条序列.我们利用上述算法,在数据库中搜索测试集,另外我们选择的比较对象有T-coffee和Smith-Waterman算法,以此作为算法性能的评测指标.结果如下表：
可以看出,算法的命中率得到明显提高,这是由于结构信息要比序列信息更保守,而我们的profile就是从纯粹的结构比对中抽取出来,所以它们也就更好的代表各个结构域的特性,也拥有了更高的搜索敏感度.
3结语
相比于经典算法,算法中加入结构信息,降低了对序列相似性的依赖度,而且结构信息要更保守于序列信息,所以比对的准确性和搜索的敏感度都有所提高,预测结果自然得到改善,尤其在低序列相似度区域.不过该方法也不是完美算法,它的局限性在于性能改善不够显著,这还需要我们继续深入的研究.