东南大学吴健雄实验室.ppt

第三章（2） 序列多重比对,主讲人：孙 啸,制作人：刘志华,东南大学 吴健雄实验室,第三节 序列多重比对,目的： 发现多个序列的共性 发现与结构和功能相关的保守序列片段 设：有k个序列s1, s2, . ,sk，每个序列由同一个字母表中的字符组成，k大于2。 通过插入操作，使得各序列达到一样的长度。,1、SP（Sum-of-Pairs）模型,评价多重序列比对的结果,按照每个对比的列进行打分，然后加和 处理每一列： k个变量的打分函数 用一个k维数组来表示该显式函数（类似于打分矩阵） 期望： 函数在形式上应该简单 具有统一的形式 不随序列的个数而发生形式变化,其中，c1,c2,ck是一列中的k个字符，p是关于一对字符相似性的打分函数。,逐对加和SP（sum-of-pairs）函数,逐对计算p(1,2)，p (1,3)，.，p(1,8)，p (2,3)，p(2,4)，.， p (2,8)，.，p (7,8) 的所有得分 （-7-6-5-4-3-2-1）+2 = -26,另一种计算方式：先处理每一个序列对 在处理序列对时，逐个计算字符对，最后加和 则SP得分模型的计算公式如下：, 是一个多重比对 ij是由推演出来的序列s i 和s j的两两比对,2、多重比对的动态规划算法,多重序列比对的最终目标是通过处理得到一个得分最高（或代价最小）的序列对比排列，从而分析各序列之间的相似性和差异。,前趋节点的个数等于2k - 1,假设以k维数组A存放超晶格，则计算过程如下： a 0, 0, ,0 = 0 a i = max a i - b + SP-score(Column(s, i, b),(3-37),(3-38),if bj = 1,if bj = 0,图3.17 三维晶格节点计算依赖关系,问题： 计算量巨大 时间复杂度为O(2ki=1,.,k si) O(2kNk),3、 优化计算方法,标准动态规划算法存在的问题： 搜索空间大 剪枝技术：将搜索空间限定在一个较小的区域范围内。 若问题是搜索一条得分最高（或代价最小）的路径，则在搜索时如果当前路径的得分低于某个下限（或累积代价已经超过某个上限），则对当前路径进行剪枝，即不再搜索当前路径的后续空间。,经过特定断点的最优比对算法： 设有两条序列s、t，已知它们的两个断点分别是i、j 经过特定断点（i、j）的最优比对可分为两个部分： 0:s:i 与 0:t:j的最优比对 i:s:m与j:t:n的最优比对,序列S:,序列t:,j,i,为了得到特定断点的最优比对，用两个矩阵A和B ai, j = sim(0:s:i , 0:t:j) bi, 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）,图 （a）前缀矩阵；（b）总得分矩阵；（c）最优比对,（a）,（b）,定理3-1：设是关于s1, s2, . ,sk的最优比对，如果SP-score() L，则 score(ij) Lij 其中 Lij = L - ( sim(sx, sy) ) xy,(x,y)(i,j),分析一个节点是否处于可能最有路径上 即判断一个节点是否是相关的 判断依据： C=A+B 元素的值 超晶格中的一个节点 i = (i1, i2, , ik ) 如果对于所有的1 x y k，i 满足 cxyix, iy Lxy 则 i 是相关的,4、星形比对,星形比对的基本思想是：在给定的若干序列中，选择一个核心序列，通过该序列与其它序列的两两比对形成所有序列的多重比对，从而使得在核心序列和任何一个其它序列方向的投影是最优的两两比对。 利用标准的动态规划方法求出所有si和sc的最优两两比对 时间为O（kn2） 将这些两两比对聚集起来 并采用“只要是空白， 则永远是空白”的原则。,sc s1 s2 sk,(sc, s1) (sc, s2) (sc, sk),两两比对 多重比对,如何选择核心序列？ 尝试将每一个序列分别作为核心序列，进行星形多重序列比对，取比对结果最好的一个。 另一种方法是计算所有的两两比对，取下式值最大的一个： sim( si, sc ),例如，有5个序列： s1 = ATTGCCATT s2 = ATGGCCATT s3 = ATCCAATTTT s4 = ATCTTCTT s5 = ACTGACC,sc=s1,ATTGCCATT ATTGCCATT- ATTGCCATT ATTGCCATT ATGGCCATT ATC-CAATTTT ATCTTC-TT ACTGACC-,ATTGCCATT- ATGGCCATT- ATC-CAATTTT ATCTTC-TT- ACTGACC-,引理3.1： 对于所有的1i，jk，,ij, 有 dc(si, sj) D(si, sc) + D(sc, sj) （3-43）,定理3.2,（3-44）,星形比对是一种近似的方法，可以证明，用该方法所得到多重序列比对的代价不会大于最优多重序列比对代价的两倍,5、树形比对,k个待比对的序列 具有k个叶节点的树 每个叶节点对应一个序列 将序列赋予树的内部节点，可以计算树中每个分支的权值。 权值代表对应分支连接的两个序列之间的相似性。 所有权值的和就是这棵树 寻找一种树的内部节点序列赋予方式，使得树的得分最大。,将CT、CG、CT分别赋予节点x、y、z，则树的得分为8。 这里假设如果a=b，则p(a,b)=1， 否则p(a,b)=0，p(a,-)=-1。,CT,CG,CT,多重序列比对 两两序列比对 合并两个比对（比对的比对）,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-VLVC t2 VLHCL- t1 LHCLV- s3 GN-LVV AA算法的输出为 -H-LVV -G-VLVG -GN-LVV L-HC-LV- V-HC-L 分别对第1、2列和4、5列进行压缩，则最后结果为,HLVV GVLVG GNLVV LHCLV- VHCL-,对于n个序列的树形比对的基本算法过程如下： （1）初始化，对于每个序列，生成一个叶节点 （2）利用AA算法合并两个节点，形成一个新节 点，合并的结果放在新节点中，原来的两 个节点作为新节点的子节点 （3）反复执行（2），直到形成n个叶节点的树 根为止，根节点中的序列即为最终的多重 比对结果。,s1 s2 s3 s4,1,2,6、其它多重序列比对算法,一般渐进式比对方法所采用的过程： （1）先将多个序列进行两两比对，基于这些比较，计算得到一个距离矩阵，该矩阵反映每对序列的关系； （2） 利用距离矩阵，建立一棵“相关树”； （3）从最接近的一对序列出发，逐步归并形成比对的聚类，直到所有序列处理完。,例：,(LYCES, SPIOL 84), (YEAST, (XENLA, (RAT, MOUSE 96), HUMAN 83), CHICK 71) 66), DROVI 58),相关树,多序列比对,目前使用最广泛的多重序列比对程序是ClustalW ClustalW是一种渐进的比对方法，先将多个序列进行两两比对，基于这些比较，计算得到一个距离矩阵，该矩阵反映了每对序列的关系,EBI的CLUSTALW网址是： http:/www.ebi.ac.uk/clustalw/,7、统计特征分析,对于所得到的多重序列比对，我们往往需要进行归纳分析，总结这些序列的特征，或者给出这些序列共性的表示,HLVV GVLVG GNLVV LHCLV- VHCL-,（1）保守序列 表示序列每个位置上最可能出现的字符（或者所有可能出现的字符） ATNTSC (N - A,T,C,G ; S - G,C),（2）特征统计图（Profile） 令P=(P1,P2,PL)，P表示在的每一列上各种字符出现的概率分布 Pj=(pj0,pj1,pj|A|) A代表字母表，Pjk代表字母表A中第k个字符在第 j 列出现的概率。 第0个字符是特殊的空位符号“-”。,ATTAT AACTT CTTAT ACTTT AGAAT,1 2 3 4 5 (位置) A 0.8 0.2 0.2 0.6 0.0 T 0.0 0.4 0.6 0.4 1.0 C 0.2 0.2 0.