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

《生物信息学更多更有效的成对序列比对及多序列比对技巧探秘》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、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）是“多项式时间”只要K<3

2、……就容易处理考虑到非空位点阵全局比对：……本质上是一个O(mn)矩阵好的例子O(n)比O(nlog(n)),O(n2),O(n3)更好。糟糕的例子O(kn)=指数时间…….恐怖！！！！NP问题—不知道多项式时间解决办法=非确定性多项式问题。递归和动力学设计比对两个没有空位的蛋白序列—大概是一个O(mn)问题。没有空位—适合于计算天文学，直接比对方法不能做。(=22L/√(2πL);L=序列长度)可选择的办法是比对所有可能的特征对(配对和错配，也很好的考虑到了空位，保持比对的数量的易处理性。)这种方法也叫动力学设计。在算术上证明了产生最佳比对。需要置换或相似矩阵和

3、考虑到空位的方法。怎样记下比队得分的例子：写下两条序列序列#1序列#2置换矩阵得分得分=Σ（AA配对得分）-缺口处罚=15BLOSUM62得分矩阵得分系统应该：支持匹配识别或是相关氨基酸处罚错误匹配和空位。为了得到好的得分系统需要明确：在相关蛋白质与它的偶然产生相比较中，特殊氨基酸对被发现的几率。替代矩阵中就包含有这些信息……并且当有空位时，会有更好的选择。真实替代矩阵的起源：首先要知道在相关蛋白质中一个氨基酸替代另一个氨基酸的频率[=P(ab)]c/w。另一个氨基酸偶然产生替代的机会，是以蛋白质中每个氨基酸的相对频率为基础的，即q(a)和q(b)。这称为“不均几

4、率”：P(ab)/q(a)q(b)如果在比对中所有位置都进行了这种处理，那么总概率将会是每个位置不均几率的乘积……但是乘法耗费计算空间……因此…..取log(不均几率)再把它们相加，用此来代替。像PAM和BLOSUM矩阵就是取了不均几率的对数。也包含了反映相关蛋白质中的氨基酸替代的可能性的正数和负数。动力学设计过程：首先沿着侧边从上到下写下一个序列。注意—线形空位处罚：γ(n)=nA，其中A=空位处罚动力学设计过程：首先沿着侧边从上到下写下一个序列。空位空位因此得到S必须知道S(i-1,j-1)和S(i,j-ij1)andS(i-1,j)……因此需要回归。我们用解

5、决小问题的方法解决大问题。我们必须记录怎样得到S。例如表格式矩阵中的中ij间解答。计算机科学家称这为动力学设计，其中“设计”即矩阵，并不是某种计算机编码。动力学设计过程：首先沿着侧边从上到下写下一个序列。空位空位全局比对：Needleman-Wunsch-SellersO(n2)利用线形空位处罚最大：对角线从左到右从上到下动力学设计过程：首先沿着侧边从上到下写下一个序列。空位空位全局比对：Needleman-Wunsch-SellersO(n2)利用线形空位处罚最大：对角线从左到右从上到下动力学设计过程：首先沿着侧边从上到下写下一个序列。动力学设计过程：首先沿着侧

6、边从上到下写下一个序列。全局比对：Needleman-Wunsch-SellersO(n2)利用线形空位处罚最大：对角线从左到右从上到下动力学设计过程：首先沿着侧边从上到下写下一个序列。动力学设计过程：首先沿着侧边从上到下写下一个序列。源追踪：当正方形比对完成之后，从较低的右边开始，以后的工作根据箭头观察怎样到那儿……源追踪引起的比对：只有向后看才能理解生活，但是要生活好，必须向前看。—SørenKierkegaard局部比对TempleSmith和MichaelWaterman，1981—修改了Needleman-Wunsch-Sellers局部比对是从x序列

7、子列到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。比对就此结束Smi

8、th-Wa