序列比对与算法和软件使用课件.ppt

1、序列比对与算法和软件使用2o 第一节 双序列比对o 第二节 多序列比对o 第三节 常用序列比对软件的使用n第一节 双序列比对4o 1. 序列比对基本概念o 2. 空位罚分o 3. 双序列比对方法o 4. 记分矩阵56789(Gap Penalties)101 GTGATAGACAC | 1 GTGCATAGACAC允许空位但不罚分不允许有空位 match = 5mismatch = -41 GTG-ATAGACAC | |1 GTGCATAGACAC1 GTG-ATAGACAC | |1 GTGC-ATAGACAC? ?Score: -21Score: 5511 A T G T T A T A

2、 CT A T G T G C G T A T A Score=4参数:匹配匹配= 1非匹配非匹配= 0g= 3r = 0.1x = 3score：8 - 3.2 = 4.8Wx=g+r(x-1)Wx:空位总记分g:空位开放罚分r:空位扩展罚分x:空位长度T A T G T G C G T A T A insertion / deletionA T G T - - - T A T A CWx= 3 + 0.1*(3 -1) = 3.212o 点阵序列比较 (Dot Matrix Sequence Comparison)o 动态规划算法 (Dynamic Programming Algorith

3、m)o 词或K串方法 (Word or K-tuple Methods)13IONIZATIONIONIZATION15o自身比对n 寻找序列中的正向或反向重复序列n 蛋白质的重复结构域(domain)n 相同残基重复出现的低复杂区(Low Complexity)n RNA二级结构中的互补区域等o对两条序列的相似性作整体的估计TACTGTCAT T A C T G T T C A TSequence 1Sequence 2T A C T G - T C A T| | | | | | | | |T A C T G T T C A T插入空位插入空位17人类低脂受体(human low-densi

4、ty lipoprotein receptor)自身比对发现正向重复序列具有连续相似区域的两条DNA序列的简单点阵图正向重复1819T A C G G T A T G A C A G T A T CT A C G G T A T G A C A G T A T CT A C G G T A T G A C A G T A T CT A C G G T A T G A C A G T A T CC T A T G A C A T A C G G T A T GWindow=3 Word Size = 320ATACTACAAGACACGTACCGG C G A T G C A T T G A G

5、 T A T C A T AWindow size = 5Stringency = 3Match = 1 Mismatch = 021ATACTACAAGACACGTACCGG C G A T G C A T T G A G T A T C A T AWindow size = 5Stringency = 3Match = 1 Mismatch = 022ATACTACAAGACACGTACCGG C G A T G C A T T G A G T A T C A T AWindow size = 5Stringency = 3Match = 1 Mismatch = 023G C G A T

6、 G C A T T G A G T A T C A T AATACTACAAGACACGTACCGWindow size = 5Stringency = 3Match = 1 Mismatch = 024G C G A T G C A T T G A G T A T C A T AATACTACAAGACACGTACCG25G C G A T G C A T T G A G T A T C A T AATACTACAAGACACGTACCG（a）对人类（Homo sapiens）与黑猩猩（Pongo pygmaeus）的球蛋白基因序列进行比较的完整点阵图（b）利用滑动窗口对以上的两种球蛋白基

7、因序列进行比较的点阵图，其中窗口大小为10个核苷酸， 相似度阈值为8，即10个核苷酸中有8个相同时就打一个点ab272829o DNA Strider (Macintosh)n http:/ o Dotter (Unix/Linux, X-Windows)o COMPARE, DOTPLOT (GCG软件)o PLALIGN (FASTA)o Dotlet3031o Eg. 匹配=1,非匹配=0, 空位罚分=-1n Sequence1: CACGAn Sequence2: CGA第一个位点得分剩余序列CC+1ACGAGA-C-1CACGAGAC-1ACGACGA32Sij=maxSi-1,j-

