东南大学 吴健雄实验室第三节第三节 序列多重比对序列多重比对目的：目的： 发现多个序列的共性发现多个序列的共性 发现与构造和功能相关的保守序列片段发现与构造和功能相关的保守序列片段设：有设：有k个序列个序列s1, s2, . ,sk，每个序列，每个序列由同一个字母表中的字符组成，由同一个字母表中的字符组成，k大于大于2。经过插入操作，使得各序列到达一样的经过插入操作，使得各序列到达一样的长度。长度。1、SPSum-of-Pairs模型模型评价多重序列比对的结果评价多重序列比对的结果按照每个按照每个对比的列比的列进展打分，然后加和展打分，然后加和处置每一列：置每一列： k个个变量的打分函数量的打分函数 用一个用一个k维数数组来表示来表示该显式函数式函数类似于打似于打分矩分矩阵期望：期望：函数在方式上函数在方式上应该简单具有一致的方式具有一致的方式不随序列的个数而不随序列的个数而发生方式生方式变化化 其中，c1,c2,ck是一列中的k个字符，p是关于一对字符类似性的打分函数。逐对加和逐对加和SPsum-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 = 1if 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: ji 为了得到特定断点的最优比对，用两个矩阵为了得到特定断点的最优比对，用两个矩阵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的最大值，可非常容易地找出最优比对所对应的途径。的最大值，可非常容易地找出最优比对所对应的途径。 -ATTCGGGATTC- 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的最的最优两两比两两比对时间为Okn2将将这些两两比些两两比对聚集起来聚集起来并采用并采用“只需是空白，只需是空白， 那么永那么永远是空白的原那么。是空白的原那么。scs1s2sk(sc, s1) (sc, s2) (sc, sk)两两比对两两比对 多重比对多重比对如何选择中心序列？尝试将每一个序列分别作为中心序列，进展星形多重序列比对，取比对结果最好的一个。另一种方法是计算一切的两两比对，取下式值最大的一个： sim( si, sc )例如，有5个序列： s1 = ATTGCCATT s2 = ATGGCCATT s3 = ATCCAATTTT s4 = ATCTTCTT s5 = ACTGACCsc=s1ATTGCCATT ATTGCCATT- ATTGCCATT ATTGCCATTATGGCCATT 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。 CTCGCT多重序列比多重序列比对 两两序列比两两序列比对 合并两个比合并两个比对比比对的比的比对Alignment of alignments, AA算法算法 假假设：有两个多重序列比：有两个多重序列比对1、2，1代表序列代表序列s1、s2、si的多重比的多重比对，2代表序列代表序列t1、t2、tj的多重比的多重比对，s1，s2，sit1，t2，tj=代表代表s1和和t1的两两比的两两比对，那么，那么计算与算与相一致的相一致的1和和2比比对的算法如下的算法如下 ：1标定定1的各列，假的各列，假设s1在比在比对中中对应位置的位置的编辑操作不操作不是插入或是插入或删除，那么除，那么这些列分些列分别标志志为s1对应位置上的字符位置上的字符a1、a2、als1ls1为序列序列s1的的长度；度；2标定定2的各列，假的各列，假设t1在比在比对中中对应的位置的位置编辑操作不操作不是插入或是插入或删除，那么除，那么这些列分些列分别标志志为t1对应位置上的字符位置上的字符b1、b2、blt1lt1为序列序列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-LVVAA算法的算法的输出出为-H-LVV-G-VLVG-GN-LVVL-HC-LV-V-HC-L分分别对第第1、2列和列和4、5列列进展展紧缩，那么最后，那么最后结果果为HLVVGVLVGGNLVVLHCLV-VHCL- 对于对于n个序列的树形比对的根本算法过程如下：个序列的树形比对的根本算法过程如下：1初始化，对于每个序列，生成一个叶节点初始化，对于每个序列，生成一个叶节点2利用利用AA算法合并两个节点，构成一个新节算法合并两个节点，构成一个新节 点，合并的结果放在新节点中，原来的两点，合并的结果放在新节点中，原来的两 个节点作为新节点的子节点个节点作为新节点的子节点3反复执行反复执行2，直到构成，直到构成n个叶节点的树个叶节点的树 根为止，根节点中的序列即为最终的多重根为止，根节点中的序列即为最终的多重 比对结果。比对结果。 s1 s2 s3 s411226、其它多重序列比对算法、其它多重序列比对算法普通普通渐进式比式比对方法所采用的方法所采用的过程：程：1先将多个序列先将多个序列进展两两比展两两比对，基于，基于这些比些比较，计算得到一个算得到一个间隔矩隔矩阵，该矩矩阵反映每反映每对序序列的关系；列的关系；2 利用利用间隔矩隔矩阵，建立一棵，建立一棵“相关相关树；3从最接近的一从最接近的一对序列出序列出发，逐，逐渐归并构成并构成比比对的聚的聚类，直到一切序列，直到一切序列处置完。置完。例：例：(LYCES, SPIOL 84), (YEAST, (XENLA,(RAT, MOUSE 96), HUMAN 83), CHICK71) 66), DROVI 58)相关树相关树多序列比对多序列比对目前运用最广泛的多重序列比对程序是ClustalW ClustalW是一种渐进的比对方法，先将多个序列进展两两比对，基于这些比较，计算得到一个间隔矩阵，该矩阵反映了每对序列的关系 EBI的CLUSTALW网址是： ebi.ac.uk/clustalw/ 7、统计特征分析、统计特征分析对于所得到的多重序列比对，我们往往需求进展归纳分析，对于所得到的多重序列比对，我们往往需求进展归纳分析，总结这些序列的特征，或者给出这些序列共性的表示总结这些序列的特征，或者给出这些序列共性的表示 HLVVGVLVGGNLVVLHCLV-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个字符是特殊的空位符号个字符是特殊的空位符号“-。 ATTATAACTTCTTATACTTTAGAAT 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.2 0.0 0.0 G 0.0 0.2 0.0 0.0 0.0 碱基碱基利用保守序列或者特征利用保守序列或者特征统计图可以判可以判别一个序列能否一个序列能否满足足一定的特征一定的特征给定一个序列定一个序列s=a1a2am，定，定义字符字符a在第在第j位的代价位的代价为 其中，其中，|A|代表字母表代表字母表A的的长度，度，Ak代表代表A的第的第k个字符，个字符，特特别地地A0代表空缺字符代表空缺字符“-。整个序列。整个序列s的代价的代价为一条序列与特征统计图相对照，假设代价值小，阐明该序一条序列与特征统计图相对照，假设代价值小，阐明该序列具有相应的特征，否那么该序列不具备相应的特征。列具有相应的特征，否那么该序列不具备相应的特征。