动态规划及其应用

动态规划及其应用第1页，课件共36页，创作于2023年2月序列比对应用举例序列组装进化分析保守区发现蛋白质结构与功能预测cDNA的基因组定位基因结构与功能分析第2页，课件共36页，创作于2023年2月序列比对模型类型：全局比对与局部比对需考虑的因素：替换，插入，删除例：AGCTA–CGTACATACCAGCTAGCGTA–

–TAGC打分系统：替换矩阵。记为：

σ(a,b)

其中a,b为我们考虑的字符集中的元素。第3页，课件共36页，创作于2023年2月比对算法的目标，就是找到在给定打分系统下，得分最高的比对方式。第4页，课件共36页，创作于2023年2月动态规划算法（全局比对）两序列：A=a1a2a3……am

B=b1b2b3……bn

用Ai，Bj分别表示上述序列的前i个和前j个碱基。矩阵元素S(i,j)表示Ai，Bj所有可能比对中的最高得分。则有递推公式：

S(i,j)=max{S(i-1,j-1)+σ(ai,bj)，

S(i,j-1)+σ(–,bj)，S(i-1,j)+σ(ai,–)}第5页，课件共36页，创作于2023年2月全局动态规划算法可图示如下：

（所用打分矩阵为若两碱基相同，则得分为1；若不同，得分为-1）结果：AGCTACGAG–TAGG第6页，课件共36页，创作于2023年2月局部动态规划递推公式改为：

S(i,j)=max{0，S(i-1,j-1)+σ(ai,bj)，

S(i,j-1)+σ(–,bj)，S(i-1,j)+σ(ai,–)}局部动态规划图示（下页）第7页，课件共36页，创作于2023年2月结果：AGCTACGAG–TAGG第8页，课件共36页，创作于2023年2月动态规划算法的改进用动态规划方法进行序列比对，需要nm到nm2的计算时间和nm的存储空间。当序列很长时，常常无法计算。因此人们陆续提出了许多改进算法，能节省空间和时间。有兴趣的同学可参考相关文献。第9页，课件共36页，创作于2023年2月其他DNA打分矩阵

及其对比对结果的影响例如：若得分大于罚分，则可得到长的，有较多插入删除的结果；反之，则得到短的，局部的比对结果。第10页，课件共36页，创作于2023年2月蛋白质序列比对的打分矩阵PAM矩阵（PercentAcceptedMutation)：基于进化模型的打分矩阵。当进化过程中一条序列1%的氨基酸发生了突变，定义该序列在进化的历史上走过了1个PAM单位。此时定义的转移矩阵称为1-PAM的突变矩阵。Dayhoff等（1978）从71个蛋白家族中的1300条近相关（closelyrelated）序列出发（其中任何两对序列之间氨基酸残基差异不大于15%），通过构造进化树对序列进行联配，得到氨基酸对之间的联合概率分布。在此基础上得到了1-PAM的突变矩阵。第11页，课件共36页，创作于2023年2月

ARNDCQEGHILKMFPSTWYVA989055612911125256921029141217R4990752216438123020355432N349888182856131110112138131D4221990507285600500375010C31109946001111011031112Q411751985618214131461455112E85630028989027111530475113G1149724399523013102102211H14731931989511322122191I21202210298782222671152242L542038213359919348224345519K533135022152822988351469122M3110241021012298595023114F10103100451009992301110283P62220531212301994365012S23517899786127418986232242T115116485276297273398791212W01001100101013000995640Y12213110131212221211099242V1521083412511431252314149884

1-PAMmutationmatrix(allvaluesmultipliedby10000)

第12页，课件共36页，创作于2023年2月表中各列满足

若fi（i=1～20）表示20种氨基酸在自然界中的分布，该矩阵还满足

第13页，课件共36页，创作于2023年2月由于fi是自然界中氨基酸经过长期进化后形成的一种稳定分布，因此满足关系

也就是说，可以通过对1-PAM突变矩阵外推得到n-PAM的突变矩阵，用来表示相距n–PAM进化单位的蛋白质之间氨基酸残基的突变概率。即

第14页，课件共36页，创作于2023年2月

