《生物信息学序列比对.ppt》由会员分享，可在线阅读，更多相关《生物信息学序列比对.ppt（73页珍藏版）》请在三一办公上搜索。
1、序列比对,生物序列的同源性,指从一些数据中推断出的两个基因或蛋白质序列具而共同祖先的结论，属于质的判断。就是说A和B的关系上，只有是同源序列，或者非同源序列两种关系。而说A和B的同源性为80都是不科学的。,同 源 性,同 源 性,直系同源,旁系同源,？,Beta-球蛋白,alpha-球蛋白,共同祖先-未知球蛋白,The Concepts of Orthology and Paralogy,Orthologs and Paralogs are two types of homologous sequences.Orthology describes genes in different spec
2、ies that derive from a common ancestor.Orthologous genes may or may not have the same function.Paralogy describes homologous genes within a single species that diverged by gene duplication.,相似性和同源性关系,序列的相似性和序列的同源性有一定的关系，一般来说序列间的相似性越高的话，它们是同源序列的可能性就更高，所以经常可以通过序列的相似性来推测序列是否同源。正因为存在这样的关系，很多时候对序列的相似性和同源
3、性就没有做很明显的区分，造成经常等价混用两个名词。所以有出现A序列和B序列的同源性为80一说。,lipocalin,RBP4,Lipocalin和RBP4基因在序列上几乎没有相似性，却在结构和功能上有非常高的相似性，被认为是同源基因？是否有问题？,序列相似性的概念,序列比对(aligment)是序列分析的基础，其他一切都建立在序列排比的基础上。ACGCTAGCGCTAGCTGCTAGCTAG ACGCTAGCGCTAGCTGCTAGCTAG ACGCTAGCGCAAGCTGCTAGCTAG _ _,序列相似性的概念,序列比对的目的,序列排比是推导蛋白质二级结构的基础是初步蛋白质功能推断的基础可
4、用于蛋白质三级结构的推导可用于推导进化树和解释种间亲缘关系用于分析分子水平的选择压力探测序列之间的相互作用探测启动子单元等,在对一个新测定的蛋白序列进行分析时，比如分析的结果是：这个序列与某种细菌的ATPase相似。这是否意味着这个未知序列就是一个ATPase？,答案是不能确定的。,MSDTPSTGFSIIHPTSSEGQVPPPRHLSLTHPVVAKRISFYKSG-PRNGTIKIYENPARTFTRPYSAKNITIYKEND,匹配率(identity),两个蛋白质有一定数量的氨基酸在排比的位点上是相同的，即如果38个氨基酸的蛋白质中15个位点相同，我们说它们39.4%相同(39.4%
5、),相似性(similarity),通常在某些位点上有一些氨基酸被另外一些化学物理特性相近的氨基酸所代替，这种突变可称为保守突变。将保守突变的因素考虑在内，就可以定义各种打分方案(scoring schemes)对两序列的相似程度打分，所得分值即代表其相似的程度。,同源性(homology),只有当两个蛋白质在进化关系上具有共同的祖先时，才可称它们为同源的。,Beta-球蛋白,alpha-球蛋白,共同祖先-未知球蛋白,序列比较是如何进行的？,要分析两个序列是否相似，必须首先作比对分析(alignment）。如何作排比分析？最基本的条件是对序列的相似性做定量分析，然后将序列进行排比，在排比中要用
6、到gaps，insertions，substitutions。对gaps和insertions打分可用较简单的扣分方案，而substitutions的打分则比较复杂，必须先构建出一个计算机的算法矩阵(Matrix),再根据此方案对序列中氨基酸残基之间的差异或相似进行打分。,序列比较是如何进行的？,要对两个序列进行排比，必须首先打出其相似性的定量分值,于是需要一个打分矩阵。打分矩阵(Scoring Matrices):给不同的氨基酸配对定义的一系列相似性分值。而一个突变打分方案(mutation data matrix)则是根据排比时序列中点突变的情况设计出的打分方案。对氨基酸配对相似性的尺度衡
7、量，例如苯丙氨酸和异亮氨酸相似性的定量标准，可以以多种方式来定义。,序列比较是如何进行的？,打分矩阵(Scoring Matrices)对氨基酸配对相似性的尺度衡量，例如苯丙氨酸和异亮氨酸相似性的定量标准，可以以多种方式来定义。因此，设计一个打分矩阵，首先必须确定用什么算法模型。在序列排比分析中，打分矩阵只是某个算法模型的量化表现，比对的结果只在该算法模型所划定的范围内有意义。,生物信息学发展的3个主要阶段,萌芽期(60-70年代),形成期(80-90年代)：,高速发展期(2000-至今),以Dayhoff的替换矩阵和Neelleman-Wunsch算法为代表，它们实际组成了生物信息学的一个最
8、基本的内容和思路：序列比较。它们的出现，代表了生物信息学的诞生(虽然“生物信息学”一词很晚才出现)，以后的发展基本是在这2项内容上不断改善。,以分子数据库和BLAST等相似性搜索程序为代表。1982年三大分子数据库的国际合作使数据共享成为可能，同时为了有效管理与日俱增的数据，以BLAST、FASTA等为代表工具软件和相应的新算法大量被提出和研制，极大地改善了人类管理和利用分子数据的能力。在这一阶段，生物信息学作为一个新兴学科已经形成，并确立了自身学科的特征和地位,以基因组测序与分析为代表。基因组计划，特别是人类基因组计划的实施，分子数据以亿计；基因组水平上的分析使生物信息学的优势得以充分表现，
9、基因组信息学成为生物信息学中发展最快的学科前沿。,Dayhoff矩阵,Neelleman-Wunsch算法,Fasta算法,blast算法,基因组分析,计算生物学,生物信息学,过渡时期,生物信息学发展的3个主要阶段,萌芽期(60-70年代),过渡期(80-90年代),高速发展时期2000年-至今,序列比对的过程,建立评分矩阵,执行比对（动态规划算法）,确定最佳途径,Pam250,blosum62,fasta,blast,Dr.Margaret Oakley Dayhoff,credited as the founder of Bio-Informatics,ca.1980,历史寻踪,最大的成绩
10、或许就是得分矩阵的出现，Dayhoff被称作生物信息学之父或许更合适。,简单了解 Dayhoff 矩阵,PhD in Chemistry,Columbia University,1947Watson Computing Laboratory Fellow 1947-48Atlas of Protein Sequence and Structure 1965-1978Protein Sequence Database,PAM Score Matrix(1978),Log-odds matrix for PAM250,PAM系列矩阵,1.Margaret Dayhoff,1978;2.Accept
11、ed point mutation(PAM):可接受的点突变，氨基酸的改变不显著影响蛋白质的功能；3.进化模型：中性进化，Kimura,1968;,使用数据,1.34个蛋白质超家族；2.72个蛋白质组；3.1572个突变；4.序列相似性 85%,功能同源的蛋白质-通过中性进化，引入可接受的点突变；,统计氨基酸的替代,1.对于同一个group内的蛋白质序列，统计氨基酸可能出现的频率，以及替换的个数；2.注意：不考虑空位；,该例中：fFF=13fFY=6fFH=1fYY=6fYF=9,对20种氨基酸做相同统计,注意：fab不一定等于fba,PAM1矩阵的构建,1.两个蛋白质序列的1%氨基酸发生变化
12、的时间；2.定义进化时间以氨基酸的变异比例为准，而不是时间；因为各个蛋白质家族进化的速度并不相等；3.PAM2=PAM1*PAM1 PAM3=(PAM1)3 PAM250=(PAM1)250,20种氨基酸的相对突变能力,Ala:主观的设定为100,PAM1的数值,氨基酸改变,概率值,PAM2矩阵,1.基本假设：每个氨基酸的突变的概率独立于前次突变。因此，PAM2=PAM1*PAM1,PAM250矩阵,1.PAM250:250%的期望的突变；2.蛋白质序列仍然有15-30%左右的相似性，例如：F-F:32%A-A:13%,PAM250矩阵，乘以100,打分矩阵的使用,1.PAM250:15-30
13、%的序列相似性；2.PAM120:40%的序列相似性；3.PAM80:50%4.PAM60:60%5.如何选择最合适的矩阵？遍历尝试,PAM矩阵的问题及改进,1.PAM系列矩阵存在的问题：A.氨基酸的打分矩阵，不关心核酸；B.进化模型的构建需要系统发育树的分析，因此，成为一个循环论证的问题：序列比对-矩阵构建-打分，进行新的序列比对；C.数据集很小；2.打分矩阵的改进 BLOSUM系列矩阵,2.BLOSUM矩阵,1.BLOCK:蛋白质家族保守的一段氨基酸，无gap，一般几个-上百个氨基酸；2.Prosite家族：至少有一个BLOCK存在于该家族的所有蛋白质序列中；3.分析500个Prosite
14、家族；4.BLOSUM62:序列的平均相似性为62%的BLOCK构建的打分矩阵；5.最被广泛使用的氨基酸打分矩阵,序列比较是如何进行的？-打分矩阵的原理(Principles of Scoring Matrices),Blosum矩阵(The Blosum matrices)Dayhoff模型假设，蛋白质序列各部位进化的速率是均等的。但事实很可能并非如此，因为保守区的进化速率显然低于非保守区。,Blosum矩阵(The Blosum matrices)(blocks substitution matrix)Henikoff&Henikoff用以下方法解决这一问题。他们采用不同种类蛋白质序列片段
15、的区间(blocks)作排比研究，排比时不加入gaps。这些序列区间对应于高度保守的区域。氨基酸匹配率可通过简单将各区间可能的匹配率加权。再将这些匹配率写如匹配率表。其进化相关机率的计算方法与Dayhoff matrix相似。,序列比较是如何进行的？-打分矩阵的原理(Principles of Scoring Matrices),Blosum矩阵(The Blosum matrices)再以簇群方式将不同进化距离整合进方案内：当两个序列排比的匹配率高于某个阈值时便归为一个簇群。不断将匹配率高于阈值的序列加入簇群内。然后将簇群内所有序列平均。通过簇群方式使得关系紧密的序列在匹配率表中的权重减少，
16、而且随着阈值的减小而减小，从而也象PAM矩阵系列一样产生一系列的矩阵。这个矩阵称为Blosum矩阵。用一个指数来指示簇群的阈值水平，即Blosum80指将序列区间归为簇群时以80%匹配率为阈值。Blosum62最接近于PAM250。,序列比较是如何进行的？-打分矩阵的原理(Principles of Scoring Matrices),Blosum矩阵(The Blosum matrices)矩阵的使用效果(Matrix Performance)通过一些测试显示，Blosum矩阵用于在数据库中查找同源性序列时，效果比PAM矩阵好。如上述，矩阵从1到250PAM两极距离太远，可能引起不准确；而B
17、losum直接从最同源的序列的区间排比获取匹配率，不考虑进化距离。Blosum矩阵的突变数据来源于未加gaps的序列区间排比，相当于蛋白序列的保守区。,Relationship between scoring matrices.The BLOSUM62 has become a de facto standard scoring matrix for a wide range of alignment programs.It is the default matrix in BLAST,PAM模型可用于寻找蛋白质的进化起源BLOSUM模型则用于发现蛋白质的保守域,打分矩阵,1.Dayhoff:
18、PAM系列矩阵；2.Henikoff:BLOSUM系列矩阵；3.常用氨基酸打分矩阵：BLOSUM62;,！,比对算法,递归关系(recurrence relation)列表式运算(tabular computation)路径回溯(traceback),动态规画算法,费氏数(Fibonacci number),费氏数(Fibonacci number)可用下列的递归关系(recurrence)来描述：,Global alignment Needleman-Wunsch algorithmLocal alignment Smith-Waterman algorithm,在1970年代，分子生物学家
19、Needleman 及Wunsch 以动态程序设计技巧(dynamic programming)分析了氨基酸序列的相似程度；有趣的是，在同一时期，计算科学家Wagner及Fisher 也以极相似的方式来计算两序列间的编辑距离(edit distance)，而这两个重要创作当初是在互不知情下独立完成的。虽然分子生物学家看的是两序列的相似程度，而计算器科学家看的是两序列的差异，但这两个问题已被证明是对偶问题(dual problem)，它们的值是可藉由公式相互转换的。,全局比对,The Needleman-Wunsch algorithm,Lets do a simple example,adap
20、ted from Needleman&Wunschs original paper.First,place the sequences on a matrix of cells.At each cell where the amino acids are identical,enter a value of 1.All the other cells are implicitly given a score of 0(zero).,Now,starting at the C-terminal ends of the sequences and working toward the origin
21、s,add to each cell the maximum value from among all the cells downstream from it(not including cells directly below or directly to the right.Lets do a few cycles of this and see how the matrix develops.Start with the last column and last row,adding in the zeros,Continue with the next column and row.
22、Note that,on the next-to-last row,the cells upstream from the PxP match each now get a value of 1;the cell with the DxD match gets a value of 1+1=2,since the sequences could be aligned beginning with D to give a D.P match(with a gap,of course).As we go along,the number in each cell will be the large
23、st number of pair matches that can be found if that cell is the origin.,Lets continue with the next row and column.All three of the RxR matches get incremented by 1 because you could now get a R.P alignment,starting at an RxR cell,We will work one more row&column.Now there are 5 cells containing the
24、 number 3.You could start at ANY of these 5 cells and,moving down&to the right,match up the sequence C.R.P!(Remember,as we go along,the number in each cell will be the largest number of pair matches that can be found if that cell is the origin.),Ive filled in the rest of the table.You are welcome to
25、 do it by hand to check me and to be sure you understand the process,In this simple example,there are two optimal paths through the matrix:,Here are the two optimal alignments,局部比对,The Smith-Waterman algorithm is a dynamic programming method for determining similarity between nucleotide or protein s
26、equences.The algorithm was first proposed in 1981 by Smith and Waterma,An exampleThe Smith-Waterman algorithm can be exemplified by the comparison of two sequences:Sequence A:CAGCCUCGCUUAGSequence B:AAUGCCAUUGACGGParameters for the scoring matrix being:,Sequence B:G C C A U U GSequence A:G C C-U C G
27、,Smith,fasta,在分析两个序列时，Smith-Waterman的方法也许勉强可以接受，但如果以它做为数据库搜寻的引擎，那就有些慢了，因为这将会耗费不少宝贵的时光。使用者选定参数ktup(k-tuple，在DNA序列分析时这个值通常设成 6 到 8；蛋白质序列则常使用 1 到 2 的值)，FASTA只考虑那些长度至少为 ktup 的那些相似子序列，试着藉由它们找出一些可能有相似性的对角区域(diagonal band)，然后再将Smith-Waterman的方法套用在这些小区域上。在BLAST横扫千军前，FASTA曾是最常被用来分析序列的工具。在FASTA中，因为它试着去串联那些 kt
28、up序列，所以耗费了不少时间,BLAST,初版的BLAST则以长度至少为 w 的相似区段着眼，只往对角线(diagonal)方向试着去延伸，直到分数的降低程度超过使用者所给定的范围为止，因为它完全不考虑间隔(gap)，所以非常地有效率，但缺点是有时不够敏锐(sensitive)。不过在第二版的BLAST中，已针对这样的缺点加以修正，它在延伸对角线时采用的策略是跳着延伸(注：延伸对角线耗去了大部份初版BLAST执行的时间)，这个立论基础是如果它真是分数很高的相似区段，跳着延伸也不会错过。,blast,fasta,知识点总结,Pam250,blosum62,Fasta算法,Blast算法,Dayhoff,Neelleman-Wunsch算法,Henikoff,Smith-Waterman算法,得分矩阵,比对算法,Pam矩阵,blosum矩阵,全局比对,局部比对,
