第四章序列分析.pptVIP

第四章序列分析;第三节 序列多重比对;目的： 发现多个序列的共性 发现与结构和功能相关的保守序列片段 设：有k个序列s1, s2, ... ,sk，每个序列由同一个字母表中的字符组成，k大于2。 通过插入操作，使得各序列达到一样的长度。;1、SP（Sum-of-Pairs）模型;按照每个对比的列进行打分，然后加和 处理每一列： — k个变量的打分函数 — 用一个k维数组来表示该显式函数（类似于打分矩阵） 期望： 函数在形式上应该简单 具有统一的形式 不随序列的个数而发生形式变化 ;其中，c1,c2,…,ck是一列中的k个字符，p是关于一对字符相似性的打分函数。;另一种计算方式：先处理每一个序列对 在处理序列对时，逐个计算字符对，最后加和 则SP得分模型的计算公式如下： ;第八页，共六十二页，2022年，8月28日;2、多重比对的动态规划算法; ; ;;3、 优化计算方法;经过特定断点的最优比对算法： 设有两条序列s、t，已知它们的两个断点分别是i、j 经过特定断点（i、j）的最优比对可分为两个部分： —— 0:s:i 与 0:t:j的最优比对 —— i:s:m与j:t:n的最优比对;为了得到特定断点的最优比对，用两个矩阵A和B a[i, j] = sim(0:s:i , 0:t:j) b[i, j] = sim(i:s:m , j:t:n) 矩阵A的计算和标准算法一样 矩阵B的计算则是反方向的，即先对B的最后一行和最后一列进行初始化，然后反向推进到（0，0）。 矩阵A与B的和C=A+B包含了在特定断点（i、j）的最优比对得分。称C矩阵为总得分矩阵，而A、B分别是前缀和后缀的得分矩阵。 根据C的最大值，可非常容易地找出最优比对所对应的路径。 ;-ATTCGG GATTC-- （c）;定理3-1：设?是关于s1, s2, ... ,sk的最优比对，如果SP-score(?) ? L，则 score(?ij) ? Lij 其中 Lij = L - ? ( sim(sx, sy) ) xy,(x,y)?(i,j);4、星形比对;sc s1 s2 … sk ;如何选择核心序列？ 尝试将每一个序列分别作为核心序列，进行星形多重序列比对，取比对结果最好的一个。 另一种方法是计算所有的两两比对，取下式值最大的一个： ? sim( si, sc ) ;例如，有5个序列： s1 = ATTGCCATT s2 = ATGGCCATT s3 = ATCCAATTTT s4 = ATCTTCTT s5 = ACTGACC ;引理3.1： 对于所有的1≤i，j≤k，,i?j, 有 dc(si, sj) ≤ D(si, sc) + D(sc, sj) （3-43）;5、树形比对;将CT、CG、CT分别赋予节点x、y、z，则树的得分为8。 这里假设如果a=b，则p(a,b)=1， 否则p(a,b)=0，p(a,-)=-1。 ; Alignment of alignments, AA算法 假设：有两个多重序列比对?1、?2， ?1代表序列s1、s2、…、si的多重比对， ?2代表序列t1、t2、…、tj的多重比对， （s1，s2，…，si）?（t1，t2，…，tj）=? ?代表s1和t1的两两比对，则计算与?相一致的?1和?2比对的算法如下 ： （1）标定?1的各列，如果s1在比对中对应位置的编辑操作不是插入或删除，则这些列分别标记为s1对应位置上的字符a1、a2、…、als1（ls1为序列s1的长度）； （2）标定?2的各列，如果t1在比对中对应的位置编辑操作不是插入或删除，则这些列分别标记为t1对应位置上的字符b1、b2、…、blt1（lt1为序列t1的长度）； （3）对a1、a2、…、als1和b1、b2、…、blt1进行比对； （4）在所得到的比对中，对于?1、?2和?中原来有插入或删除操作的位置，恢复其原有的实际字符或空位字符“-”。;例： ?1: s1 -H-LVV ?2: t1 L-HCLV ?：s1 -H-LVV s2 G