blast原理及过程

序列比对SequenceAlignment杨秋红中国农业科学院硕[e-mail]简单介绍全局比对中的动态规划局部比对中的动态规划常用打分矩阵空位罚分Blast算法outline简单介绍全局比对中的动态规划局部比对中的动态规划常用打分矩阵空位罚分Blast算法介绍序列比较的根本任务是：发现序列之间的相似性辨别序列之间的差异目的：相似序列相似的结构，相似的功能判别序列之间的同源性推测序列之间的进化关系例一:s:SSENTIALSOFSEQUENCEANALYSISt:SSENTIALSOFSEQUENCEANALYSIS点阵图例二s:ESSENTIALSOFSEQUENCEANALYSISt:ESSENTIAL———————--ANALYSISoutline全局比对中的动态规划局部比对中的动态规划常用打分矩阵空位罚分Blast算法双序列比对全局比对LGPSSKQTGKGS-SRIWDN|||||||LN-ITKSAGKGAIMRLGDA局部比对–––––––TGKG––––––––|||–––––––AGKG––––––––以碱基序列为例s:AGCACAC–AAG–CACACAt:A–CACACTAorACACACT–Acost:2cost:4显然左边的比对效果好一点，它的代价小，出现这种变化的可能性大如何衡量：Weight（Score）match:w(a,a)=1mismatch:w(a,b)=-2fora≠bgap:w(a,-)=w(-,b)=-5分阶段求子最优解动态规划0-3-6-9-12-15-18-21-24-3-6-9-12-15-18-21GAATCTGCCAATTGACAATTGAGAATCTGCMatch：8Mismatch：-5Gap：-3全局比对NeedlemanWunsch算法0-3-6-9-12-15-18-21-24-3-6-6-9-12-15-18-21GAATCTGCCAATTGACAATTGAGAATCTGCMatch：8Mismatch：-5Gap：-30-3-6-9-12-15-18-21-24-3-5-8-11-14-4-7-10-13-6-830-3-6-9-12-15-9-11011852-1-4-12-14-38191613107-15-11-651614242118-18-7-921311213229-21-101-1108182927GAATCTGCCAATTGACAATTGAGAATCTGCMatch：8Mismatch：-5Gap：-30-3-6-9-12-15-18-21-24-3-5-8-11-14-4-7-10-13-6-830-3-6-9-12-15-9-11011852-1-4-12-14-38191613107-15-11-651614242118-18-7-921311213229-21-101-1108182927GAATCTGCCAATTGACAATTGAGAATCTGCMatch：8Mismatch：-5Gap：-30-3-6-9-12-15-18-21-24-3-5-8-11-14-4-7-10-13-6-830-3-6-9-12-15-9-11011852-1-4-12-14-38191613107-15-11-651614242118-18-7-921311213229-21-101-1108182927GAATCTGCCAATTGACAATTGAGAATCTGCMatch：8Mismatch：-5Gap：-30-3-6-9-12-15-18-21-24-3-5-8-11-14-4-7-10-13-6-830-3-6-9-12-15-9-11011852-1-4-12-14-38191613107-15-11-651614242118-18-7-921311213229-21-101-1108182927GAATCTGCCAATTGACAAT-TGAGAATCTGC-5+8+8+8-3+8+8-5=27Match：8Mismatch：-5Gap：-3GlobalAlignmentvs.LocalAlignment全局比对局部比对（功能域，内含子）outline简单介绍全局比对中的动态规划局部比对中的动态规划常用打分矩阵空位罚分Blast算法局部比对（SmithWaterman）djiFdjiyixs)1,(),1i(F),(1)-j，1-F(i0maxj)F(i,0localalignment000000000085200852053008531302000852110000853?000CGGATCATCTTAACTMatch:8Mismatch:-5Gapsymbol:-3localalignment0000000000852008520530085313020008521100008531310000085211808525313107053021310818CGGATCATCTTAACTMatch:8Mismatch:-5Gapsymbol:-3localalignment0000000000852008520530085313020008521100008531310000085211808525313107053021310818CGGATCATCTTAACTMatch:8Mismatch:-5Gapsymbol:-3Thebestscore0000000000852008520530085313020008521100008531310000085211808525313107053021310818CGGATCATCTTAACTThebestscoreA–C-TATCAT8-3+8-3+8=18outline简单介绍全局比对中的动态规划局部比对中的动态规划常用打分矩阵空位罚分Blast算法打分矩阵PAMBLOSUMPAMPAM（1978，MargaretDayhoff）PAM1：把只相差1%的序列(近相关蛋白)进行人工多序列比对，数出各种氨基酸变化的个数，计算概率，求出logodds=log𝑝1−𝑝值，构建PAM1矩阵。PAMn：把一个PAM看作是进化的一步，进行矩阵的自乘，比如PAM30就是（PAM1）30比如:PAM2中氨基酸N→N的概率就是P（N→？→N）常用的PAM矩阵是PAM250BLOSUMBLOSUM（1992，StevenHenikoff&JorjaHenikoff）首先寻找氨基酸模式，即有意义的一段氨基酸片断（如一个结构域及其相邻的两小段氨基酸序列），分别比较相同的氨基酸模式之间氨基酸的保守性（某种氨基酸对另一种氨基酸的取代数据），然后，以所有60％保守性的氨基酸模式之间的比较数据为根据，产生BLOSUM60；以所有80％保守性的氨基酸模式之间的比较数据为根据，产生BLOSUM80。PAMandBLOSUMMatricesPAM-NandBLOSUM-NBLOSUM80BLOSUM62BLOSUM45PAM1PAM120PAM250高相似度低相似度PAM100:50%identityPAM250:20%identityMostwidelyused:PAM250andBLOSUM62outline简单介绍全局比对中的动态规划局部比对中的动态规划常用打分矩阵空位罚分Blast算法空位罚分AG--CACACAACATCACT–AGap=indel（insertANDdelete），因为indel影响功能，一般给负分，也就是空位罚分Gap分为GapStarting和GapExtendingGapStarting一般-10分GapExtending一般-0.5分outline简单介绍全局比对中的动态规划局部比对中的动态规划常用打分矩阵空位罚分Blast算法BLAST（lessaccuratebutover50timesfasterthanSmith-Watermanalgorithm）Blast：BasicLocalAlignmentSearchTool主要过程：SeedingExtendingSeeding:划分查询序列去掉QuerySequence的低复杂度或重复区域将QuerySequence划分成K-letterwordsWordSize:Protein:3DNA:11Wordsize大，准确度高，精确度差。Seeding:创建序列的查询列表Blast2是blast的一个新版本，他会把gap小于阈值A的区域连接起来，作为一个新的字串，再用blast查询，它更能节约时间，但是为了保证灵敏性，它需要降低阈值T。Seeding:在数据库中定位种子找到Hit由于数据库预先有建立索引，因此查询种子找到match是非常快的。可以利用如下方法：利用hash建index后缀树Extending：HitHSP(high-scoringsegmentpair)当Score值开始下降的时候停止延伸Extending：Score的统计学显著性把score值足够大的HSPs列出来HPSsScore的显著性评价（E值）：Evalue:随机情况下，获得当前或者比当前更高比对分数的可能比对条数E=10就意味着会有10个随机的匹配获得与当前比对相等或者更高的分数。Extending：Score的统计学显著性Extending：HSP的合并Showtheresult把QuerySequence和database中的每一条序列的局部比对结果展示出来原始的blast的结果是un-gap的Blast2是允许gap的Psi-BLASTPositionSpecificIterativeBLAST在蛋白质数据库中循环搜索查询蛋白质，所有前一次被psi-blast发现的统计显著蛋白质序列将整合成新记分矩阵，通过多次迭代比对，直到不再发现统计显著的新蛋白质。FrequencymatrixScorematrixScorematrixPsi-BLASTvsBLAST主要参考华中农业大学陈玲玲老师课件北京大学生物信息学中心高歌老师教学视频ABC网站降帅和亢雨笺关于blast的报告