动态规划及其应用优秀课件.ppt

《动态规划及其应用优秀课件.ppt》由会员分享，可在线阅读，更多相关《动态规划及其应用优秀课件.ppt（36页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、动态规划及其应用第1页，本讲稿共36页序列比对应用举例l序列组装l进化分析l保守区发现l蛋白质结构与功能预测lcDNA的基因组定位l基因结构与功能分析第2页，本讲稿共36页序列比对模型l类型：全局比对与局部比对l需考虑的因素：替换，插入，删除l例：AGCTA CGTACATACC AGCTAGCGTA TAGCl打分系统：替换矩阵。记为：(a,b)其中a,b为我们考虑的字符集中的元素。第3页，本讲稿共36页 比对算法的目标，就是找到在给定打分系统下，得分最高的比对方式。第4页，本讲稿共36页动态规划算法（全局比对）l两序列：A=a1a2a3am B=b1b2b3bn 用Ai，Bj分别表示上述序

2、列的前i个和前j个碱基。矩阵元素S(i,j)表示Ai，Bj所有可能比对中的最高得分。则有递推公式：S(i,j)=maxS(i-1,j-1)+(ai,bj)，S(i,j-1)+(,bj)，S(i-1,j)+(ai,)第5页，本讲稿共36页l全局动态规划算法可图示如下：（所用打分矩阵为若两碱基相同，则得分为1；若不同，得分为-1）结果：A G C T A C G A G T A G G第6页，本讲稿共36页局部动态规划l递推公式改为：S(i,j)=max0，S(i-1,j-1)+(ai,bj)，S(i,j-1)+(,bj)，S(i-1,j)+(ai,)l局部动态规划图示（下页）第7页，本讲稿共36

3、页结果：A G C T A C G A G T A G G第8页，本讲稿共36页动态规划算法的改进l用动态规划方法进行序列比对，需要nm到nm2的计算时间和nm的存储空间。当序列很长时，常常无法计算。因此人们陆续提出了许多改进算法，能节省空间和时间。有兴趣的同学可参考相关文献。第9页，本讲稿共36页其他DNA打分矩阵及其对比对结果的影响l例如：l若得分大于罚分，则可得到长的，有较多插入删除的结果；反之，则得到短的，局部的比对结果。第10页，本讲稿共36页蛋白质序列比对的打分矩阵lPAM矩阵（Percent Accepted Mutation)：基于进化模型的打分矩阵。当进化过程中一条序列1%的

4、氨基酸发生了突变，定义该序列在进化的历史上走过了1个PAM单位。此时定义的转移矩阵称为1-PAM的突变矩阵。Dayhoff 等（1978）从 71个蛋白家族中的1300条近相关（closely related）序列出发（其中任何两对序列之间氨基酸残基差异不大于15%），通过构造进化树对序列进行联配，得到氨基酸对之间的联合概率分布。在此基础上得到了1-PAM的突变矩阵。第11页，本讲稿共36页 A R N D C Q E G H I L K M F P S T W Y V A R N D C Q E G H I L K M F P S T W Y V A 9890 5 5 6 12 9 11 1

5、2 5 2 5 6 9 2 10 29 14 1 2 17 A 9890 5 5 6 12 9 11 12 5 2 5 6 9 2 10 29 14 1 2 17 R 4 9907 5 2 2 16 4 3 8 1 2 30 2 0 3 5 5 4 3 2 R 4 9907 5 2 2 16 4 3 8 1 2 30 2 0 3 5 5 4 3 2 N 3 4 9888 18 2 8 5 6 13 1 1 10 1 1 2 13 8 1 3 1 N 3 4 9888 18 2 8 5 6 13 1 1 10 1 1 2 13 8 1 3 1 D 4 2 21 9905 0 7 28 5 6 0

6、 0 5 0 0 3 7 5 0 1 0 D 4 2 21 9905 0 7 28 5 6 0 0 5 0 0 3 7 5 0 1 0 C 3 1 1 0 9946 0 0 1 1 1 1 0 1 1 0 3 1 1 1 2 C 3 1 1 0 9946 0 0 1 1 1 1 0 1 1 0 3 1 1 1 2 Q 4 11 7 5 1 9856 18 2 14 1 3 14 6 1 4 5 5 1 1 2 Q 4 11 7 5 1 9856 18 2 14 1 3 14 6 1 4 5 5 1 1 2 E 8 5 6 30 0 28 9890 2 7 1 1 15 3 0 4 7 5 1

