两两序列比对与算法PPT课件

1、两两序列比对与算法生物信息学生物信息学2nSequence homology, similarity and comparison 序列同源性、相似性和序列比对Homology is one of the most important terms in biology.生物信息学3基因组学概论3同源性(homology)反映出进化关系祖先基因祖先基因物种物种1基因复制基因复制Orthologs 直直向同向同源源基因基因物种物种2Paralogs 平平行进化同行进化同源源基因基因物种分化物种分化n同源基因(homologs)具有共同的进化祖先，是通过基因之间的序列相似性而发现的。这些相似性就形成

2、了分子系统进化的依据。n同源基因分为两类：直向同源基因(直源基因) orthologs：由于物种分化产生的分布在不同物种间的同源基因平行进化同源基因(并源基因) paralogs：同一物种内由于基因复制产生的的同源基因生物信息学44生物信息学5利用orthologous构建不同物种的系统发育树“Phylogenetic(系统发育的) reconstructions of organisms created using information from the nucleotide sequences of genes require orthologous, rather than paral

3、ogous genes, so the distinction between these two gene classes is important for practical reasons.”生物信息学6n利用多个物种之间的orthologs或者一个物种内的paralogs来构建分子进化树（称之为基因树gene tree）在后面章节中会讲授。生物信息学7Homology 同源性nFeatures derived from a common ancestor are called homologs.nNew sequences are adapted from pre-existing s

4、equences rather than invented de novo (从新开始).nNature is a tinkerer and not an inventor. Its products are not necessarily neat or elegant. (Jacob. 1977. Science 196:1161-1166) 进化是一位修补匠,而不是发明家。他的产物不必整洁而又优雅. 生物信息学8Assumption: genetic constitution of organisms can be traced back to a set of common ances

5、tral genes. 假设：通过追溯一系列共同祖先基因，我们可以构建物种之间的亲缘关系。nThus, we can make a comparison between gene sequences from different species to identify the distances between them. 基于上面的假设，我们可以通过比较不同物种的同源序列的差异，来推断这些物种或者序列之间的进化距离。生物信息学9Homology SimilarityOrthologous relationships: p One to one ? One to many? Or Many t

6、o many?p Complex: gene duplication, gene loss and speciation can be frequent events in the history of a group of organisms. 基因复制、基因丢失和物种分化等进化事件频繁发生，导致不同物种的同源基因数量很不一致。生物信息学10Further readingnFitch WM. (2000) Homology - a personal view on some of the problems. TRENDS IN GENETICS 16 (5): 227-231.nSonnha

7、mmer ELL and Koonin EV. (2002) Orthology, paralogy and proposed classification for paralog subtypes. TRENDS IN GENETICS 18 (12): 619-620.这两篇文献不提供这两篇文献不提供PDFs，你们利用，你们利用PubMed或者其他搜索引擎或者其他搜索引擎来搜索文献。依据个人习惯，自由选择在线阅读，或者下载来搜索文献。依据个人习惯，自由选择在线阅读，或者下载PDF阅读。阅读。生物信息学11接下来几次课内要求掌握1.在数据库中进行序列相似性搜索：两两序列比对Blast, PS

8、I-blast, Megablast, Blat 2.多序列比对：多条序列一起参与比较ClustalW/X, MUSCLE, Mafft, T-Coffee 3.进化树构建与分子进化分析Mega, Phylip, PAUP, PhyML, Bayes 生物信息学12n两两序列比对BlastBlast 演示两两序列比对算法生物信息学13Database Similarity Search 数据库相似性搜索Sequence similarity is a powerful tool for in the sequence world Scans a database for alignments

9、of a query sequence 在数据库中检测和查询序列相似的序列Can get tons of informationFunctionality 功能Evolutionary history 进化历史Important residues 重要的残基Seq ASeq 1Seq 2Seq NSeq A1Seq A2Seq A3Seq Amdatabase生物信息学14BlastnBlast 是“基本的局部相似性查询工具”(Basic Local Alignment Search Tool)的 缩写.Altschul SF, Gish W, Miller W, Myers EW &