8、1,+s(aibj),maxx1 (Si-x,j-wx),maxy 1 (Si,j-y-wy)Sij=maxSi-1,j-1,+s(aibj),maxx1 (Si-1,j-wx),maxy 1 (Si,j-1-wy)公式一的简化公式一公式二说明：Sij是序列a在位置i和序列b在位置j的分值， s(aibj)是位置i 和j上比对分值，wx是在序列a 中长度为x的间隔罚分，wy是序列b中长度为y的间隔罚分33ACTTCGACTAG匹配3错配-1空位-234ACTTCG0ACTAG匹配3错配-1空位-235ACTTCG0-2ACTAG匹配3错配-1空位-236ACTTCG0-2-4-6-8-10-1

9、2ACTAG匹配3错配-1空位-237ACTTCG0-2-4-6-8-10-12A-2CTAG匹配3错配-1空位-238ACTTCG0-2-4-6-8-10-12A-2C-4T-6A-8G-10?S(2,2)-2+(-2)-2+(-2)0+3匹配3错配-1空位-239ACTTCG0-2-4-6-8-10-12A-23C-4T-6A-8G-10?S(2,3)-4+(-2) 3+(-2)-2+(-1)匹配3错配-1空位-240ACTTCG0-2-4-6-8-10-12A-231C-4T-6A-8G-10匹配3错配-1空位-241ACTTCG0-2-4-6-8-10-12A-231-1-3-5-7C

10、-416420-2T-6-14?A-8-3 2G-10-50S(4,4) 4+(-2) 4+(-2) 6+3匹配3错配-1空位-242ACTTCG0-2-4-6-8-10-12A-231-1-3-5-7C-416420-2T-6-149A-8-3 2G-10-50匹配3错配-1空位-2ACTTCG0-2-4-6-8-10-12A-231-1-3-5-7C-416420-2T-6-149753A-8-3 27864G-10-505679GGT-CATTCCAA回回 溯溯ACTTCG0-2-4-6-8-10-12A-231-1-3-5-7C-416420-2T-6-149753A-8-3 2786

11、4G-10-505679GGT-CATTCCAAACTTCG0-2-4-6-8-10-12A-231-1-3-5-7C-416420-2T-6-149753A-8-3 27864G-10-505679GGTAC-TTCCAA461.ACTTCGAC-TAG2.ACTTCGACT-AG3.ACTTCGACTA-G哪一个是最优比对哪一个是最优比对(optimal alignment)呢呢?记分矩阵47oDNA计分矩阵o蛋白质计分矩阵o广泛使用的两种矩阵n PAM n BLOSUMo空位罚分48actaccagttcatttgatacttctcaaataccattaccgtgttaactgaaagg

12、acttaaagactSequence 1Sequence 2AGCTA1000G0100C0010T0001匹配: 1错配: 0分值：549CTAG嘧啶嘌呤 表示转换(transition)，表示颠换(transversions)转换比颠换更容易发生AGTCA0.99G0.0060.99T0.0020.0020.99C0.0020.0020.0060.99转换速率是颠换3倍时的模型PTHPLASKTQILPEDLASEDLTIPTHPLAGERAIGLARLAEEDFGMSequence 1Sequence 2记分矩阵T:G= -2 T:T = 5Score= 48 CSTPAGND.C 9

13、S-1 4T-1 1 5P-3-1-1 7A 0 1 0-1 4G-3 0-2-2 0 6N-3 1 0-2-2 0 5D-3 0-1-1-2-1 1 6 . CSTPAGND.C 9S-1 4T-1 1 5P-3-1-1 7A 0 1 0-1 4G-3 0-2-2 0 6N-3 1 0-2-2 0 5D-3 0-1-1-2-1 1 6 .52 A R N D C Q E G H I L K M F P S T W Y V B ZA 2 -2 0 0 -2 0 0 1 -1 -1 -2 -1 -1 -3 1 1 1 -6 -3 0 2 1 R -2 6 0 -1 -4 1 -1 -3 2 -2

14、 -3 3 0 -4 0 0 -1 2 -4 -2 1 2 N 0 0 2 2 -4 1 1 0 2 -2 -3 1 -2 -3 0 1 0 -4 -2 -2 4 3 D 0 -1 2 4 -5 2 3 1 1 -2 -4 0 -3 -6 -1 0 0 -7 -4 -2 5 4 C -2 -4 -4 -5 12 -5 -5 -3 -3 -2 -6 -5 -5 -4 -3 0 -2 -8 0 -2 -3 -4 Q 0 1 1 2 -5 4 2 -1 3 -2 -2 1 -1 -5 0 -1 -1 -5 -4 -2 3 5 E 0 -1 1 3 -5 2 4 0 1 -2 -3 0 -2 -5 -

