结构生物信息学4-多序列比对(1).ppt

生物信息学多序列比对 张法中国科学院计算技术研究所2013 3 31 Outline 多序列比对的意义多序列比对算法原理常见多序列比对应用程序介绍多序列比对的并行策略 什么是多序列比对 定义 有k个序列s1 s2 sk 每个序列由同一个字母表中的字符组成 k 2 序列所有字符的相对位置保持不变 通过插入 空位 操作 使得各序列达到一样的长度 从而形成这些序列的多重比对 多序列比对 多序列比对的应用 寻找蛋白质家族 识别多个序列的保守区域发现直系同源 Orthologs 与旁系同源 Paralogs 基因寻找同源基因 相似的序列往往具有同源性 辅助预测新序列的二级或三级结构可以直观地看到基因的哪些区域对突变敏感PCR引物设计分析多个序列的一致序列系统发育方法构建进化树 用于进化分析寻找个体之间单核苷酸多态性 SNPs 多序列比对 多序列比对的应用 多序列比对与进化研究例子 多序列比对 图中NYLS为树根 多序列比对的应用 多序列比对与进化研究例子 多序列比对 共变位点 保守位点 保守区域 Outline 多序列比对的意义多序列比对算法原理常见多序列比对应用程序介绍多序列比对的并行策略 多序列比对算法原理 多重比对的动态规划算法SP方法优化算法星型比对树形比对CLUSTALW算法 渐进算法 隐马尔可夫模型 多序列比对 算法原理 动态规划算法 多序列比对 多重序列比对的最终目标是通过处理得到一个得分最高 或代价最小 的序列对比排列 从而分析各序列之间的相似性和差异 两条序列比对的计算复杂度是N2多序列比对的计算复杂度呈指数增长 计算量巨大 无法实际应用 算法原理 动态规划算法 多序列比对 多序列比对的动态规划算法 算法原理 动态规划算法 多序列比对 多序列比对的动态规划算法 算法原理 动态规划算法 多序列比对 多序列比对的动态规划算法 算法原理 SP方法 为了找到最佳比对 并解决解决动态规则算法的计算复杂问题 Carrillo Lipman 1988 建立了SP SumofPairs 方法SP 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 4 3 2 1 2 26然后将一个多重比对所有列的得分全部加起来 其和即为该多重比对的得分 将所有多重比对的得分计算出来进行比较 得分最高的 应该是最好的 算法原理 SP方法 SP计算方法2 先计算多重序列结果的序列两两比对得分 多序列比对 是一个多重比对 ij是由 推演出来的序列si和sj的两两比对 方法1和方法2等价的条件 P 0 算法原理 SP方法 基于SP方法的多序列比对流程 多序列比对 计算所有双序列比对的分数用这些分数构建进化树基于进化树计算双序列比对权重基于进化树构建一个启发式多序列比对算法计算每一对双序列比对的最大权重 计算比对的空间位置以达到最佳比对完成最佳比对输出与最大权重 比较所获得的 慢且消耗大量内存最大可以比对8 9个长约250的氨基酸残基 算法原理 渐进算法 多序列比对 启发式算法 不一定保证最终能得到最优解 但在大多数情况下 其计算结果接近于最优结果 启发式算法 能够大大减少所需的计算时间 加快计算速度渐进算法 多重序列比对中常用的启发式方法 其基本思想是将序列多重比对转化为序列两两比对 逐渐将两两比对组合起来 最终形成完整的多序列比对 星形结构和树形结构 算法原理 星形比对 多序列比对 首先由Gusfield提出 在给定的若干序列中 选择一个核心序列 通过该序列与其它序列的两两比对形成所有序列的多重比对 从而使得 在核心序列和任何一个其它序列方向的投影是最优的两两比对 星形比对的基本思想 只要是空位 则永远是空位 逐步增加sc中的空位字符 以适应其他的比对 决不删除sc中已存在的空位字符 算法原理 星形比对 多序列比对 星形比对算法示意图 scs1s2 sk sc s1 sc s2 sc sk 算法原理 星形比对 多序列比对 如何选择核心序列 方法1 尝试将每一个序列分别作为核心序列 进行星形多重序列比对 取比对结果最好的一个 即SP得分最高的为最好 方法2 是计算所有的两两比对 取下式值最大的一个 算法原理 星形比对 多序列比对 有5个序列 s1 ATTGCCATTs2 ATGGCCATTs3 ATCCAATTTTs4 ATCTTCTTs5 ACTGACC sc s1 ATTGCCATTATTGCCATT ATTGCCATTATTGCCATTATGGCCATTATC CAATTTTATCTTC TTACTGACC s1 s2 s1 s3 s1 s4 s1 s5 ATTGCCATT ATGGCCATT ATC CAATTTTATCTTC TT ACTGACC 算法原理 树形比对 多序列比对 k个待比对的序列 具有k个叶节点的树每个叶节点对应一条序列将序列赋予树内部节点 计算树中每个分支的权值 权值代表对应分支连接的两个序列之间的相似性 所有权值的和就是这棵树的得分 树形比对 寻找一种树的内部节点序列赋予方式 使得树的得分最大 星形比对的基本思想 算法原理 树形比对 多序列比对 将CT CG CT分别赋予节点x y z 则树的得分为8 CT CG CT 多重序列比对 两两序列比对 合并两个比对 比对的比对 AligmentofAlignment AA算法 P a a 1P a b 0 a b P a P b 1 1 1 1 1 2 2 G TCATC GCTG 比对结果 打分函数 算法原理 树形比对 多序列比对 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和 中原来有插入或删除操作的位置 恢复其原有的实际字符或空位字符 a1a2a3a4 b1b2b3b4b5 算法原理 树形比对 多序列比对 对于n个序列的树形比对的基本算法过程如下 1 初始化 对于每个序列 生成一个叶节点 2 利用AA算法合并两个节点 形成一个新节点 合并的结果放在新节点中 原来的两个节点作为新节点的子节点 3 反复执行 2 直到形成n个叶节点的树根为止 根节点中的序列即为最终的多重比对结果 s1s2s3s4 1 2 算法原理 CLUSTAL算法 多序列比对 CLUSTAL算法是一种渐进的比对方法 它是由D G Higgins和P M Sharp于1988年首次提出的 目的 对来自不同物种的功能相同或相似的蛋白进行比对和聚类分析 可对这些物种的亲缘关系进行判断 并且对这些蛋白在生物进化过程中的保守性作出估计 算法原理 CLUSTAL算法 多序列比对 Clustal算法包括三个阶段 1 先将多重序列进行两两比对 基于这些比对 计算得到一个距离矩阵 该矩阵反映每对序列之间的关系 2 根据距离矩阵计算产生系统发育树 以此来确定被比较序列间相似的程度3 有了这棵系统发育树的指导 从关系最紧密的两条序列开始 逐步引入邻近的序列或序列组 并不断重新构建比对 直到所有序列都被加入为止 算法原理 CLUSTAL算法 多序列比对 实例 Hbb Human 人的 球蛋白Hbb Horse 马的 球蛋白Hba Human 人的 球蛋白Hba Horse 马的 球蛋白Myg phyca 抹香鲸的血红蛋白Glb5 petma 七鳃鳗蓝血红蛋白Lgb2 Luplu 羽扇豆的豆血红蛋白 已知三级结构的七个球蛋白序列 分别为 算法原理 CLUSTAL算法 多序列比对 实例 两两比对 构建距离矩阵 系统发育树的构建 渐进比对 算法原理 CLUSTAL算法 多序列比对 Clustal算法第1阶段 产生距离矩阵树 用完全动态规划法计算的7个球蛋白序列之间的7 7的距离矩阵 算法原理 CLUSTAL算法 多序列比对 Clustal算法第2阶段 构建系统发育树 根据第一阶段结果中的距离矩阵 用邻近归并法来计算产生一棵有分枝长度和序列权重的有根树 算法原理 CLUSTAL算法 多序列比对 Clustal算法第3阶段 渐进的比对 通过一系列两两比对来构建更大的比对序列组 按照指导树中的分支顺序 从有根树的末梢到树根逐渐进行 1 对 2 3 对 4 8 对 9 5 对 10 6 对 11 7 对 12 13 算法原理 CLUSTAL算法 多序列比对 实例 算法原理 Tcoffee算法 多序列比对 Tcoffee算法包括四个阶段 采用Clustal计算两两序列之间的全局最优比对结果 采用LALIGN计算两两序列之间的局部最优比对 设计加权系统 综合考虑以上两类结果的因素 构建指导库 最后 采用渐进式比对算法 得到最终的结果 算法原理 Tcoffee算法 多序列比对 同时进行全局和局部的两两序列比对 对以上打分的结果设计权重系统 找到序列中最保守的部分 渐进方法的比对 基于上述计算的primarylibrary 算法原理 渐进算法 多序列比对 渐进算法存在的问题 如果有两组序列AB和CD 他们的距离非常接近 哪组最先比对 以谁为基准 Seq1 ARKCVSeq2 ARCVSeq3 AKCV 若Seq1 2先比对 再加入Seq3 ARKCVAR CVA KCV ARKCVA RCVA KCV ARKCVAR CVAK CV 若Seq1 3先比对 再加入Seq3 若Seq2 3先比对 再加入Seq1 算法原理 迭代算法PRRP 多序列比对 1 先用 渐进 算法进行多序列比对 2 基于多序列比对的结果构建进化树 3 重新计算序列之间的距离 再用 渐进 算法进行多序列比对 4 重复上述步骤 直到结果不再发生改变为止 算法原理 迭代算法DiAlign 多序列比对 1 对所有序列进行两两之间的局部最优化的比对 2 找到所有能够匹配的部分M1 将重叠的 前后连续的匹配部分连接起来 diagonals 为M2 3 将剩下的未比对的序列重新比对 再发现能够匹配的部分 构成新M1 将连续部分构成M2 4 重复上述步骤 直到结果收敛 算法原理 统计学方法 多序列比对 隐马尔科夫模型 定义 一种统计模型 它考虑有关匹配 错配和间隔的所有可能的组合来生成一组序列排列HMM用来序列分析 产生概形HMM 分析序列组成和模式并通过预测开放阅读框 OpenReadingFrame ORF 来定位基因及预测蛋白质结构原理 先产生一个序列家族模型 并用先验信息初始化 然后用一组序列 序列条数 20 来训练HMM模型 训练过程中包括的序列越多 分析的精确性越高 算法原理 统计学方法 多序列比对 隐马尔科夫模型 优点 植根于概率论 无须序列的顺序信息 无需插入 缺失和罚分 可以用到很多先验信息缺点 需要至少20条序列 有时需要更多才能了解进化历史分析工具 HMMER http hmmer wustl edu Pfam http www sanger ac uk Software Pfam proteindomainalignmentsandprofileHMMs 算法原理 统计学方法 多序列比对 隐马尔科夫模型 图中 方形代表匹配状态 主状态 即输出的氨基酸和基本序列中对应的氨基酸匹配 圆形表示删除或缺失状态 即从原始蛋白质序列中去掉一个特定的氨基酸 菱形表示氨基酸的插入 即在原始蛋白质序列插入一个氨基酸 各状态间的箭头表示状态间的转换途径 注意 不同的参数会使模型以不同的概率产生新的氨基酸 一个训练好的模型可以代表有共同特征的蛋白质序列 算法原理 统计学方法 多序列比对 隐马尔科夫模型 NKYLT是通过BEG M1 I1 M2 M3 M4 END 算法原理 统计学方法 多序列比对 HMM模型 多序列比对 相关序列选取 模型构建 模型训练 参数调整 应用 确立模型 算法原理 MUSCLE算法 多序列比对 算法分为三个部分 每个部分相对独立 1 Draftprogressive 1 对两条序列 计算距离采用k mer的思想 2 用UPGMA算法构建引导树 3 使用渐进算法进行多序列比对 两条序列之间的距离不