7、1 3 E 8 5 6 30 0 28 9890 2 7 1 1 15 3 0 4 7 5 1 1 3 G 11 4 9 7 2 4 3 9952 3 0 1 3 1 0 2 10 2 2 1 1 G 11 4 9 7 2 4 3 9952 3 0 1 3 1 0 2 10 2 2 1 1 H 1 4 7 3 1 9 3 1 9895 1 1 3 2 2 1 2 2 1 9 1 H 1 4 7 3 1 9 3 1 9895 1 1 3 2 2 1 2 2 1 9 1 I 2 1 2 0 2 2 1 0 2 9878 22 2 26 7 1 1 5 2 2 42 I 2 1 2 0 2 2 1

8、0 2 9878 22 2 26 7 1 1 5 2 2 42 L 5 4 2 0 3 8 2 1 3 35 9919 3 48 22 4 3 4 5 5 19 L 5 4 2 0 3 8 2 1 3 35 9919 3 48 22 4 3 4 5 5 19 K 5 33 13 5 0 22 15 2 8 2 2 9883 5 1 4 6 9 1 2 2 K 5 33 13 5 0 22 15 2 8 2 2 9883 5 1 4 6 9 1 2 2 M 3 1 1 0 2 4 1 0 2 10 12 2 9859 5 0 2 3 1 1 4 M 3 1 1 0 2 4 1 0 2 10 12

9、 2 9859 5 0 2 3 1 1 4 F 1 0 1 0 3 1 0 0 4 5 10 0 9 9923 0 1 1 10 28 3 F 1 0 1 0 3 1 0 0 4 5 10 0 9 9923 0 1 1 10 28 3 P 6 2 2 2 0 5 3 1 2 1 2 3 0 1 9943 6 5 0 1 2 P 6 2 2 2 0 5 3 1 2 1 2 3 0 1 9943 6 5 0 1 2 S 23 5 17 8 9 9 7 8 6 1 2 7 4 1 8 9862 32 2 4 2 S 23 5 17 8 9 9 7 8 6 1 2 7 4 1 8 9862 32 2

10、4 2 T 11 5 11 6 4 8 5 2 7 6 2 9 7 2 7 33 9879 1 2 12 T 11 5 11 6 4 8 5 2 7 6 2 9 7 2 7 33 9879 1 2 12 W 0 1 0 0 1 1 0 0 1 0 1 0 1 3 0 0 0 9956 4 0 W 0 1 0 0 1 1 0 0 1 0 1 0 1 3 0 0 0 9956 4 0 Y 1 2 2 1 3 1 1 0 13 1 2 1 2 22 1 2 1 10 9924 2 Y 1 2 2 1 3 1 1 0 13 1 2 1 2 22 1 2 1 10 9924 2 V 15 2 1 0 8

11、 3 4 1 2 51 14 3 12 5 2 3 14 1 4 9884V 15 2 1 0 8 3 4 1 2 51 14 3 12 5 2 3 14 1 4 9884 1-PAM mutation matrix (all values multiplied by 10000)第12页，本讲稿共36页l表中各列满足 l若fi（i=120）表示20种氨基酸在自然界中的分布，该矩阵还满足 第13页，本讲稿共36页l由于fi 是自然界中氨基酸经过长期进化后形成的一种稳定分布，因此满足关系 l也就是说，可以通过对1-PAM突变矩阵外推得到n-PAM的突变矩阵，用来表示相距n PAM进化单位的蛋白质

12、之间氨基酸残基的突变概率。即 第14页，本讲稿共36页 A R N D C Q E G H I L K M F P S T W Y V A R N D C Q E G H I L K M F P S T W Y V A 1350 677 733 733 884 748 781 884 647 649 597 714 671 461 834 1006 899 342 468 803 A 1350 677 733 733 884 748 781 884 647 649 597 714 671 461 834 1006 899 342 468 803 R 460 1583 568 493 323 7