15、1 0 0 -7 -4 -2 4 5 G 1 -3 0 1 -3 -1 0 5 -2 -3 -4 -2 -3 -5 0 1 0 -7 -5 -1 2 1 H -1 2 2 1 -3 3 1 -2 6 -2 -2 0 -2 -2 0 -1 -1 -3 0 -2 3 3 I -1 -2 -2 -2 -2 -2 -2 -3 -2 5 2 -2 2 1 -2 -1 0 -5 -1 4 -1 -1 L -2 -3 -3 -4 -6 -2 -3 -4 -2 2 6 -3 4 2 -3 -3 -2 -2 -1 2 -2 -1 K -1 3 1 0 -5 1 0 -2 0 -2 -3 5 0 -5 -1 0

16、0 -3 -4 -2 2 2 M -1 0 -2 -3 -5 -1 -2 -3 -2 2 4 0 6 0 -2 -2 -1 -4 -2 2 -1 0 F -3 -4 -3 -6 -4 -5 -5 -5 -2 1 2 -5 0 9 -5 -3 -3 0 7 -1 -3 -4 P 1 0 0 -1 -3 0 -1 0 0 -2 -3 -1 -2 -5 6 1 0 -6 -5 -1 1 1 S 1 0 1 0 0 -1 0 1 -1 -1 -3 0 -2 -3 1 2 1 -2 -3 -1 2 1 T 1 -1 0 0 -2 -1 0 0 -1 0 -2 0 -1 -3 0 1 3 -5 -3 0

17、2 1 W -6 2 -4 -7 -8 -5 -7 -7 -3 -5 -2 -3 -4 0 -6 -2 -5 17 0 -6 -4 -4 Y -3 -4 -2 -4 0 -4 -4 -5 0 -1 -1 -4 -2 7 -5 -3 -3 0 10 -2 -2 -3 V 0 -2 -2 -2 -2 -2 -2 -1 -2 4 2 -2 2 -1 -1 -1 0 -6 -2 4 0 0 B 2 1 4 5 -3 3 4 2 3 -1 -2 2 -1 -3 1 2 2 -4 -2 0 6 5 Z 1 2 3 4 -4 5 5 1 3 -1 -1 2 0 -4 1 1 1 -4 -3 0 5 6 u模

18、块替换矩阵BLOSUM以序列片段为基础,它是 基于蛋白质模块(Block)数据库而建立起来的 u 在模块比对的每一列中，分别计算 两两氨基酸的变化情况,来自所有 模块的数值被用来计算BLOSUM矩阵u矩阵后面的数字表示构建此矩阵所用的 序列的相似程度，如BLOSUM62表示由 相似度为62%的序列构建AACECA - C = 0A - E = -1C - E = -4A - A = 4C - C = 9AACEC (Blocks Substitution Matrix)555657585960o 寻找蛋白质家族，识别多个序列的保守区域；o 相似的蛋白质序列往往具有相似的结构与功能；o 辅助预测

19、新序列的二级或三级结构；o 可以直观地看到基因的哪些区域对突变敏感；o PCR引物设计；我们为什么做多序列比对?o 分析多个序列的一致序列；o 用于进化分析，是用系统发育方法构建进化树的初使步骤； o 寻找个体之间单核苷酸多态性(SNPs)；o 通过序列比对发现直系同源(Orthologs)与旁系同源(Paralogs)基因；o 寻找同源基因(相似的序列往往具有同源性)。我们为什么做多序列比对?多序列比对与进化研究例子图中NYLS为树根一个多序列比对例子VTISCTGSSSNIGAG-NHVKWYQVTISCTGTSSNIGS-ITVNWYQLRLSCSSSGFIFSS-YAMYWVRLSLT

