序列比对的一些算法思想.pptxVIP

序列比对的一些算法思想;一、序列比对的意义;二、序列比对的一般过程;（一）序列比对的得分系统;b.转换颠换矩阵（transition，transversion） （嘌呤：腺嘌呤A，鸟嘌呤G；嘧啶：胞嘧啶C，胸腺嘧啶T） b c c.BLAST矩阵 ;2，蛋白质打分矩阵 PAM矩阵（Point Accepted Mutation） ﹡ 基于进化位点突变模型，通过统计相似序列比对中的各种氨基酸替换发生率而得到该矩阵。 ﹡ PAM 概率矩阵?对数比值矩阵 （ Mab：a，b真实比对概率 Pb：随机情况下b比对的概率） ﹡序列相似度 = 40% 50% 60% | | | 打分矩阵 = PAM120 PAM80 PAM 60 PAM250 → 14% - 27% ;b. BLOSUM矩阵（Blocks Amino Acid Substitution Matrices） ﹡依据保守域模块建立，对氨基酸相似性不低于62%的蛋白质序列比对进行统计构建BLOSUM62 BLOSUM概率矩阵?对数比值矩阵 ﹡ ;BLOSUM62;3，空位罚分体系 a.线性罚分 b.仿射罚分（affine penalty） ;(二)序列比对算法;1，点阵法 ;2，动态规划算法 a. N-W算法是一种全局比对动态规划算法。 首先假设我们要对两条序列a和b进行比对，它们的长度分别为M和N，序列a的第i个字符（残基）为 ，序列b的第j个字符为 。动态规划算法由四部分组成：1）最优化的递归计算方法； 2）存储子问题的最优化的动态规划矩阵；3）给出自问题最优解的矩阵填充过程和4）寻找最优化比对路径的回溯方法。 ;b. S-W局部比对算法 局部比对的应用范围比全局比对更广。 S-W算法与N-W算法的区别在于多了一个去头去尾的操作。 去头，在动态规划矩阵的每个单元格的计算增加一条路径。也就是如果当前比对分数小于0，那么之前的比对全部去掉，比对从目前位置重新开始。 去尾，回溯的时候不是从最后开始，而是从最大的分数开始。 ;Algorithm: Similarity input: s and t; output: similarity between s and t ;Algorithm Align input: indices i, j , array a given by algorithm Similarity output: alignment in align-s, align-t, and length in len if i =0 and; j=0 then len=0 else if i 0 and a[i, j] = a[i-1, j] + g then Align(i - 1, j , len) len =len + 1 align-s[len] = s[i] align-t[len] =“-” else if i 0 and j 0 and a[i, j] = a[i-1, j-1] + p(i, j) then Align(i -1, j -1, len) len=len + 1 align-s[len]=s[i] align-t[len]= t[j] else // has to be j 0 and a[i, j] = a[i, j-1] + g Align(i, j-1, len) len = len + 1 align-s[len]=“-” align-t[len]=t[j] ;例1：利用S-W算法对两条DNA序列进行全局比对。a=ATTCCAAG，b=TTCGAGT，得分系统：｛4，-3，-4｝（匹配得4分，不匹配得－3分，空隙得－4分） 1）给动态规划矩阵赋初值。 ;2）按照最优化的递归算法填充动态规划矩阵。 ;3）从最后一个单元格开始，回溯最优化比对路径 ;例2：利用S-W算法对两条DNA序列进行局部比对。a=ATTCCAAG，b=TTCGAGT，得分系统：｛4，-3，-4｝（匹配得4分，不匹配得－3分，空隙得－4分） 1）给动态规划矩阵赋初值。 ;2）按照最优化的递归算法填充动态规划矩阵。 ;3）从矩阵中分值最大的单元格开始，回溯到0为止得到最优比对路径。 ;（三）序列比对