13、51 589 424 616 304 320 995 361 253 429 512 507 366 351 337 R 460 1583 568 493 323 751 589 424 616 304 320 995 361 253 429 512 507 366 351 337 N 425 485 1092 747 299 534 563 496 601 239 228 552 275 225 366 558 507 197 326 271 N 425 485 1092 747 299 534 563 496 601 239 228 552 275 225 366 558 507 197

14、326 271 D 501 496 881 1593 260 666 1007 549 591 221 213 604 268 188 453 597 536 164 284 273 D 501 496 881 1593 260 666 1007 549 591 221 213 604 268 188 453 597 536 164 284 273 C 212 114 124 91 2660 107 94 119 138 145 134 100 153 157 93 193 166 149 169 187 C 212 114 124 91 2660 107 94 119 138 145 134

15、 100 153 157 93 193 166 149 169 187 Q 359 530 442 468 215 705 558 300 496 243 261 538 303 208 359 390 379 201 253 264 Q 359 530 442 468 215 705 558 300 496 243 261 538 303 208 359 390 379 201 253 264 E 580 645 722 1095 293 863 1334 483 635 315 305 768 370 237 525 614 572 215 312 376 E 580 645 722 10

16、95 293 863 1334 483 635 315 305 768 370 237 525 614 572 215 312 376 G 827 583 801 752 466 585 608 3387 530 264 264 567 332 224 512 799 569 291 292 346 G 827 583 801 752 466 585 608 3387 530 264 264 567 332 224 512 799 569 291 292 346 H 194 271 310 259 173 309 256 170 946 143 153 267 175 231 182 225

17、221 194 387 149 H 194 271 310 259 173 309 256 170 946 143 153 267 175 231 182 225 221 194 387 149 I 480 330 304 239 446 375 314 208 353 1460 1094 354 1027 726 320 379 510 381 489 1185 I 480 330 304 239 446 375 314 208 353 1460 1094 354 1027 726 320 379 510 381 489 1185 L 717 566 473 374 673 653 492

18、339 612 1779 2390 576 1798 1501 561 575 707 793 942 1443 L 717 566 473 374 673 653 492 339 612 1779 2390 576 1798 1501 561 575 707 793 942 1443 K 535 1097 713 662 311 840 774 454 667 358 359 1240 425 276 510 600 605 264 360 394 K 535 1097 713 662 311 840 774 454 667 358 359 1240 425 276 510 600 605

19、264 360 394 M 195 154 138 114 185 183 144 103 170 403 435 165 608 326 130 166 198 181 217 330 M 195 154 138 114 185 183 144 103 170 403 435 165 608 326 130 166 198 181 217 330 F 239 193 202 143 340 224 165 124 399 510 649 191 583 2041 171 213 246 937 1312 419 F 239 193 202 143 340 224 165 124 399 51

20、0 649 191 583 2041 171 213 246 937 1312 419 P 484 367 366 385 225 434 410 318 353 251 271 396 259 191 2614 495 467 144 222 299 P 484 367 366 385 225 434 410 318 353 251 271 396 259 191 2614 495 467 144 222 299 S 774 580 741 671 619 625 636 657 578 394 368 616 439 315 656 997 844 285 393 475 S 774 58

21、0 741 671 619 625 636 657 578 394 368 616 439 315 656 997 844 285 393 475 T 707 587 687 616 544 621 605 478 580 542 462 635 535 372 632 862 1101 274 397 622 T 707 587 687 616 544 621 605 478 580 542 462 635 535 372 632 862 1101 274 397 622 W 57 90 57 40 103 70 48 52 108 86 110 59 104 301 41 62 58 33

22、98 336 72 W 57 90 57 40 103 70 48 52 108 86 110 59 104 301 41 62 58 3398 336 72 Y 195 215 235 173 293 220 175 130 539 276 327 200 311 1054 160 213 211 843 1955 253 Y 195 215 235 173 293 220 175 130 539 276 327 200 311 1054 160 213 211 843 1955 253 V 708 437 413 352 689 486 446 326 440 1415 1060 464