20、CTVSGTSFDD-YYSTWVRPEVTCVVVDVSHEDPQVKFNWYVDG-ATLVCLISDFYPGA-VTVAWKADS-AALGCLVKDYFPEP-VTVSWNSG-VSLTCLVKGFYPSD-IAVEWWSNG-多序列比对方法动态规划算法 (Dynamic Programming Algorithm)分而治之方法 (Divide and Conquer Methods)SP方法 (Sum of Pairs Methods) 累进方法 (Progressive Methods)迭代方法 (Iterative Methods)概形分析 (Pro)区块分析 (Block An

21、alysis) (Statistical Methods）在多序列比对前要考虑的问题一、全局序列比对 (Dynamic Programming Algorithm) (Divide and Conquer Methods) (Sum of Pairs Methods) (Progressive Methods) (Iterative Methods) (Genetic Algorithms)o 序列长度为序列长度为 n 的双序列比对的双序列比对n n2 比对比对o 比对数目成指数增长比对数目成指数增长n 例如：序列长度为例如：序列长度为n，序列数为，序列数为N 的多序列比对数目的多序列比对数目

22、是是nNo 对于数目较少且较短的序列来说都不切实际对于数目较少且较短的序列来说都不切实际1.动态规划算法(Dynamic Programming)Sequence 1Sequence 2Sequence 3多维的动态规划算法分而治之分而治之 (Divide and Conquer, DCA)方法方法将MSA（Measurement System Analysis）的空间复杂度减小DCA在线MSA2. 分而治之方法So in effect Sequence 1Sequence 2Sequence 33. SP(Sum of Pairs)方法4. 累进算法(Progressive Methods)

23、o 针对基于动态规划算法的MSA程序比对序列数目有限， Feng & Doolittle(1987)发明了累进算法o CLUSTAL 和 PILEUP 是目前常用的基于累进算法的比对软件o CLUSTAL 是免费软件,目前应用非常广泛 igbmc.u-strasbg.fr/BioInfo/ClustalX/Top.html1 对所有序列做双序列比对，构建距离矩阵计算相似性分数值2 基于双序列距离矩阵，构建一个进化树 Scer Cele Dmel MouseHuman3 依据进化树进行渐进比对 依据进化树，开始对关系较 近的序列进行两两比对 逐渐加入关系较远的序列进行比对 构建多序列比对Mult

24、iple alignmentScerevisiae 1Celegans 2 0.640Drosophia 3 0.634 0.327Human 4 0.630 0.408 0.420Mouse 5 0.619 0.405 0.469 0.289累进算法原理一般累进比对方法132513131325254droot果仁糖累进方法(Praline progressive strategy)13213131325254d d4累进算法的一些问题o 比对的准确性高度依赖于开始选择的双序列比对o 序列关系越远发生的错误可能越高o 选择合适的打分矩阵和罚分准则较困难ClLUSTALW/X简介CLUSTAL方

25、法* CLUSTAL W (1.8) Multiple Sequence Alignments * 1.Sequence Input From Disc2. Multiple Alignments 3. Profile / Structure Alignments 4. Phylogenetic trees S. Execute a system command H. HELP X. EXIT (leave program) Your choice:1CLUSTAL WSequences should all be in 1 file. 7 formats accepted: NBRF/PIR

26、, EMBL/SwissProt, Pearson (Fasta), GDE, Clustal, GCG/MSF, RSF. Enter the name of the sequence file: anti.fasta Sequence format is Pearson Sequences assumed to be PROTEIN Sequence 1: ANP4_PSEAM85 aa Sequence 2: ANP_LIMFE97 aa Sequence 3: ANPA_PSEAM82 aa Sequence 4: ANPX_PSEAM91 aa Sequence 5: ANPY_PS

27、EAM91 aa CLUSTAL W* CLUSTAL W (1.8) Multiple Sequence Alignments * 1.Sequence Input From Disc 2. Multiple Alignments 3. Profile / Structure Alignments 4. Phylogenetic trees S. Execute a system command H. HELP X. EXIT (leave program) Your choice: 2 CLUSTAL WClustal W* * MULTIPLE ALIGNMENT MENU * * 1.

28、 Do complete multiple alignment now (Slow/Accurate) 2. Produce guide tree 3. Do alignment using old guide tree file 4. Toggle Slow/Fast pairwise alignments = SLOW 5. Pairwise alignment parameters 6. Multiple alignment parameters 7. Reset gaps between alignments? = OFF 8. Toggle screen display = ON 9

29、. Output format options S. Execute a system command H. HELP or press RETURN to go back to main menuYour choice: 1 Enter a name for the CLUSTAL output file anti.aln: Enter name for new GUIDE TREE file anti.dnd: Start of Pairwise alignments Aligning. Sequences (1:2) Aligned. Score: 62 Sequences (1:3)

30、Aligned. Score: 59 Sequences (1:4) Aligned. Score: 84 Sequences (1:5) Aligned. Score: 83 Sequences (2:3) Aligned. Score: 68 Sequences (2:4) Aligned. Score: 80 Sequences (2:5) Aligned. Score: 79 Sequences (3:4) Aligned. Score: 81 Sequences (3:5) Aligned. Score: 80 Sequences (4:5) Aligned. Score: 98 G

31、uide tree : anti.dnd Start of Multiple Alignment There are 4 groups Aligning. Group 1: Sequences: 2 Score:1476 Group 2: Sequences: 3 Score:1499 Group 3: Sequences: 4 Score:1190 Group 4: Sequences: 5 Score:1404 Alignment Score 3470 Consensus length = 102 CLUSTAL-Alignment anti.aln Mac Vector界面的Clusta

32、l WClustal X介绍ClustalX介绍ClustalX介绍ClustalX介绍ClustalX介绍ExampleMultiple sequence alignment of 7 neuroglobins using clustalxPILEUPOutput of Pileup 401 OATNFA1 TTCAG. .ACACTCAGG TCATCTTCTC AAGC OATNFAR TTCAG. .ACACTCAGG TCATCTTCTC AAGC BSPTNFA TTCAA. .ACACTCAGG TCCTCTTCTC AAGC CEU14683 TTCAG. .ACCCTCAGG

33、 TCATCTTCTC AAGC HSTNFR CCCAG. .GCAGTCAGA TCATCTTCTC GAACSYNTNFTRP CCCAG. .GCAGTCAGA TCATCTTCTC GAAC CATTNFAA CCCAG. .ACACTCAGA TCATCTTCTC GAAC CFTNFA TCCAG. .ACAGTCAAA TCATCTTCTC GAAC RABTNFM CCCAGATGGT CACCCTCAGA TCAGCTTCTC GGGC RNTNFAA CCCAGACCCT CACACTCAGA TCATCTTCTC AAAAOutput of PileupClUSTAL和

34、PILEUP存在的问题5. 迭代方法 (Iterative Methods)二、局部序列比对1. 概形分析 (Pro)概形分析 (Pro)不同物种HSP70蛋白的profile图用CLUSTALX进行Profile比对2. 区块分析MSA中的统计学方法(Statistical Methods）(Expectation Maximization Algorithm,EM)(Gibbs Sampler)(Hidden Markov Model,HMM)(Position-Specific Scoring Matrix, PSSM)(Sequence Logo)最大期望运算法则MEME (Multi

35、ple EM for Motif Elicitation)o MEME程序是由加州大学san Diego 分校的超级计算中心所创立。o MEME的三种模体(Motif)模型：n OOPS每条序列中预期出现一次motif；n ZOOPS每条序列出现零次或一次motif；n TCM每条序列中出现任意次数的motif。基于Web的MEME软件o 在线MEME工具：n MEMEo Discover motifs (highly conserved regions) in groups of related DNA or protein sequences o http:/meme.sdsc.edu/m

36、eme/website/meme.html n MASTo Search sequence databases using motifso http:/meme.sdsc.edu/meme/website/mast.html MEME结果隐马尔可夫模型(HMM)隐马尔可夫模型(HMM)o 优点：植根于概率论，无须序列的顺序信息，无需插入/缺失和罚分，可以用到很多先验信息。o 缺点：需要至少20条序列，有时需要更多才能了解进化历史。o 分析工具：HMMER(/)o Pfam: (protein domain alignments and profile HMMs) http:/ HMM示意图NKYLT是通过BEG-M1-I1-M2-M3-M4-END计算这条路径的概率位置特异性记分矩阵PSSM用途序列标语(Sequence Logos)X轴表示模式的位置，Y轴上字母高度代表该字母在此位置上出现的频率CINEMA