ARNDCQEGHILKMFPSTWYVA13506777337338847487818846476495977146714618341006899342468803R4601583568493323751589424616304320995361253429512507366351337N4254851092747299534563496601239228552275225366558507197326271D50149688115932606661007549591221213604268188453597536164284273C2121141249126601079411913814513410015315793193166149169187Q359530442468215705558300496243261538303208359390379201253264E58064572210952938631334483635315305768370237525614572215312376G8275838017524665856083387530264264567332224512799569291292346H194271310259173309256170946143153267175231182225221194387149I4803303042394463753142083531460109435410277263203795103814891185L71756647337467365349233961217792390576179815015615757077939421443K53510977136623118407744546673583591240425276510600605264360394M195154138114185183144103170403435165608326130166198181217330F23919320214334022416512439951064919158320411712132469371312419P4843673663852254344103183532512713962591912614495467144222299S774580741671619625636657578394368616439315656997844285393475T7075876876165446216054785805424626355353726328621101274397622W579057401037048521088611059104301416258339833672Y19521523517329322017513053927632720031110541602132118431955253V7084374133526894864463264401415106046410047124545456983825351501250-PAMmutationmatrix(allvaluesmultipliedby10000)

第15页，课件共36页，创作于2023年2月对250-PAM突变矩阵，有：即经过250个PAM单位进化后的蛋白质分子，与它的祖先相比较，大约只有20%左右的氨基酸残基保持不变。

第16页，课件共36页，创作于2023年2月当我们通过动态规划对两个序列进行联配时，用到PAM突变矩阵的另一种形式，PAM打分矩阵，其中PAM-1打分矩阵定义为：

PAM-250打分矩阵定义为：

第17页，课件共36页，创作于2023年2月C17S-1912T-22-1312P-33-19–2013A-18-14-18-1911G-25-19-25-25-1811N-24-16-18-24-22-1913D-32-19-20-23-21-21-1413E-35-19-21-22-19-24-20-1312Q-29-18-19-20-19-23-17-19-1314H-22-20-20-23-22-24-15-19-19-1416R-24-20-21-23-22-22-20-24-21-15-1813K-33-20-18-22-21-24-17-20-16-14-19–1312M-22-22-19-31-19-28-25-33-24-18-21-24–2116I-26-26-20-28-25-35-26-34-27-26-25-27-24–1312L-25-26-24-24-22-31-28-35-27-21-24-24-24-13-1410V-19-24-17-25-17-30-27-34-23-24-27-25-24-18-11-1712F-22-28-25-30-25-32-27-33-33-26-20-31-30-17-19-16–2214Y-21-22-25-27-26-30-22-26-27-24-14-23-25-23-24-22-23-1215W-22-25-29-32-29-27-28-38–30-24-23-22-31-23-25-23-29-16-1519CSTPAGNDEQHRKMILVFYWPAM-1scoringmatrix（经过四舍五入）

第18页，课件共36页，创作于2023年2月PAM-250scoringmatrix（经过四舍五入）

C12S02T-213P-3106A-21112G-310-115N-410-1002D-500-10124E-500-100134Q-5-1-100-11224H-3-1-10-1-221136R-40-10-2-30-1-1126K-500-1-1-21001035M-5-2-1-2-1-3-2-3-2-1-2006I-2-10-2-1-3-2-2-2-2-2-2-225L-6-3-2-3-2-4-3-4-3-2-2-3-3426V-2-10-10-1-2-2-2-2-2-2-22424F-4-3-3-5-4-5-4-6-5-5-2-4-5012-19Y0-3-3-5-3-5-2-4-4-40-4-4-2-1-1-2710W-8-2-5-6-6-7-4-7-7-5-32-3-4-5-2-60017CSTPAGNDEQHRKMILVFYW第19页，课件共36页，创作于2023年2月BLOSUM打分矩阵

BLOSUM矩阵建立在BLOCKS数据库的基础上。这个数据库由很多序列块（block）组成，一个block包含了对SWISSPROT库中蛋白序列进行多序列联配（multiplealignment）得到的一组氨基酸序列片段。这些序列具有很高的相似性，把它们截断为长度相同，中间没有插入或删除空位的一组，就称为一个block。通过对这个数据库中联配氨基酸残基出现频率的统计，生成了BLOSUM矩阵。

第20页，课件共36页，创作于2023年2月下表为BLOCKSv.9数据库中某一个块的数据结构片段，其中包括三个类（cluster）。类中的每一条序列都能在同一类中至少找到另一条序列，两条序列之间80%以上的氨基酸残基是相同的。

FA9_BOVIN(6)LEEFVRGNLERECKEEKCSFEEAREVFENTEKTTEFWKQY29FA9_CANFA(45)LEEFVRGNLERECIEEKCSFEEAREVFENTEKTTEFWKQY29FA9_HUMAN(52)LEEFVQGNLERECMEEKCSFEEAREVFENTERTTEFWKQY30