10、 Lipman DJ. 1990. Basic local alignment search tool. JMB 215:403-415Altschul & Gish 1996. Methods in Enzymology 266:460-480;Altschul et al. 1997. NAR 25:3389-3402nBlast 是一个序列相似性搜索的程序包，其中包含了很多个独立的程序，这些程序是根据查询的对象和数据库的不同来定义的。比如说查询的序列为核酸，查询数据库亦为核酸序列数据库，那么就应该选择blastn程序。nFast & Heuristic (运行速度快&am

11、p;直观的)Not 100% assurance, but excellent in most cases.生物信息学15主要的Blast程序程序名Query 查询序列Subject 数据库搜索方法Blastn核酸核酸核酸序列搜索逐一核酸数据库中的序列Blastp蛋白质蛋白质蛋白质序列搜索逐一蛋白质数据库中的序列Blastx核酸蛋白质核酸序列6框翻译成蛋白质序列后和蛋白质数据库中的序列逐一搜索。Tblastn蛋白质核酸蛋白质序列和核酸数据库中的核酸序列6框翻译后的蛋白质序列逐一比对。TBlastx核酸核酸核酸序列6框翻译成蛋白质序列，再和核酸数据库中的核酸序列6框翻译成的蛋白质序列逐一进行比对

12、。QuerySeq 1Seq 2Seq NSeq A1Seq A2Seq A3Seq AmSubject生物信息学16Blast评价序列相似性的两个分值Score：使用打分矩阵对匹配的片段进行打分，这是对各对氨基酸残基（或碱基）打分求和的结果，一般来说，匹配片段越长、相似性越高则Score值越大。E-value:在相同长度的情况下，两个氨基酸残基（或碱基）随机排列的序列进行打分，得到上述Score值的概率的大小。 E-value值越小表示随机情况下得到该Score值的可能性越低。类似于Empirical P-valueH0: score_observed is random.H1: score

13、_observed is not random.生物信息学17Blast资源1.NCBI主站点： (网络版) /blast/ (单机版；本课程不讲授)2.其他站点 /Blast/index.jsp (拟南芥) /blast/ (果蝇) 生物信息学18n例子：Human Hemoglobin subunit beta (血红蛋白亚基)n对应的蛋白质序列：sp|P68871|HBB_HUMAN Hemoglo

14、bin subunit beta OS=Homo sapiens GN=HBB PE=1 SV=2 MVHLTPEEKSAVTALWGKVNVDEVGGEALGRLLVVYPWTQRFFESFGDLSTPDAVMGNPK VKAHGKKVLGAFSDGLAHLDNLKGTFATLSELHCDKLHVDPENFRLLGNVLVCVLAHHFG KEFTPPVQAAYQKVVAGVANALAHKYH 1919两两序列比对 (Pairwise alignment)2020Scroll down本学期将会讲授如何使用Primer-BLAST设计引

15、物21212.选择程序。因为查询序列是蛋白序列可以选择blastp，点击进入也可以选择tblastn作为演示，我们这里选blastp生物信息学22Three steps to BLAST生物信息学23First glance to the output生物信息学24First glance to the output生物信息学25First glance to the outputFirst glance to the outputFirst glance to the output生物信息学28And now, more details if my sequence is saved in

16、a fasta file, my friend just tell me an accession number?7xx生物信息学29输入蛋白质编号或者FASTA序列或者上传本地FASTA文件And now, more details生物信息学30可以设定输入序列的起始位置生物信息学31 I only care about human proteins from SwissProtAnd now, more details生物信息学32And now, more details I only care about human proteins from SwissProt生物信息学33E-va

17、lue 上限默认值：0.05And now, more details生物信息学34准备提交Blast生物信息学35准备提交Blast生物信息学36Output: a closer lookClick to save our result in difference filetype生物信息学37Summary由于提交Blast之前，我们对数据库、物种和E-value定限制，所以这次比对出来的序列比上次少很多生物信息学38One-line descriptionHuman protein sequence from Swissprot(sp), with linkage to the prot

18、ein webpageE-Value 表示因随机性获得这一比对结果的可能性 (值值越小越好越小越好)Bits score of each alignment(值越大越好值越大越好)生物信息学39One-line descriptionClick to save fasta or aligned information of selected proteins.生物信息学40AlignmentslIdentities 序列相似性: Number of identical residues / length of alignment;lPositives 序列一致性: Number of cons

