多序列比对研究生生物信息学课件06.ppt

多序列比对 MultipleAlignments 寻找蛋白质家族 识别保守区与可变区功能预测 相似的蛋白质序列往往具有相似的结构与功能结构预测 辅助预测新序列的二级或三级结构可以直观地看到基因的哪些区域对突变敏感系统发育分析 我们为什么做多序列比对 一个多序列比对例子 VTISCTGSSSNIGAG NHVKWYQQLPGVTISCTGTSSNIGS ITVNWYQQLPGLRLSCSSSGFIFSS YAMYWVRQAPGLSLTCTVSGTSFDD YYSTWVRQPPGPEVTCVVVDVSHEDPQVKFNWYVDG ATLVCLISDFYPGA VTVAWKADS AALGCLVKDYFPEP VTVSWNSG VSLTCLVKGFYPSD IAVEWWSNG 多序列比对与进化研究例子 图中NYLS为树根 多序列比对方法 全局序列比对动态规划算法 DynamicProgrammingAlgorithm 分而治之方法 DivideandConquerMethods SP方法 SumofPairsMethods 累进方法 ProgressiveMethods 迭代方法 IterativeMethods 遗传算法 GeneticAlgorithms 局部序列比对概形分析 ProfileAnalysis 区块分析 BlockAnalysis 统计学方法 StatisticalMethods 多序列比对总体思路 在多序列比对前要考虑的问题 比对的优劣与序列条数正相关避免在比对中包括相似度差异过大的序列每个亚群应分别先比对 然后再整体比对 全局序列比对 动态规划算法 DynamicProgrammingAlgorithm 分而治之方法 DivideandConquerMethods SP方法 SumofPairsMethods 累进方法 ProgressiveMethods 迭代方法 IterativeMethods 遗传算法 GeneticAlgorithms 序列长度为n的双序列比对n2比对比对数目成指数增长例如 序列长度为n 序列数为N的多序列比对数目是nN对于数目较少且较短的序列来说都不切实际 动态规划算法 DynamicProgramming Sequence1 Sequence2 Sequence3 多维的动态规划算法 分而治之 DivideandConquer DCA 方法 Stoye etal 1997 将MSA的空间复杂度减小DCA在线MSAhttp bioweb pasteur fr seqanal interfaces dca simple html 分而治之方法 Soineffect Sequence1 Sequence2 Sequence3 SP SumofPairs 方法 为了找到最佳比对 并解决解决动态规则算法的计算复杂问题 Carrillo Lipman 1988 发明了SP SumofPairs 方法SP方法通过对一个随机数据矩阵中氨基酸对的所有可能组合的记分求和来获得矩阵记分 SP方法例子 使用BLOSUM62矩阵 空位罚分为 8在第一列 有三种两两比对组合方式 S SS S每一列有k k 1 2个双序列比对 8 8 4 12 计算所有双序列比对的分数用这些分数构建进化树基于进化树计算双序列比对权重基于进化树构建一个启发式多序列比对 HeuristicAlignment 计算每一对双序列比对的最大权重 计算比对的空间位置以达到最佳比对完成最佳比对输出与最大权重 比较所获得的 慢且消耗大量内存最大可以比对8 9个长约250的氨基酸残基 基于SP方法的MSA程序 针对基于动态规划算法的MSA程序比对序列数目有限 Feng Doolittle 1987 发明了累进算法 主要思想 通过双序列比对构建进化关系 并通过这种关系来构建序列比对 CLUSTAL和PILEUP是目前常用的基于累进算法的比对软件 CLUSTAL是免费软件 目前应用非常广泛 分为基于文本的CLUSTALW和图形用户界面的CLUSTALXhttp www igbmc u strasbg fr BioInfo ClustalX Top html T Coffee是一种新的基于CLUSTAL的程序 它在比对关系较远的序列时较CLUSTAL更具优势 但速度较CLUSTAL要慢 累进算法 ProgressiveMethods 1对所有序列做双序列比对 构建距离矩阵计算相似性分数值 2基于双序列距离矩阵 构建一个进化树 3依据进化树进行渐进比对 依据进化树 开始对关系较近的序列进行两两比对 逐渐加入关系较远的序列进行比对 构建多序列比对 Multiplealignment Scerevisiae 1 Celegans 2 0 640Drosophia 3 0 6340 327Human 4 0 6300 4080 420Mouse 5 0 6190 4050 4690 289 累进算法原理 一般的累进比对方法 1 3 2 5 1 3 1 3 1 3 2 5 2 5 4 d root 果仁糖累进方法 Pralineprogressivestrategy 1 3 2 1 3 1 3 1 3 2 5 2 5 4 d 4 累进算法的一些问题 比对的准确性高度依赖于开始选择的双序列比对序列关系越远发生的错误可能越高选择合适的打分矩阵和罚分准则较困难 ClLUSTALW X简介 ClLUSTAL是用于MSA分析的最为流行的软件用来多序列比对 概形 Profile 分析和创建进化树ClLUSTAL最初初由Higgins等于1988年创立并不断完善ClLUSTAL分为ClLUSTALW和CLUSTALX两种类型 这两种软件核心功能完全相同 区别在于ClLUSTALX为图形界面 而ClLUSTALW保留以前的非图形平台ClLUSTAL有用于WINDOWS和UNIX LINUX的各种版本 CLUSTAL方法 进行所有序列间的双序列比对基于双序列比对分数产生一个相邻连接进化树 neighbor jointree 根据进化树提供的序列间关系按顺序对序列进行比对先排最相近序列 再添加其它的序列产生一个MSA来显示每列的序列变异初期比对可通过一种与FASTA相似的较快的k tuple模型寻找或动态规则算法来进行产生进化树的过程中需要计算序列间的遗传距离 错配对位置的数目与比对位置的总数的比值 空位除外 比对可以用以下两种方法 slow accurate fast approximate ClustalX ClustalX ClustalX ClustalX ClustalX Example Multiplesequencealignmentof7neuroglobinsusingclustalx PILEUP PILEUP是GCG GeneticsComputerGroup 软件包中的MSA分析工具与CLUSTAL一样使用累进式整体比对方法 ProgressiveGlobalAlignment PILEUP开始的双序列比对使用Needleman Wunsch动态规划算法 所以是全局序列比对 善于比较相似度较高的序列 OutputofPileup 401OATNFA1TTCAG ACACTCAGGTCATCTTCTCAAGCOATNFARTTCAG ACACTCAGGTCATCTTCTCAAGCBSPTNFATTCAA ACACTCAGGTCCTCTTCTCAAGCCEU14683TTCAG ACCCTCAGGTCATCTTCTCAAGCHSTNFRCCCAG GCAGTCAGATCATCTTCTCGAACSYNTNFTRPCCCAG GCAGTCAGATCATCTTCTCGAACCATTNFAACCCAG ACACTCAGATCATCTTCTCGAACCFTNFATCCAG ACAGTCAAATCATCTTCTCGAACRABTNFMCCCAGATGGTCACCCTCAGATCAGCTTCTCGGGCRNTNFAACCCAGACCCTCACACTCAGATCATCTTCTCAAAA OutputofPileup ClUSTAL和PILEUP存在的问题 最终的比对结果取决于最初的双序列比对 起初的序列相似度越高比对越准确如果比对序列间长度差异较大则会生成异常的引导树 guidetrees 从而严重影响多序列比对所选的记分与罚分标准并不一定适合一组序列中的所有序列 针对累进比对方法的不足产生了迭代方法迭代方法策略在比对过程中不断重新比对各亚组序列把亚组序列再排成包括所有序列在内的整体比对获得最优的总比对分数 由成对比对分数相加而成 迭代方法 IterativeMethods 迭代方法程序 MultAlin Corpet1988 在累进比对的过程中重新计算成对比对的分数根据这些分数来完善比对记分的进化树DIALIGN在双序列比对中使用对角点阵图找到不包含空位的局部比对区域找到不同长度的对角线找到可以使比对产生最大权重和的加权过的对角线 一种由计算机科学家发明的普通机器学习算法一种很好的解决进化改变问题的方法原理 通过重排模拟进化过程中空位的插入与重组来尝试多种的MSA方案 以达到越来越高的MSA记分缺点 序列超过20条时会变的非常慢与模拟退火算法相近 模拟退火算法是通过其概率途径来调整已有的比对来获得高记分的MSA 遗传算法 GeneticAlgorithms 局部序列比对 局部比对 LocalAlignment 方法能够确定序列中高度保守的区域概形分析 ProfileAnalysis 区块分析 BlockAnalysis 概形分析 ProfileAnalysis 优势 用来寻找一个可能与之匹配的目标序列用来在一个数据库中搜索一个可能的新的蛋白 pfsearch 通过搜索一个profile数据库来找到提交的序列属于哪一家族 pfscan 比对两个MSA profiletoprofile 缺点 所产生的概形仅仅代表MSA本身的序列族变异 如果MSA中的几个序列相似 则衍生的概形将偏向于这些序列 概形分析 ProfileAnalysis 通过对一组序列进行整体MSA分析 把其中高度保守的区域提出分成小的MSA这些小的MSA根据其序列与结构的比对得到一个记分矩阵根据这个矩阵列出每个位置上的残基分数 称为位置特异记分表 PositionSpecificScoringTable 或概形 Profile 概形 Profile 类似于一个小的MSA 包括匹配 错配 插入和缺失 不同物种HSP70蛋白的profile图 左边第一列为一致序列 consensussequence 其余的行的数值表示一致序列中每一个氨基酸出现的频率的对数与随机频率对数的比值 如出现空位 则必须减去空位行在相应位置上的数值 如用其寻找一个长度为100aa的序列 则检查的串为1 10 2 11 最高记分区段将是概形最相似部分 图中Z表示谷氨酸or谷氨酰胺 B表示天冬氨酸or丙氨酸 ACD VWY sequence profile Profile sequencealignment ACD Y ACD VWY profile profile Profile profilealignment 用CLUSTALX进行Profile比对 区块分析 与概形分析相似 区块也代表MSA中的保守区区块无插入与缺失 每一个位置只有匹配与错配每一条序列中的同一区块具有相同的长度BLOCKS数据库http blocks fhcrc org MSA中的统计学方法 StatisticalMethods 最大期望运算法则 ExpectationMaximizationAlgorithm EM 吉布斯取样器 GibbsSampler 隐马尔可夫模型 HiddenMarkovModel HMM 位置特异性记分矩阵 Position SpecificScoringMatrix PSSM 序列标语 SequenceLogo 最大期望运算法则 用来从未比对的蛋白序列中寻找保守功能域从DNA序列中找蛋白质结合位点通过EM算法找到的这些模体 Motif 允许空位的存在 EM算法策略 先对模体所在每一个序列中的位置和大小进行一个大致预测 并将序列中的这些部分比对 这一比对估计模体中每一位置上的残基或核甘酸的大致组成使用期望步骤 从上述已有的模体中通过每列中的组成来估算每一序列的每一位置上找到这一位点的概率 这些概率又反过来为该位点期望的碱基和氨基酸分布提供新的信息使用最大化步骤 使用以上所得数据重复上面的步骤 直到期望步骤的数据不再发生变化为止 这样就得到了每个序列的最好比对和每列残基的最好估计 MEME MultipleEMforMotifElicitation MEME程序是由加州大学sanDiego分校的超级计算中心所创立MEME可对单个DNA或蛋白质序列或一系列DNA或蛋白质序列中对一个或多个无间隔的模式 Pattern 定位MEME的三种模体 Motif 模型 OOPS 每条序列中预期出现一次motifZOOPS 每条序列出现零次或一次motifTCM 每条序列中出现任意次数的motif在线MEME工具 MEMEDiscovermotifs highlyconservedregions ingroupsofrelatedDNAorproteinsequenceshttp meme sdsc edu meme website meme htmlMASTSearchsequencedatabasesusingmotifshttp meme sdsc edu meme website mast html MEME结果 吉布斯取样器 GibbsSampler 随机地从所有序列中抽出一个或几个作为外围序列用来计算背景噪音 然后对剩下的序列随机地选择假设存在的模体的开始位置 并来回移动其位置 直到模体概率相对于背景概率之比达到最大值 来发现所有序列共有的最可能模式调整序列比对以获得较好的记分 但保留寻找其它更好位置的余地 当在几个序列中选择了模体的正确开始位置后 模体的组成便开始反映在其余序列中所能找到的模体集合最佳模体 并确定模体在每一序列中的精确位置被广泛应用于蛋白序列中发现复杂和可变的模体http bayesweb wadsworth org gibbs gibbs html 隐马尔可夫模型 HMM 定义 一种统计模型 它考虑有关匹配 错配和间隔的所有可能的组合来生成一组序列排列HMM用来序列分析 产生概形HMM 分析序列组成和模式并通过预测开放阅读框 OpenReadingFrame ORF 来定位基因及预测蛋白质结构原理 先产生一个序列家族模型 并用先验信息初始化 然后用一组序列 序列条数 20 来训练HMM模型 训练过程中包括的序列越多 分析的精确性越高 隐马尔可夫模型 HMM 优点 植根于概率论 无须序列的顺序信息 无需插入 缺失和罚分 可以用到很多先验信息缺点 需要至少20条序列 有时需要更多才能了解进化历史分析工具 HMMER http hmmer wustl edu Pfam http www sanger ac uk Software Pfam proteindomainalignmentsandprofileHMMs HMM示意图 图示 NKYLT是通过BEG M1 I1 M2 M3 M4 END 每个氨基酸的概率为 0 33 0 05 0 33 0 05 0 33 0 05 0 33 0 05 0 33 0 05 0 5 一个转换的平均值为0 33 因为大多存在3种转换方式 只有从M4和D4上离开时有2种方式 平均概率为0 5 HowtocreateaHMM 多序列比对 相关序列选取 模型构建 模型训练 参数调整 应用 确立模型 Example 1 Sequenceselection 选取相关的序列 2 Alignment Saveresultasmsformat 多序列比对 模型建立 3 Hmmbuild4 Hmmt5 Hmmcalibrate 模型建立 用相关序列对模型进行训练 参数调整 位