23、1004 712 454 545 698 382 535 1501 V 708 437 413 352 689 486 446 326 440 1415 1060 464 1004 712 454 545 698 382 535 1501 250-PAM mutation matrix (all values multiplied by 10000)第15页，本讲稿共36页l对250-PAM突变矩阵，有：即经过250个PAM单位进化后的蛋白质分子，与它的祖先相比较，大约只有20%左右的氨基酸残基保持不变。第16页，本讲稿共36页l当我们通过动态规划对两个序列进行联配时，用到PAM突变矩阵的另一

24、种形式，PAM打分矩阵，其中PAM-1打分矩阵定义为：PAM-250打分矩阵定义为：第17页，本讲稿共36页C 17 C 17 S -19 12 S -19 12 T -22 -13 12 T -22 -13 12 P -33 -19 P -33 -19 20 13 20 13 A -18 -14 -18 -19 11 A -18 -14 -18 -19 11 G -25 -19 -25 -25 -18 11 G -25 -19 -25 -25 -18 11 N -24 -16 -18 -24 -22 -19 13 N -24 -16 -18 -24 -22 -19 13 D -32 -19

25、-20 -23 -21 -21 -14 13 D -32 -19 -20 -23 -21 -21 -14 13 E -35 -19 -21 -22 -19 -24 -20 -13 12 E -35 -19 -21 -22 -19 -24 -20 -13 12 Q -29 -18 -19 -20 -19 -23 -17 -19 -13 14 Q -29 -18 -19 -20 -19 -23 -17 -19 -13 14 H -22 -20 -20 -23 -22 -24 -15 -19 -19 -14 16 H -22 -20 -20 -23 -22 -24 -15 -19 -19 -14 1

26、6 R -24 -20 -21 -23 -22 -22 -20 -24 -21 -15 -18 13 R -24 -20 -21 -23 -22 -22 -20 -24 -21 -15 -18 13 K -33 -20 -18 -22 -21 -24 -17 -20 -16 -14 -19 K -33 -20 -18 -22 -21 -24 -17 -20 -16 -14 -19 13 12 13 12 M -22 -22 -19 -31 -19 -28 -25 -33 -24 -18 -21 -24 M -22 -22 -19 -31 -19 -28 -25 -33 -24 -18 -21

27、-24 21 16 21 16 I -26 -26 -20 -28 -25 -35 -26 -34 -27 -26 -25 -27 -24 I -26 -26 -20 -28 -25 -35 -26 -34 -27 -26 -25 -27 -24 13 12 13 12 L -25 -26 -24 -24 -22 -31 -28 -35 -27 -21 -24 -24 -24 -13 -14 10 L -25 -26 -24 -24 -22 -31 -28 -35 -27 -21 -24 -24 -24 -13 -14 10 V -19 -24 -17 -25 -17 -30 -27 -34

28、-23 -24 -27 -25 -24 -18 -11 -17 12 V -19 -24 -17 -25 -17 -30 -27 -34 -23 -24 -27 -25 -24 -18 -11 -17 12 F -22 -28 -25 -30 -25 -32 -27 -33 -33 -26 -20 -31 -30 -17 -19 -16 F -22 -28 -25 -30 -25 -32 -27 -33 -33 -26 -20 -31 -30 -17 -19 -16 22 14 22 14 Y -21 -22 -25 -27 -26 -30 -22 -26 -27 -24 -14 -23 -2

29、5 -23 -24 -22 -23 -12 15 Y -21 -22 -25 -27 -26 -30 -22 -26 -27 -24 -14 -23 -25 -23 -24 -22 -23 -12 15 W -22 -25 -29 -32 -29 -27 -28 -38 W -22 -25 -29 -32 -29 -27 -28 -38 30 -24 -23 -22 -31 -23 -25 -23 -29 -16 -15 1930 -24 -23 -22 -31 -23 -25 -23 -29 -16 -15 19 C S T P A G N D E Q H R K M I L V F Y W

30、 C S T P A G N D E Q H R K M I L V F Y W PAM-1 scoring matrix（经过四舍五入）（经过四舍五入）第18页，本讲稿共36页lPAM-250scoringmatrix（经过四舍五入）（经过四舍五入）C 12 C 12 S 0 2 S 0 2 T -2 1 3 T -2 1 3 P -3 1 0 6P -3 1 0 6A -2 1 1 1 2 A -2 1 1 1 2 G -3 1 0 -1 1 5G -3 1 0 -1 1 5N -4 1 0 -1 0 0 2N -4 1 0 -1 0 0 2D -5 0 0 -1 0 1 2 4D -5