19、ervative substitutions / length of alignment;lGaps: Number of gaps / length of alignment.Sequence identifierSequence definition生物信息学41AlignmentsIdentical matchesGaps(indels)+：Conservative substitutions生物信息学42但是有时候n数据库序列 自己定义，而不是NCBI上提供。n这时候可以选择 “Aligh two or more sequences”生物信息学43生物信息学44生物信息学45Blast

20、 Help生物信息学46作业作业1.重点：熟悉Blast运行的例子，熟悉Blast使用流程和结果分析。2.可选：通过Blast Help了解更多内容。/Blast.cgi?CMD=Web&PAGE_TYPE=BlastDocs生物信息学47序列比对的算法生物信息学48序列比对算法n空位罚分 (重点讲解)n双序列比对方法 (了解)点阵序列比较(Dot Matrix Sequence Comparison)动态规划算法(Dynamic Programming Algorithm)n记分矩阵 (了解)生物信息学49序列比对两种类型o 全

21、局序列比对全局序列比对l定义：在全局范围内对两条序列进行比对打分的方法l适合于非常相似且长度近似相等的序列o 局部序列比对局部序列比对l定义：一种寻找匹配子序列的序列比对方法 l适合于一些片段相似而另一些片段相异的序列生物信息学50序列比对两种类型Blast 采用局部比对，所以在大多数情况下两条序列的比对会被分解为若干个明显的HSP (High-score Sequence Pairs)。生物信息学51生物信息学52空位罚分(Gap Penalties)n空位为了获得两个序列最佳比对，必须使用空位和空位罚分n空位罚分分类：空位开放罚分(Gap opening penalty)空位扩展罚分(Ga

22、p extension penalty)n最优的序列比对通常具有以下两下特征：尽可能多的匹配尽可能少的空位n插入任意多的空位会产生较高的分数，但找到的并不一定是真正相似序列生物信息学53空位罚分公式 A T G T T A T A CT A T G T G C G T A T A Score=4参数:匹配匹配 match = 1非匹配非匹配 mismatch = 0g= -3r = -0.1x = 3score：8 - 3.2 = 4.8Wx=g+r(x-1)Wx:空位总记分g: 空位开放罚分 gap-open penaltyr: 空位扩展罚分 gap-extension penaltyx:

23、空位长度 gap lengthT 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.2生物信息学54双序列比对方法n点阵序列比较 (Dot Matrix Sequence Comparison)n动态规划算法 (Dynamic Programming Algorithm)n词或K串方法 (Word or K-tuple Methods)：不讲授生物信息学55点阵序列比较n点阵(Dot Matrix)分析是一种简单的图形显示序列相似性的方法自身比对对两条序列的相似性作整

24、体的估计生物信息学56点阵法：自身的比对A K G F K C A D EA100000100K10010000G1000000F100000K10000C1000A100D10E1生物信息学57点阵法：重复序列A K G F D K G F EA100000000K10001000G1000100F100010D10000K11000G1100F110E1生物信息学58点阵法：反向重复/回文A U G C A C G U CA100010000U10000010G1000100C101000A10000C11001G1100U110C1生物信息学59点阵法：不同序列的比对P K D F C

25、K A L VP100000000K10001000F0100000T00000K11000A100I00V011:PKDFCKALV2:PK-FTKAIVSeq 1Seq2生物信息学60点阵法的序列比对Sequence 1#1nSequence 2#1m“-” Insertion“-” Insertion生物信息学61动态规划算法n动态规划算法(Dynamic Programming Algorithm)是一种计算方法，它的主要思路是把一个NP问题分成若干个小问题来解决。n在生物学中应用的两种动态规划算法：Needleman-Wunsch算法（全局比对）和Smith-Waterman算法（局

26、部比对）生物信息学62序列比对中某一位点匹配的三种可能性nEg. 匹配=1,非匹配=0, 空位罚分=-1Sequence1: CACGASequence2: CGA第一个位点剩余序列得分CCACGAGA+1-CCACGAGA-1C-ACGACGA-1生物信息学63动态规划算法的正式表述Si,j这个位置的分数为图中箭头所示三个方向值中最大的一个i -xi -1j -1j -yji Si - x,j - wx Si 1, j- 1 + s(ai , bj)Si, j - y - wy Si, j 生物信息学64动态规划算法实例GapACTTCGGapACTAG匹配3错配-1空位-2生物信息学65G

