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

第三节 序列多重比对 1、SP（Sum-of-Pairs）模型 2、多重比对的动态规划算法 3、 优化计算方法 4、星形比对 星形比对的基本思想是：在给定的若干序列中，选择一个核心序列，通过该序列与其它序列的两两比对形成所有序列的多重比对?，从而使得?在核心序列和任何一个其它序列方向的投影是最优的两两比对。 利用标准的动态规划方法求出所有si和sc的最优两两比对 时间为O（kn2） 将这些两两比对聚集起来 并采用“只要是空白， 则永远是空白”的原则。 sc s1 s2 … sk 如何选择核心序列？ 尝试将每一个序列分别作为核心序列，进行星形多重序列比对，取比对结果最好的一个。 另一种方法是计算所有的两两比对，取下式值最大的一个： ? sim( si, sc ) 例如，有5个序列： s1 = ATTGCCATT s2 = ATGGCCATT s3 = ATCCAATTTT s4 = ATCTTCTT s5 = ACTGACC 5、树形比对 6、其它多重序列比对算法 一般渐进式比对方法所采用的过程： （1）先将多个序列进行两两比对，基于这些比较，计算得到一个距离矩阵，该矩阵反映每对序列的关系； （2） 利用距离矩阵，建立一棵“相关树”； （3）从最接近的一对序列出发，逐步归并形成比对的聚类，直到所有序列处理完。 例： 目前使用最广泛的多重序列比对程序是ClustalW ClustalW是一种渐进的比对方法，先将多个序列进行两两比对，基于这些比较，计算得到一个距离矩阵，该矩阵反映了每对序列的关系 利用保守序列或者特征统计图可以判断一个序列是否满足一定的特征 给定一个序列s=a1a2…am，定义字符a在第j位的代价为 其中，|A|代表字母表A的长度，Ak代表A的第k个字符，特别地A0代表空缺字符“-”。整个序列s的代价为 多序列比对 EBI的CLUSTALW网址是： http://www.ebi.ac.uk/clustalw/ 7、统计特征分析 对于所得到的多重序列比对，我们往往需要进行归纳分析，总结这些序列的特征，或者给出这些序列共性的表示 —H—LVV G—VLVG GN—LVV 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.2 0.0 0.0 G 0.0 0.2 0.0 0.0 0.0 （碱基） 一条序列与特征统计图相对照，如果代价值小，说明该序列具有相应的特征，否则该序列不具备相应的特征。 * * 东南大学 吴健雄实验室 目的： 发现多个序列的共性 发现与结构和功能相关的保守序列片段 设：有k个序列s1, s2, ... ,sk，每个序列由同一个字母表中的字符组成，k大于2。 通过插入操作，使得各序列达到一样的长度。 评价多重序列比对的结果 按照每个对比的列进行打分，然后加和 处理每一列： — 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 另一