31、0 0 -1 0 1 2 4E -5 0 0 -1 0 0 1 3 4E -5 0 0 -1 0 0 1 3 4Q -5 -1 -1 0 0 -1 1 2 2 4Q -5 -1 -1 0 0 -1 1 2 2 4H -3 -1 -1 0 -1 -2 2 1 1 3 6H -3 -1 -1 0 -1 -2 2 1 1 3 6R -4 0 -1 0 -2 -3 0 -1 -1 1 2 6R -4 0 -1 0 -2 -3 0 -1 -1 1 2 6K -5 0 0 -1 -1 -2 1 0 0 1 0 3 5K -5 0 0 -1 -1 -2 1 0 0 1 0 3 5M -5 -2 -1 -2

32、-1 -3 -2 -3 -2 -1 -2 0 0 6M -5 -2 -1 -2 -1 -3 -2 -3 -2 -1 -2 0 0 6I -2 -1 0 -2 -1 -3 -2 -2 -2 -2 -2 -2 -2 2 5I -2 -1 0 -2 -1 -3 -2 -2 -2 -2 -2 -2 -2 2 5L -6 -3 -2 -3 -2 -4 -3 -4 -3 -2 -2 -3 -3 4 2 6L -6 -3 -2 -3 -2 -4 -3 -4 -3 -2 -2 -3 -3 4 2 6V -2 -1 0 -1 0 -1 -2 -2 -2 -2 -2 -2 -2 2 4 2 4V -2 -1 0

33、-1 0 -1 -2 -2 -2 -2 -2 -2 -2 2 4 2 4F -4 -3 -3 -5 -4 -5 -4 -6 -5 -5 -2 -4 -5 0 1 2 -1 9F -4 -3 -3 -5 -4 -5 -4 -6 -5 -5 -2 -4 -5 0 1 2 -1 9Y 0 -3 -3 -5 -3 -5 -2 -4 -4 -4 0 -4 -4 -2 -1 -1 -2 7 10Y 0 -3 -3 -5 -3 -5 -2 -4 -4 -4 0 -4 -4 -2 -1 -1 -2 7 10W -8 -2 -5 -6 -6 -7 -4 -7 -7 -5 -3 2 -3 -4 -5 -2 -6

34、0 0 17W -8 -2 -5 -6 -6 -7 -4 -7 -7 -5 -3 2 -3 -4 -5 -2 -6 0 0 17 C S T P A G N D E Q H R K M I L V F Y W C S T P A G N D E Q H R K M I L V F Y W第19页，本讲稿共36页BLOSUM打分矩阵 lBLOSUM矩阵建立在BLOCKS数据库的基础上。这个数据库由很多序列块（block）组成，一个block包含了对SWISSPROT库中蛋白序列进行多序列联配（multiple alignment）得到的一组氨基酸序列片段。这些序列具有很高的相似性，把它们截断为长

35、度相同，中间没有插入或删除空位的一组，就称为一个block。通过对这个数据库中联配氨基酸残基出现频率的统计，生成了BLOSUM矩阵。第20页，本讲稿共36页l下表为下表为BLOCKSv.9数据库中某一个块的数数据库中某一个块的数据结构片段，其中包括三个类（据结构片段，其中包括三个类（cluster）。）。类中的每一条序列都能在同一类中至少找类中的每一条序列都能在同一类中至少找到另一条序列，两条序列之间到另一条序列，两条序列之间80%以上的以上的氨基酸残基是相同的。氨基酸残基是相同的。FA9_BOVIN(6)LEEFVRGNLERECKEEKCSFEEAREVFENTEKTTEFWKQY 29F

36、A9_BOVIN(6)LEEFVRGNLERECKEEKCSFEEAREVFENTEKTTEFWKQY 29 FA9_CANFA(45)LEEFVRGNLERECIEEKCSFEEAREVFENTEKTTEFWKQY 29 FA9_CANFA(45)LEEFVRGNLERECIEEKCSFEEAREVFENTEKTTEFWKQY 29 FA9_HUMAN(52)LEEFVQGNLERECMEEKCSFEEAREVFENTERTTEFWKQY 30 FA9_HUMAN(52)LEEFVQGNLERECMEEKCSFEEAREVFENTERTTEFWKQY 30 MGP_BOVIN(56)ERIR