MGP_BOVIN(56)ERIRELNKPQYELNREACDDFKLCERYAMVYGYNAAYDRY70MGP_HUMAN(56)ERIRERSKPVHELNREACDDYRLCERYAMVYGYNAAYNRY73MGP_MOUSE(56)KRVQERNKPAYEINREACDDYKLCERYAMVYGYNAAYNRY65MGP_RAT(56)ERVRELNKPAQEINREACDDYKLCERYALIYGYNAAYNRY71

OSTC_BOVIN(57)LGAPAPYPDPLEPKREVCELNPDCDELADHIGFQEAYRRF33OSTC_FELCA(6)LGAPAPYPDPLEPKREICELNPDCDELADHIGFQDAYRRF34OSTC_HUMAN(57)LGAPVPYPDPLEPRREVCELNPDCDELADHIGFQEAYRRF34OSTC_MACFA(6)LGAPAPYPDPLEPKREVCELNPDCDELADHIGFQEAYRRF33OSTC_RABIT(6)QGAPAPYPDPLEPKREVCELNPDCDELADQVGLQDAYQRF45OSTC_RAT(55)LGAPAPYPDPLEPHREVCELNPNCDELADHIGFQDAYKRI46第21页，课件共36页，创作于2023年2月一个类被作为一条序列处理，因此如果一个类中包含n条序列，那么其中每一个氨基酸残基出现的频率被乘以权重因子1/n。对BLOCKS数据库进行统计，得到氨基酸对之间的联合概率分布P(i,j)，BLOSUM矩阵定义为

其中C为常数，在不同的BLOSUM矩阵（BLOSUM62，BLOSUM80等）中，C取不同的值（1/2，1/3）。第22页，课件共36页，创作于2023年2月按照62%的标准对BLOCKS数据库进行聚类（即类中的每一条序列都能在同一类中至少找到另一条序列，两条序列之间62%以上的氨基酸残基是相同的），得到BLOSUM62矩阵，按照70%的标准对BLOCKS数据库进行聚类，得到BLOSUM70矩阵。第23页，课件共36页，创作于2023年2月两种打分矩阵的比较PAM矩阵基于进化的突变模型，且是从进化距离近的数据外推到远的。BLOSUM矩阵基于蛋白家族中的保守区段，不考虑进化距离远近。PAM矩阵计算了相关序列中的所有位点，而BLOSUM矩阵只计算了一些保守区段中的位点。第24页，课件共36页，创作于2023年2月比对得分的统计检验这种统计检验主要用于局部比对，因为在局部比对中我们需要判断哪些结果是真正有意义的。在局部比对中，通常能比上的只占参加比对序列总数的一小部分。因此从整体上说，可把比对过程视为反复进行大量小片段间的比对。由于随机序列之间的比对结果服从正态分布，故可用极值分布来对某一具体结果进行检验。第25页，课件共36页，创作于2023年2月极值分布：分布函数：故有：第26页，课件共36页，创作于2023年2月常用比对软件介绍FASTA计算步骤：

1．查找查询序列和数据库序列之间长度大于k（氨基酸1-3，核酸1-6）的精确匹配片段；

2.把顺序相同，互相间距离小于给定值的匹配片段连成没有洞（gap)的区间；

3.用打分矩阵对其中匹配数和匹配密度最高的区间重新打分，选出其中得分最高的区间；

4.通过“gap”把得分最高的区间连接起来，加上它们的匹配分数，并减去加入“gap”带来的罚分，记录下分值最高的连接；

5.用动态规划重新处理上述有“gap”的联配。第27页，课件共36页，创作于2023年2月BLAST计算步骤：1.屏蔽序列中低复杂性区域；2.对“字”（氨基酸：3-tup，核酸：11-tup）在数据库中每一条目的位置建立索引表；3.对查询序列建立字集，对其中每一个字建立它的邻域（即虽然不同，但比对分值大于给定阈值的字，蛋白的每个字大约有50个近邻）；4.在数据库中搜索与查询序列字集邻域中相同的字；第28页，课件共36页，创作于2023年2月5.以找到的字为种子，向两端延伸，直到累计得分开始下降。这样就得到了匹配片段；6.对找到的匹配片段进行统计检验；7.对检验显著的片段重做动态规划的局部比对（没有gap）。8.在BLAST2中，不是对每个匹配片段做动态规划比对，