结构生物信息学4-多序列比对

《结构生物信息学4-多序列比对》由会员分享，可在线阅读，更多相关《结构生物信息学4-多序列比对（50页珍藏版）》请在金锄头文库上搜索。

1、生物信息学 多序列比对,张 法 中国科学院计算技术研究所 2013-3-31,Outline,多序列比对的意义 多序列比对算法原理 常见多序列比对应用程序介绍 多序列比对的并行策略,什么是多序列比对,定义：有k个序列s1, s2, . ,sk，每个序列由同一个字母表中的字符组成，k2，序列所有字符的相对位置保持不变，通过插入“空位”操作，使得各序列达到一样的长度，从而形成这些序列的多重比对。,多序列比对,多序列比对的应用,寻找蛋白质家族，识别多个序列的保守区域 发现直系同源(Orthologs)与旁系同源(Paralogs)基因 寻找同源基因(相似的序列往往具有同源性) 辅助预测新序列的二级或

2、三级结构 可以直观地看到基因的哪些区域对突变敏感 PCR引物设计 分析多个序列的一致序列 系统发育方法构建进化树，用于进化分析 寻找个体之间单核苷酸多态性(SNPs) ,多序列比对,多序列比对的应用,多序列比对与进化研究例子,多序列比对,图中NYLS为树根,多序列比对的应用,多序列比对与进化研究例子,多序列比对,共变位点,保守位点,保守区域,Outline,多序列比对的意义 多序列比对算法原理 常见多序列比对应用程序介绍 多序列比对的并行策略,多序列比对算法原理,多重比对的动态规划算法 SP方法 优化算法 星型比对 树形比对 CLUSTALW算法（渐进算法） 隐马尔可夫模型,多序列比对,算法原

3、理 动态规划算法,多序列比对,多重序列比对的最终目标是通过处理得到一个得分最高（或代价最小）的序列对比排列，从而分析各序列之间的相似性和差异。 两条序列比对的计算复杂度是N2 多序列比对的计算复杂度呈指数增长，,计算量巨大，无法实际应用,算法原理 动态规划算法,多序列比对,多序列比对的动态规划算法,算法原理 动态规划算法,多序列比对,多序列比对的动态规划算法,算法原理 动态规划算法,多序列比对,多序列比对的动态规划算法,算法原理 SP方法,为了找到最佳比对，并解决解决动态规则算法的计算复杂问题，Carrillo & Lipman (1988)建立了SP(Sum of Pairs)方法 SP (

4、Sum-of-Pairs) 方法：通过对一个随机矩阵中氨基酸对的所有可能组合的记分求和来获得矩阵得分 SP计算可分为两种方法。,多序列比对,算法原理 SP方法,SP计算方法1：先计算多重比对结果的每一列字符的得分,多序列比对,其中，c1,c2,ck是一列中的k个字符， p是关于一对字符相似性的打分函数。 SP_score(c1,c2,ck)是多重序列比对中某一列 的得分.,算法原理 SP方法,SP计算方法1：计算多重比对每一列的SP得分,多序列比对,逐对计算p(1,2)，p (1,3)，.，p(1,8)，p (2,3)，p(2,4)，.p(2,8) .，p(7,8) 的所有得分：（-7-6-5

5、-4-3-2-1）+2 = -26 然后将一个多重比对所有列的得分全部加起来，其和即为该多重比对的得分。 将所有多重比对的得分计算出来进行比较，得分最高的，应该是最好的。,算法原理 SP方法,SP计算方法2：先计算多重序列结果的序列两两比对得分,多序列比对, 是一个多重比对 ij是由推演出来的序列si和sj的两两比对,方法1和方法2等价的条件：P(-,-)=0,算法原理 SP方法,基于SP方法的多序列比对流程：,多序列比对,计算所有双序列比对的分数 用这些分数构建进化树 基于进化树计算双序列比对权重 基于进化树构建一个启发式多序列比对算法 计算每一对双序列比对的最大权重 计算比对的空间位置以达