37、ELNKPQYELNREACDDFKLCERYAMVYGYNAAYDRY 70 MGP_BOVIN(56)ERIRELNKPQYELNREACDDFKLCERYAMVYGYNAAYDRY 70 MGP_HUMAN(56)ERIRERSKPVHELNREACDDYRLCERYAMVYGYNAAYNRY 73 MGP_HUMAN(56)ERIRERSKPVHELNREACDDYRLCERYAMVYGYNAAYNRY 73 MGP_MOUSE(56)KRVQERNKPAYEINREACDDYKLCERYAMVYGYNAAYNRY 65 MGP_MOUSE(56)KRVQERNKPAYEINREACD

38、DYKLCERYAMVYGYNAAYNRY 65 MGP_RAT(56)ERVRELNKPAQEINREACDDYKLCERYALIYGYNAAYNRY 71 MGP_RAT(56)ERVRELNKPAQEINREACDDYKLCERYALIYGYNAAYNRY 71OSTC_BOVIN(57)LGAPAPYPDPLEPKREVCELNPDCDELADHIGFQEAYRRF 33OSTC_BOVIN(57)LGAPAPYPDPLEPKREVCELNPDCDELADHIGFQEAYRRF 33OSTC_FELCA(6)LGAPAPYPDPLEPKREICELNPDCDELADHIGFQDAYRR

39、F 34OSTC_FELCA(6)LGAPAPYPDPLEPKREICELNPDCDELADHIGFQDAYRRF 34OSTC_HUMAN(57)LGAPVPYPDPLEPRREVCELNPDCDELADHIGFQEAYRRF 34OSTC_HUMAN(57)LGAPVPYPDPLEPRREVCELNPDCDELADHIGFQEAYRRF 34OSTC_MACFA(6)LGAPAPYPDPLEPKREVCELNPDCDELADHIGFQEAYRRF 33OSTC_MACFA(6)LGAPAPYPDPLEPKREVCELNPDCDELADHIGFQEAYRRF 33OSTC_RABIT(6)Q

40、GAPAPYPDPLEPKREVCELNPDCDELADQVGLQDAYQRF 45OSTC_RABIT(6)QGAPAPYPDPLEPKREVCELNPDCDELADQVGLQDAYQRF 45 OSTC_RAT(55)LGAPAPYPDPLEPHREVCELNPNCDELADHIGFQDAYKRI 46 OSTC_RAT(55)LGAPAPYPDPLEPHREVCELNPNCDELADHIGFQDAYKRI 46第21页，本讲稿共36页l一个类被作为一条序列处理，因此如果一个类中包含n条序列，那么其中每一个氨基酸残基出现的频率被乘以权重因子1/n。对BLOCKS 数据库进行统计，得到氨基酸

41、对之间的联合概率分布P(i,j)，BLOSUM矩阵定义为 其中C为常数，在不同的BLOSUM矩阵（BLOSUM62，BLOSUM80等）中，C取不同的值（1/2，1/3）。第22页，本讲稿共36页l按照62%的标准对BLOCKS 数据库进行聚类（即类中的每一条序列都能在同一类中至少找到另一条序列，两条序列之间62%以上的氨基酸残基是相同的），得到BLOSUM62矩阵，按照70%的标准对BLOCKS 数据库进行聚类，得到BLOSUM70矩阵。第23页，本讲稿共36页两种打分矩阵的比较lPAM矩阵基于进化的突变模型，且是从进化距离近的数据外推到远的。BLOSUM矩阵基于蛋白家族中的保守区段，不考虑

42、进化距离远近。lPAM矩阵计算了相关序列中的所有位点，而BLOSUM矩阵只计算了一些保守区段中的位点。第24页，本讲稿共36页比对得分的统计检验l这种统计检验主要用于局部比对，因为在局部比对中我们需要判断哪些结果是真正有意义的。l在局部比对中，通常能比上的只占参加比对序列总数的一小部分。因此从整体上说，可把比对过程视为反复进行大量小片段间的比对。由于随机序列之间的比对结果服从正态分布，故可用极值分布来对某一具体结果进行检验。第25页，本讲稿共36页l极值分布极值分布：l分布函数分布函数：l故有：故有：第26页，本讲稿共36页常用比对软件介绍lFASTA计算步骤：1查找查询序列和数据库序列之间长