27、apACTTCGGap0ACTAG动态规划算法实例匹配3错配-1空位-2生物信息学66GapACTTCGGap0-2ACTAG动态规划算法实例匹配3错配-1空位-2生物信息学67GapACTTCGGap0-2-4-6-8-10-12ACTAG动态规划算法实例匹配3错配-1空位-2生物信息学68GapACTTCGGap0-2-4-6-8-10-12A-2CTAG动态规划算法实例匹配3错配-1空位-2生物信息学69GapACTTCGGap0-2-4-6-8-10-12A-2C-4T-6A-8G-10动态规划算法实例?S(2,2)-2+(-2)-2+(-2)0+3匹配3错配-1空位-2生物信息学70

28、GapACTTCGGap0-2-4-6-8-10-12A-23C-4T-6A-8G-10动态规划算法实例?S(2,3)-4+(-2) 3+(-2)-2+(-1)匹配3错配-1空位-2生物信息学71动态规划算法实例GapACTTCGGap0-2-4-6-8-10-12A-231C-4T-6A-8G-10匹配3错配-1空位-2生物信息学72动态规划算法实例GapACTTCGGap0-2-4-6-8-10-12A-231-1-3-5-7C-416420-2T-6-14?A-8-3 2G-10-50S(4,4) 4+(-2) 4+(-2) 6+3匹配3错配-1空位-2生物信息学73动态规划算法实例Ga

29、pACTTCGGap0-2-4-6-8-10-12A-231-1-3-5-7C-416420-2T-6-149A-8-3 2G-10-50匹配3错配-1空位-2生物信息学74GapACTTCGGap0-2-4-6-8-10-12A-231-1-3-5-7C-416420-2T-6-149753A-8-3 27864G-10-505679GGT-CATTCCAA回回 溯溯生物信息学75GapACTTCGGap0-2-4-6-8-10-12A-231-1-3-5-7C-416420-2T-6-149753A-8-3 27864G-10-505679GGT-CATTCCAA生物信息学76GapACT

30、TCGGap0-2-4-6-8-10-12A-231-1-3-5-7C-416420-2T-6-149753A-8-3 27864G-10-505679GGTAC-TTCCAA生物信息学77比对结果1.ACTTCGAC-TAG2.ACTTCGACT-AG3.ACTTCGACTA-G哪一个是最优比对哪一个是最优比对(optimal alignment)呢呢?记分矩阵记分矩阵生物信息学78记分矩阵 (SCORING MATRICES)nDNA Scoring Matrices (DNA积分矩阵)nAmino Acid Substitution Matrices (氨基酸替换矩阵)PAM (Poin

31、t Accepted Mutation) BLOSUM (Blocks Substitution Matrix)生物信息学79转换和颠换CTAG嘧啶嘌呤 表示转换(transition)， 表示颠换(transversions) 转换比颠换更容易发生DNA计分矩阵生物信息学80AGTCA0.99G0.0060.99T0.0020.0020.99C0.0020.0020.0060.99转换速率是颠换3倍时的模型转换和颠换CTAG嘧啶嘌呤生物信息学81蛋白质计分矩阵PTHPLASKTQILPEDLASEDLTIPTHPLAGERAIGLARLAEEDFGMSequence 1Sequence 2记

32、分矩阵T:T = 5T:G= -2Score= 48 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 . 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 .生物信息学82PAM (Percent Accepted Mutation) 矩阵n氨基酸容易被其它生化、物理特性相似的氨基酸替换nPAM1(1个PAM单位）被定义为每100个残基

33、出现一个被接受的点突变(氨基酸的置换不引起蛋白质功能上的显著变化）nPAMn是PAM1自乘n次nPAM250、PAM120、PAM80和PAM60矩阵可用于相似性分别为20%、40%、50%和60%的序列比对生物信息学83 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 -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

34、-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 -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

35、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 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 -