《blast原理及过程word版本》由会员分享，可在线阅读，更多相关《blast原理及过程word版本（51页珍藏版）》请在金锄头文库上搜索。
1、序列比对,Sequence Alignment,杨秋红 中国农业科学院硕19 ,outline,简单介绍 全局比对中的动态规划 局部比对中的动态规划 常用打分矩阵 空位罚分 Blast算法,outline,简单介绍 全局比对中的动态规划 局部比对中的动态规划 常用打分矩阵 空位罚分 Blast算法,介绍,序列比较的根本任务是： 发现序列之间的相似性 辨别序列之间的差异 目的： 相似序列 相似的结构，相似的功能 判别序列之间的同源性 推测序列之间的进化关系,例一:s: SSENTIALSOFSEQUENCEANALYSISt: SSENTIALSOFSEQUENCEANALYSIS,点阵图,例二
2、s: ESSENTIALSOFSEQUENCEANALYSISt: ESSENTIAL-ANALYSIS,outline,全局比对中的动态规划 局部比对中的动态规划 常用打分矩阵 空位罚分 Blast算法,双序列比对,全局比对 L G P S S K Q T G K G S - S R I W D N | | | | | | | L N - I T K S A G K G A I M R L G D A 局部比对 T G K G | | | A G K G ,以碱基序列为例,s:AGCACACA AG CACACA t:A CACACTA or ACACACT A cost : 2 cost
3、: 4 显然左边的比对效果好一点，它的代价小，出现这种变化的可能性大 如何衡量：Weight（Score） match:w(a,a)=1 mismatch: w(a,b)= -2 for ab gap :w(a,-)=w (-, b) = -5,分阶段 求子最优解,动态规划,9,13,12,8,6,3,4,2,17,G A A T C T G C,CAATTGA,C A A T T G AG A A T C T G C,Match：8 Mismatch：-5 Gap：-3,全局比对 Needleman Wunsch算法,G A A T C T G C,CAATTGA,C A A T T G A
4、G A A T C T G C,Match：8 Mismatch：-5 Gap：-3,G A A T C T G C,CAATTGA,C A A T T G AG A A T C T G C,Match：8 Mismatch：-5 Gap：-3,G A A T C T G C,CAATTGA,C A A T T G AG A A T C T G C,Match：8 Mismatch：-5 Gap：-3,G A A T C T G C,CAATTGA,C A A T T G AG A A T C T G C,Match：8 Mismatch：-5 Gap：-3,G A A T C T G C,C
5、AATTGA,C A A T - T G AG A A T C T G C-5 +8 +8 +8 -3 +8 +8 -5 = 27,Match：8 Mismatch：-5 Gap：-3,Global Alignment vs. Local Alignment,全局比对 局部比对（功能域，内含子）,outline,简单介绍 全局比对中的动态规划 局部比对中的动态规划 常用打分矩阵 空位罚分 Blast算法,局部比对（Smith Waterman）,0,local alignment,C G G A T C A T,CTTAACT,Match: 8 Mismatch: -5 Gap symbol:
6、 -3,local alignment,C G G A T C A T,CTTAACT,Match: 8 Mismatch: -5 Gap symbol: -3,local alignment,C G G A T C A T,CTTAACT,Match: 8 Mismatch: -5 Gap symbol: -3,The best score,C G G A T C A T,CTTAACT,The best score,A C - TA T C A T 8-3+8-3+8 = 18,outline,简单介绍 全局比对中的动态规划 局部比对中的动态规划 常用打分矩阵 空位罚分 Blast算法,打
7、分矩阵,PAM BLOSUM,PAM,BLOSUM,BLOSUM（1992，Steven Henikoff &Jorja Henikoff） 首先寻找氨基酸模式，即有意义的一段氨基酸片断（如一个结构域及其相邻的两小段氨基酸序列） ，分别比较相同的氨基酸模式之间氨基酸的保守性（某种氨基酸对另一种氨基酸的取代数据），然后，以所有 60保守性的氨基酸模式之间的比较数据为根据，产生BLOSUM60；以所有80保守性的氨基酸模式之间的比 较数据为根据，产生BLOSUM80。,PAM and BLOSUM Matrices,PAM-N and BLOSUM-N BLOSUM80 BLOSUM62 BLOS
8、UM45 PAM1 PAM120 PAM250 高相似度低相似度,PAM100: 50% identity PAM250: 20% identity Most widely used: PAM250 and BLOSUM62,outline,简单介绍 全局比对中的动态规划 局部比对中的动态规划 常用打分矩阵 空位罚分 Blast算法,空位罚分,AG- -CACACA ACATCACTA Gap=indel（insert AND delete），因为indel影响功能，一般给负分，也就是空位罚分 Gap分为Gap Starting和Gap Extending Gap Starting一般-10分
9、 Gap Extending一般-0.5分,outline,简单介绍 全局比对中的动态规划 局部比对中的动态规划 常用打分矩阵 空位罚分 Blast算法,BLAST（less accurate but over 50 times fasterthan Smith-Waterman algorithm）,Blast：Basic Local Alignment Search Tool 主要过程： Seeding Extending,Seeding:划分查询序列,去掉Query Sequence的低复杂度或重复区域 将Query Sequence划分成K-letter words,Word Size
10、: Protein : 3 DNA : 11 Word size大，准确度高，精确度差。,Seeding:创建序列的查询列表,Blast2是blast的一个新版本，他会把gap小于阈值A的区域连接起来，作为一个新的字串，再用blast查询，它更能节约时间，但是为了保证灵敏性，它需要降低阈值T。,Seeding:在数据库中定位种子找到Hit,由于数据库预先有建立索引，因此查询种子找到match是非常快的。可以利用如下方法： 利用hash建index 后缀树,Extending：Hit HSP(high-scoring segment pair),当Score值开始下降的时候停止延伸,Extend
11、ing：Score的统计学显著性,把score值足够大的HSPs列出来 HPSs Score的显著性评价（E值）： E value:随机情况下，获得当前或者比当前更高比对分数的可能比对条数 E=10就意味着会有10个随机的匹配获得与当前比对相等或者更高的分数。,Extending：Score的统计学显著性,Extending：HSP的合并,Show the result,把Query Sequence和database中的每一条序列的局部比对结果展示出来 原始的blast的结果是un-gap的 Blast2是允许gap的,Psi-BLAST,Position Specific Iterative BLAST 在蛋白质数据库中循环搜索查询蛋白质，所有前一次被psi-blast发现的统计显著蛋白质序列将整合成新记分矩阵，通过多次迭代比对，直到不再发现统计显著的新蛋白质。,Frequency matrix,Score matrix,Score matrix,Psi-BLAST vs BLAST,主要参考,华中农业大学陈玲玲老师课件 北京大学生物信息学中心 高歌老师教学视频 ABC网站 降帅和亢雨笺关于blast的报告 https:/en.wikipedia.org/wiki/BLAST,Thanks！,