43、度大于k（氨基酸 1-3，核酸1-6）的精确匹配片段；2.把顺序相同，互相间距离小于给定值的匹配片段连成没有洞（gap)的区间；3.用打分矩阵对其中匹配数和匹配密度最高的区间重新打分，选出其中得分最高的区间；4.通过“gap”把得分最高的区间连接起来，加上它们的匹配分数，并减去加入“gap”带来的罚分，记录下分值最高的连接；5.用动态规划重新处理上述有“gap”的联配。第27页，本讲稿共36页lBLAST计算步骤：1.屏蔽序列中低复杂性区域；2.对“字”（氨基酸：3-tup，核酸：11-tup）在数据库中每一条目的位置建立索引表；3.对查询序列建立字集，对其中每一个字建立它的邻域（即虽然不同，

44、但比对分值大于给定阈值的字，蛋白的每个字大约有50个近邻）；4.在数据库中搜索与查询序列字集邻域中相同的字；第28页，本讲稿共36页5.以找到的字为种子，向两端延伸，直到累计得分开始下降。这样就得到了匹配片段；6.对找到的匹配片段进行统计检验；7.对检验显著的片段重做动态规划的局部比对（没有gap）。8.在BLAST2中，不是对每个匹配片段做动态规划比对，而是把数据库每条序列中的匹配片段连起来做有gap的局部比对。这样有可能得到更长的匹配片段。第29页，本讲稿共36页动态规划算法的其它应用l动态规划算法实际是一种有效的穷举法，即把一切可能值都算出来，然后挑其中最大的。其巧妙之处在于建立了递归算

45、法，每一步都是从前一步的结果出发，从而大大减少了所需计算量，使穷举法成为可行。这种思想也可用在其他生物信息学问题上。第30页，本讲稿共36页动态规划算法的其它应用l例例1.核酸序列的字典模型核酸序列的字典模型已知观测序列已知观测序列S=(s1 s2.sn)，si(A,C,G,T)，给定模，给定模型型其中其中wi称为单词，观测序列是由这些单词生成的，称为单词，观测序列是由这些单词生成的，pwi是单词出现的概率，满足是单词出现的概率，满足求求P(S|M)第31页，本讲稿共36页l解：因为即求序列S在模型M下的概率，需要穷举S在模型M下的所有可能划分方式。定义变量Z(1,i)，它表示观测序列S中从1

46、到i的片段s1 s2.si在模型M下的概率，则得到递归关系 其中(i,l)表示序列S中从i-l+1到i，长度为l的子字串。如果(i,l)为模型中的单词，则p(i,l)等于该单词的概率pw，否则为0。第32页，本讲稿共36页l例2模体的权重矩阵描述模型 已知观测序列S=(s1 s2.sn)，si(A,C,G,T)，给定模型其中q0为噪声出现的概率，qi,i=1,2,.,6为六个模体出现的概率，满足 p(bk|0),bk(A,C,G,T)是bk作为噪声时出现的概率，满足 第33页，本讲稿共36页lp(bk|i,j),bk(A,C,G,T)是bk在模体i中位置j出现的概率，满足 求P(S|M)。l解

47、：同样定义变量Z(1,i)，在权重矩阵模型下，递归关系关系为 第34页，本讲稿共36页多序列比对l目的：找出一组序列中的保守片段，以便进行结构、功能、进化方面的分析。l可以直接把动态规划的算法推广到多个序列，但由于速度限制，只能用于3个，且不能很长。l近似算法：累进算法迭代算法从顺序的局部保守序列出发概率模型和统计方法第35页，本讲稿共36页常用程序举例：CLUSTALWl主要步骤：1.对所有序列作两两比对；2.根据比对得分构建系统树；3.按照系统树的关系把序列逐一加入。l累进比对的缺点：启始一对序列中的排列错误会随序列增加扩展得越来越多，当序列亲缘关系远时，这一问题更加突出。第36页，本讲稿共36页