生物信息学更多更有效的成对序列比对及多序列比对技巧探秘

7.91–Lecture#2MichaelYaffe更多的成对序列比对—和—多序列比对阅读：文献：Mountpp.8-9,65-89,96-115,140-155,161-170要点大纲递归和动力学设计动力学设计应用：全局比对：Needleman-Wunsch动力学设计应用：局部比对：Smith-Waterman置换矩阵：PAM,BLOSUM,Gonnet空位—线形和affine序列比对统计学要优化一个序列比对需要知道什么要点大纲（续）多序列比对：MSA,Clustal阻断分析特殊位置得分矩阵(PSSM)例子O（NK）是“多项式时间”只要K3……就容易处理考虑到非空位点阵全局比对：……本质上是一个O(mn)矩阵好的例子O(n)比O(nlog(n)),O(n2),O(n3)更好。糟糕的例子O(kn)=指数时间…….恐怖！！！！NP问题—不知道多项式时间解决办法=非确定性多项式问题。递归和动力学设计比对两个没有空位的蛋白序列—大概是一个O(mn)问题。没有空位—适合于计算天文学，直接比对方法不能做。(=22L/√(2πL);L=序列长度)可选择的办法是比对所有可能的特征对(配对和错配，也很好的考虑到了空位，保持比对的数量的易处理性。)这种方法也叫动力学设计。在算术上证明了产生最佳比对。需要置换或相似矩阵和考虑到空位的方法。怎样记下比队得分的例子：写下两条序列序列#1序列#2置换矩阵得分得分=Σ（AA配对得分）-缺口处罚=15BLOSUM62得分矩阵得分系统应该：支持匹配识别或是相关氨基酸处罚错误匹配和空位。为了得到好的得分系统需要明确：在相关蛋白质与它的偶然产生相比较中，特殊氨基酸对被发现的几率。替代矩阵中就包含有这些信息……并且当有空位时，会有更好的选择。真实替代矩阵的起源：首先要知道在相关蛋白质中一个氨基酸替代另一个氨基酸的频率[=P(ab)]c/w。另一个氨基酸偶然产生替代的机会，是以蛋白质中每个氨基酸的相对频率为基础的，即q(a)和q(b)。这称为“不均几率”：P(ab)/q(a)q(b)如果在比对中所有位置都进行了这种处理，那么总概率将会是每个位置不均几率的乘积……但是乘法耗费计算空间……因此…..取log(不均几率)再把它们相加，用此来代替。像PAM和BLOSUM矩阵就是取了不均几率的对数。也包含了反映相关蛋白质中的氨基酸替代的可能性的正数和负数。动力学设计过程：首先沿着侧边从上到下写下一个序列。注意—线形空位处罚：γ(n)=nA，其中A=空位处罚动力学设计过程：首先沿着侧边从上到下写下一个序列。空位空位因此得到Sij必须知道S(i-1,j-1)和S(i,j-1)andS(i-1,j)……因此需要回归。我们用解决小问题的方法解决大问题。我们必须记录怎样得到Sij。例如表格式矩阵中的中间解答。计算机科学家称这为动力学设计，其中“设计”即矩阵，并不是某种计算机编码。动力学设计过程：首先沿着侧边从上到下写下一个序列。空位空位全局比对：Needleman-Wunsch-SellersO(n2)利用线形空位处罚最大：对角线从左到右从上到下动力学设计过程：首先沿着侧边从上到下写下一个序列。空位空位全局比对：Needleman-Wunsch-SellersO(n2)利用线形空位处罚最大：对角线从左到右从上到下动力学设计过程：首先沿着侧边从上到下写下一个序列。动力学设计过程：首先沿着侧边从上到下写下一个序列。全局比对：O(n2)利用线形空位处罚Needleman-Wunsch-Sellers最大：对角线从左到右从上到下动力学设计过程：首先沿着侧边从上到下写下一个序列。动力学设计过程：首先沿着侧边从上到下写下一个序列。源追踪：当正方形比对完成之后，从较低的右边开始，以后的工作根据箭头观察怎样到那儿……源追踪引起的比对：只有向后看才能理解生活，但是要生活好，必须向前看。—SørenKierkegaard局部比对TempleSmith和MichaelWaterman，1981—修改了Needleman-Wunsch-Sellers局部比对是从x序列子列到y序列子列比对中得分最好的。重要的并不是比对到序列结束。对序列x，残基1，2，3……N，能够得到~N2个子链，也就是说启始点a=1,2….N，结束点b=1,2….n。Y序列也一样，得到~M2个子链。对于任意两个子链，由于有旧的O(mn)比对问题，所以可能比对的总数目是~N2M2(NM)=O(M3N3)—很不好！！！！在多项式时间中是可以解决的，但需要一个大的多项式。局部比对再一次地，动力学设计可以补救！动力学设计的基本设置与以前一样……错配时相似矩阵MUST产生负值--和--****在得分矩阵中，计算位置的值是负数时，这个值就被设置成0。比对就此结束Smith-Waterman:首先沿着侧边从上到下写下一个序列。空位空位局部比对：最大：对角线从左到右从上到下全局和局部比对程序生物工作平台：的网页氨基酸替代矩阵MargaretDayhoff,1978,PAM矩阵**进化模型**以一个小数据库为基础。假设是对称的：假设短时间周期的氨基酸替代模型能够推测出长时间周期的替代模型。71组蛋白质序列，1572个相似氨基酸85%发生改变。功能蛋白质→由自然选择“接受”变异PAM1矩阵意味着在蛋白质之间有1%的分歧–也就是说每100个残基中有1个氨基酸变异。一些文章也重述了这个情况，每个氨基酸变成另一个氨基酸的概率是~1%，而不变的概率是~99%。构建Dayhoff矩阵：PAM1步骤1：在相关蛋白质家族内测量每个氨基酸的成对替代频率900个Phe(F)….+另外100个可能的Phe但是…100个Phe(F)→80Tyr(Y),3Trp(W),2His(H)….给了fab,也就是……通过进化！对所有20个氨基酸的处理直接假设—第一顺序马尔柯夫链转化模型给定fab=配对交换频率步骤2：计算ab交换对的相对概率Pa=氨基酸a的概率fab=a和b之间的替代数量fa=含有氨基酸a的替代模式总数f=在相关序列组中产生变异的总数量=M’ab的相对概率定义为：步骤3：依比例确定相对概率，即获得任意一个氨基酸变成另一个不同的氨基酸1%总机会i.s.测量M’来确定:步骤4：定义“相对易变性”给每个氨基酸指定ma含有氨基酸a的突变数量‘a’变异的方向Prob(a)*每100个位点中加权变异的总数步骤5：计算进化距离尺度只有1/1000的氨基酸产生变化Maa表示氨基酸守衡实例（Phe突变的调整概率）**用尺度因子λ，Maa是~0.99也就是变异概率是~1%也就是定义PAM1矩阵….λ是进化尺度因子……对于任何特别的突变概率，λMab反应了在1PAM上氨基酸b替代氨基酸a的可能性的标准尺度。接下来，假定在每个位置的变异独立于前面的变异。因此计算关系稍远的相关蛋白的变化，该蛋白质进行了N次变异，每一百个氨基酸通过乘以PAM1矩阵对其变异次数N的值例子：PAM2矩阵：PAM250矩阵•将PAM1自乘250次！有Mab个值。如进化互相关联的蛋白质在PAM250中一个氨基酸取代另一个氨基酸的几率PAM250矩阵－250％期望变化序列仍然有~15-30％序列相似性，如，苯丙氨酸与苯丙氨酸有~32%的匹配概率丙氨酸与丙氨酸有~13%的匹配概率期望值％相似性其它的PAM矩阵：PAM120－40%PAM80－50%PAM60－60%PAM250–15-30%相似性相似性序列的使用PAM250矩阵表中数据的来源？步骤6：计算关联几率序列比对中两个氨基酸来自于由进化的相关蛋白几率，和它们来自于两个不相关的蛋白质比对的几率Mab＝相关蛋白中b取代a的几率－vs－Paran＝非相关蛋白中b取代a的几率……它们是随机的现在，Paran＝fa，氨基酸a发生的频率PAM250矩阵表中数据的来源？步骤6：计算关联几率进化的关联几率而不是偶然几率PAM250矩阵表中数据的来源？步骤7：计算对数值(关联几率)和乘以十来清楚碎片值例子：Phe→Tyr(必须＝Tyr→Phe)因此平均值＝(5.7+8.3)/2=7…PAM250中的数据记住…看上次怎样使用这些数字+动态规划程序来得到比对分值PAM250矩阵－250％期望变化序列仍然有~15-30％序列相似性，如，苯丙氨酸与苯丙氨酸有~32%的匹配概率丙氨酸与丙氨酸有~13%的匹配概率期望值％相似性其它的PAM矩阵：PAM120－40%PAM80－50%PAM60－60%PAM250–15-30%相似性用正确的PAM矩阵比对是基于比对序列的相似性。但是等等…我们怎样知道序列间的关系呢？通常我们不知道！！！！所以……尝试PAM200，PAM120，PAM60，PAM80和PAM30矩阵，用非空位比对得分最高的一个相似性序列的使用怎样使用正确的矩阵！替代氨基酸矩阵Dayhoff的问题：•基于氨基酸，不是核苷酸。•假定进化模型具有直接系统发生关系，循环讨论：序列→矩阵；矩阵→新的序列•基于一小部分关系紧密的分子•Gonnett,Cohen&Benner•所有的模型是用达尔文的1,700,000匹配对所有的数据库极性匹配直接在不同PAM编译进化矩阵•BLOSUM=空位氨基酸替代矩阵－Henikoff&Henikoff1992基于一个较大的数据库，该数据库从~500Prosite家族得到，这些家族用用每个家族定义的保守氨基酸模式”块”由Bairoch确认典型的用多序列比对AA替代注释，得到对数几率比率例如…块模式60％确认得到Blosum60矩阵，等等…如：基于非缺口比对的保守函数块。Blosum62－在信息内容和数据量最优匹配不是基于直接的进化模型GAPS•线性罚分矩阵Wn=nγ,n=缺口数,γ=空位罚分•亲缘空位罚分Wn=g+nγ,＝缺口数，γ=空位拓展罚分g=空位开放罚分简化比对统计我们怎样告诉别人基于分值的比对的好坏？当两个随机序列在比对时得到近似的分值的可能性有多大？考虑一个简单的问题－在随机的硬币投掷过程中，获得头像l的最大可能概率？均匀的硬币p＝0.5且ErdÖsandRényi–最大可能概率＝log1/p(n)这里log2(n).如果n=100,最大可能概率是6.65对长度分别为n和m的两个序列，我们做nm比对，这样预测的最长序列匹配将是log1/p(mn)更确确的说，期望值，或者最长匹配的平均值将是E(M)~=log1/p(Kmn)这里K是依赖于氨基酸组成的常数。…事实上，它仅对非空位局部比对有用且我们忽略了边际效应和错配的情况一些注释…•E(M)~=log1/p(Kmn)意思是当序列长度积的对数值越大匹配的长度越多。用氨基酸的替代矩阵，我们可以匹配长度转化为序列分值，S。•两个更常见的使用参数：λ=ln(1/p)和前面我们已经讨论过的参数K•我们想知道高分值对的数量，HSP(如：氨基酸的高分值)•HSPs的数值表示超过了由E=Kmne-λS计算的某一分值•因此我们通过期望得到的分值HSPs数量(如E值)来评估一个序列分值的好坏(它的S)。注意(内容)我们从哪里得到能告诉我们E值和关联性的分布函数？需要在一些随机比对序列的模型中查看那些分值…注意(内容)•随机序列比对将产生一个极值分布想一个•倾斜的高斯分布一样称为Gumbel极值分布对具有均值m和σ变量的正态分布，曲线的高度由Y=1/(σ√2π)exp[-(x-m)2/2σ2来表示对一个极值分布，曲线的高度由Y=exp[-x-e-x]…和P(Sx)=1-exp[-e-λ(x-u)]这里u=(lnKmn)/λ来表示由图有平均极端分值是~log2(nm),获得超过某一标准偏差X的分值的概率是：P(Sx)~Kmne-λx.***K和λ由不同的矩阵得到***对较小的统计包含：Kmne-λS•两种方法得到参数K和λ1－对很多氨基酸替代矩阵，Altschul和Gish对1