6、到最佳比对 完成最佳比对 输出与最大权重比较所获得的,慢且消耗大量内存 最大可以比对8-9 个长约250的氨基酸残基,算法原理 渐进算法,多序列比对,启发式算法：不一定保证最终能得到最优解，但在大多数情况下，其计算结果接近于最优结果； 启发式算法：能够大大减少所需的计算时间，加快计算速度 渐进算法：多重序列比对中常用的启发式方法。其基本思想是将序列多重比对转化为序列两两比对，逐渐将两两比对组合起来，最终形成完整的多序列比对。 星形结构和树形结构,算法原理 星形比对,多序列比对,首先由Gusfield 提出。 在给定的若干序列中，选择一个核心序列，通过该序列与其它序列的两两比对形成所有序列的多重

7、比对 ，从而使得 在核心序列和任何一个其它序列方向的投影是最优的两两比对。,星形比对的基本思想：,只要是空位，则永远是空位； 逐步增加sc中的空位字符，以适应其他的比对； 决不删除sc中已存在的空位字符。,算法原理 星形比对,多序列比对,星形比对算法示意图,sc s1 s2 sk,(sc, s1) (sc, s2) (sc, sk),算法原理 星形比对,多序列比对,如何选择核心序列？,方法1：尝试将每一个序列分别作为核心序列， 进行星形多重序列比对，取比对结果最 好的一个。即SP得分最高的为最好。 方法2：是计算所有的两两比对，取下式值最大 的一个：,算法原理 星形比对,多序列比对,有5个序列

8、： s1 = ATTGCCATT s2 = ATGGCCATT s3 = ATCCAATTTT s4 = ATCTTCTT s5 =ACTGACC,sc=s1,ATTGCCATT ATTGCCATT- ATTGCCATT ATTGCCATT ATGGCCATT ATC-CAATTTT ATCTTC-TT ACTGACC- (s1,s2) (s1,s3) (s1,s4) (s1,s5),ATTGCCATT- ATGGCCATT- ATC-CAATTTT ATCTTC-TT- ACTGACC-,算法原理 树形比对,多序列比对,k个待比对的序列 具有k个叶节点的树 每个叶节点对应一条序列 将序列赋予

9、树内部节点，计算树中每个分支的权值，权值代表对应分支连接的两个序列之间的相似性。所有权值的和就是这棵树的得分。 树形比对： 寻找一种树的内部节点序列赋予方式， 使得树的得分最大。,星形比对的基本思想：,算法原理 树形比对,多序列比对,将CT、CG、CT分别赋予节点 x、y、z，则树的得分为8。,CT,CG,CT,多重序列比对 两两序列比对 合并两个比对（比对的比对） Aligment of AlignmentAA算法,P（a,a）=1 P（a,b）= 0 （ab） P（a,-）=P（-,b）= -1,1,1,1,1,2,2,G - T C A T C - G C T G,比对结果：,打分函数,

10、算法原理 树形比对,多序列比对,AA算法概述-1：,假设有两个多重比对1和2 1代表序列s1,s2,si的多重比对 2代表序列t1,t2,tj的多重比对 并且,( s1,s2,si ) ( t1,t2,tj )= 代表s1和t1的两两比对, 则 计算与相一致的1 和2比对的算法如下:,算法原理 树形比对,多序列比对,AA算法概述-2：,标定1的各列中不为空位的字符: a1,a2,al1 s1=l1 标定2的各列中不为空位的字符: b1,b2,bl2 t1=l2 对a1,a2,al1 和b1,b2,bl2 进行比对, 在所得到的比对中,对于1、2和中原来有插入或删除操作的位置, 恢复其原有的实际

11、字符或空位字符”-”.,a1 a2a3a4,b1 b2b3b4b5,算法原理 树形比对,多序列比对,对于n个序列的树形比对的基本算法过程如下： （1）初始化，对于每个序列，生成一个叶节点 （2）利用AA算法合并两个节点，形成一个新节点， 合并的结果放在新节点中，原来的两个节点作为 新节点的子节点 （3）反复执行（2），直到形成n个叶节点的树根为止， 根节点中的序列即为最终的多重比对结果。,s1 s2 s3 s4,1,2,算法原理 CLUSTAL算法,多序列比对,CLUSTAL 算法是一种渐进的比对方法，它是由 D.G.Higgins和 P.M.Sharp 于1988年首次提出的。,目的： 对来

12、自不同物种的功能相同或相似的蛋白进行比对 和聚类分析，可对这些物种的亲缘关系进行判断，并且 对这些蛋白在生物进化过程中的保守性作出估计。,算法原理 CLUSTAL算法,多序列比对,Clustal算法包括三个阶段：,1. 先将多重序列进行两两比对。基于这些比对，计算得到 一个距离矩阵，该矩阵反映每对序列之间的关系。 2. 根据距离矩阵计算产生系统发育树，以此来确定被比较 序列间相似的程度 3. 有了这棵系统发育树的指导，从关系最紧密的两条序列 开始，逐步引入邻近的序列或序列组，并不断重新构建 比对，直到所有序列都被加入为止。,算法原理 CLUSTAL算法,多序列比对,实例：,Hbb_Human

13、: 人的-球蛋白 Hbb_Horse : 马的-球蛋白 Hba_Human : 人的-球蛋白 Hba_Horse : 马的-球蛋白 Myg_phyca : 抹香鲸的血红蛋白 Glb5_petma : 七鳃鳗蓝血红蛋白 Lgb2_Luplu : 羽扇豆的豆血红蛋白,已知三级结构的七个球蛋白序列，分别为：,算法原理 CLUSTAL算法,多序列比对,实例：,两两比对，构建距离矩阵,系统发育树的构建,渐进比对,算法原理 CLUSTAL算法,多序列比对,Clustal算法第1阶段：产生距离矩阵树,用完全动态规划法计算的7个球蛋白序列之间的77的距离矩阵,算法原理 CLUSTAL算法,多序列比对,Clus

14、tal算法第2阶段：构建系统发育树,根据第一阶段结果中的距离矩阵，用邻近归并法来计算产生一棵有分枝长度和序列权重的有根树。,算法原理 CLUSTAL算法,多序列比对,Clustal算法第3阶段：渐进的比对,通过一系列两两比对来构建更大的比对序列组。按照指导树中的分支顺序，从有根树的末梢到树根逐渐进行,(1)对(2) (3)对(4) (8)对(9) (5)对(10) (6)对(11) (7)对(12) (13),算法原理 CLUSTAL算法,多序列比对,实例：,算法原理 Tcoffee算法,多序列比对,Tcoffee算法包括四个阶段：,采用Clustal计算两两序列之间的全局最优比对结果； 采用

15、LALIGN计算两两序列之间的局部最优比对； 设计加权系统，综合考虑以上两类结果的因素，构建指导库； 最后，采用渐进式比对算法，得到最终的结果。,算法原理 Tcoffee算法,多序列比对,同时进行全局和局部的两两序列比对,对以上打分的结果设计权重系统，找到序列中最保守的部分,渐进方法的比对，基于上述计算的primary library,算法原理 渐进算法,多序列比对,渐进算法存在的问题：,如果有两组序列AB和CD，他们的距离非常接近，哪组最先比对？以谁为基准？,Seq1: ARKCV Seq2: ARCV Seq3: AKCV,若Seq1,2先比对，再加入Seq3：,ARKCV AR-CV A-KCV,ARKCV A-RCV A-KCV,ARKCV AR-CV AK-CV,若Seq1,3先比对，再加入Seq3：,若Seq2,3先比对，再加入Seq1：,算法原理 迭代算法PRRP,多序列比对,1. 先用“渐进”算法进行多序列比对; 2. 基于多序列比对的结果构建进化树； 3. 重新计算序列之间的距离，再用“渐进”算法进行多序列比对； 4. 重复上述步骤，直到结果不再发生改变为止。,算法原理 迭代算法DiAlign,多序列比对,1. 对所有序列进行两两之间的