多序列比对.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,分析多个序列的一致序列,识别蛋白质家族的序列模式,辅助预测新序列的二级或三级结构,相似的蛋白质序列往往具有相似的结构与功能,PCR 引物设计,用于进化分析，是用系统发育方法构建进化树的初使步骤,寻找同源基因,我们为什么做多序列比对?,一个多序列比对例子,VTIS,C,TGSSSNIGAG-NHVK,W,YQ,QLPG,VTIS,C,TGTSSNIGS-ITVN,W,YQ,QLPG,LRLS,C,SSSGFIFSS-YAMY,W,VR,QAPG,LSLT,C,TVSGTSFDD-YYST,W,VR,QPPG,PEVT,C,VVVDVSHEDPQVKFN,W,YVDG-,ATLV,C,LISDFYPGA-VTVA,W,KADS-,AALG,C,LVKDYFPEP-VTVS,W,NSG-,VSLT,C,LVKGFYPSD-IAVE,W,WSNG-,多序列比对与进化研究例子,图中NYLS为树根,多序列比对方法,全局序列比对,动态规划算法,(Dynamic Programming Algorithm),分而治之方法,(Divide and Conquer Methods),SP,方法,(Sum of Pairs Methods),累进方法,(Progressive Methods),迭代方法,(Iterative Methods),遗传算法,(Genetic Algorithms),局部序列比对,概形分析,(Profile Analysis),区块分析,(Block Analysis),统计学方法,(,Statistical Methods,）,多序列比对总体思路,在多序列比对前要考虑的问题,比对的优劣与序列条数正相关,避免在比对中包括相似度差异过大的序列,每个亚群应分别先比对，然后再整体比对,序列长度为,n,的双序列比对,n,2,比对,比对数目成指数增长,例如：序列长度为,n,，序列数为,N,的多序列比对数目是,n,N,对于数目较少且较短的序列来说都不切实际,动态规划算法,(Dynamic Programming),Sequence 1,Sequence 2,Sequence 3,多维的动态规划算法,分而治之,(,Divide and Conquer,DCA,),方法,(,Stoye,et,al,1997),将,MSA,的,空间复杂度减小,DCA,在线,MSA,bioweb.pasteur.fr/seqanal/interfaces/dca-simple.html,分而治之方法,So in effect,Sequence 1,Sequence 2,Sequence 3,SP(Sum of Pairs)方法,为了找到最佳比对，并解决解决动态规则算法的计算复杂问题，,Carrillo&Lipman(1988),建立了SP(Sum of Pairs)方法,SP方法通过对一个随机数据矩阵中氨基酸对的所有可能组合的记分求和来获得矩阵记分,SP 方法例子,使用 BLOSUM62 矩阵,空位罚分为-8,在第一列,有三种两两比对组合方式：,-,S,-,S,S,S,每一列有k(k-1)/2 个双序列比对,-,I,K,S,I,K,S,S,E,-8-8+4=-12,计算所有双序列比对的分数,用这些分数构建进化树,基于进化树计算双序列比对权重,基于进化树构建一个启发式多序列比对,(Heuristic Alignment),计算每一对双序列比对的最大权重,计算比对的空间位置以达到最佳比对,完成最佳比对,输出与最大权重,比较所获得的,慢且消耗大量内存,最大可以比对,8-9,个长约,250,的氨基酸残基,基于,SP,方法的,MSA,程序,针对基于动态规划算法的MSA程序比对序列数目有限，Feng&Doolittle(1987)发明了累进算法,主要思想:通过双序列比对构建进化关系,并通过这种关系来构建序列比对,CLUSTAL 和 PILEUP 是目前常用的基于累进算法的比对软件,CLUSTAL 是免费软件,目前应用非常广泛。,分为基于文本的CLUSTALW和图形用户界面的CLUSTALX,www-igbmc.u-strasbg.fr/BioInfo/ClustalX/Top.html,T-Coffee 是一种新的基于CLUSTAL的程序，,它在比对关系较远的系列上较CLUSTAL更具优势，,但速度较CLUSTAL 要慢,累进算法,(Progressive Methods),1,对所有序列做双序列比对，,构建,距离矩阵计算相似性分数值,2,基于双序列,距离矩阵，,构建一个进化树,Scer,Cele,Dmel,Mouse,Human,3,依据进化树进行渐进比对,依据进化树，开始对关系较近的序列进行两两比对,逐渐加入关系较远的序列进行比对,构建多序列比对,Multiple alignment,Scerevisiae 1,Celegans 2 0.640,Drosophia 3 0.634 0.327,Human 4 0.630 0.408 0.420,Mouse 5 0.619 0.405 0.469 0.289,累进算法原理,一般的累进比对方法,1,3,2,5,1,3,1,3,1,3,2,5,2,5,4,d,root,果仁糖累进方法,(Praline progressive strategy),1,3,2,1,3,1,3,1,3,2,5,2,5,4,d,4,累进算法的一些问题,比对的准确性高度依赖于开始选择的双序列比对,序列关系越远发生的错误可能越高,选择合适的打分矩阵和罚分准则较困难,ClLUSTAL,W,/X简介,ClLUSTAL是用于MSA分析的最为流行的软件,用来多序列比对、概形(Profile)分析和创建进化树,ClLUSTAL最初初由Higgins等于1988年创立并不断完善,ClLUSTAL分为ClLUSTALW和CLUSTALX两种类型，这两种软件核心功能完全相同，区别在于ClLUSTALX为图形界面，而ClLUSTALW保留以前的非图形平台,ClLUSTAL有用于WINDOWS和UNIX/LINUX的各种版本,CLUSTAL方法,进行所有序列间的双序列比对,基于双序列比对分数产生一个相邻连接进化树(neighbor-join tree),根据进化树提供的序列间关系按顺序对序列进行比对,先排最相近序列，再添加其它的序列产生一个MSA来显示每列的序列变异,初期比对可通过一种与FASTA相似的较快的k-tuple模型寻找或动态规则算法来进行,产生进化树的过程中需要计算序列间的遗传距离（错配对位置的数目与比对位置的总数的比值，空位除外）,比对可以用以下两种方法：,-slow/accurate,-fast/approximate,ClustalX,ClustalX,ClustalX,ClustalX,ClustalX,Example,Multiple sequence alignment of 7,neuroglobins using clustalx,P,ILEUP,P,ILEUP是GCG(Genetics Computer Group)软件包中的MSA分析工具,与CLUSTAL一样使用累进式整体比对方法(Progressive Global Alignment),PILEUP开始的双序列比对使用Needleman-Wunsch动态规划算法，所以是全局序列比对，善于比较相似度较高的序列,Output of Pileup,401,OATNFA1 TTCAG.ACACTCAGG TCATCTTCTC AAGC,OATNFAR TTCAG.ACACTCAGG TCATCTTCTC AAGC,BSPTNFA TTCAA.ACACTCAGG TCCTCTTCTC AAGC,CEU14683 TTCAG.ACCCTCAGG TCATCTTCTC AAGC,HSTNFR CCCAG.GCAGTCAGA TCATCTTCTC GAAC,SYNTNFTRP CCCAG.GCAGTCAGA TCATCTTCTC GAAC,CATTNFAA CCCAG.ACACTCAGA TCATCTTCTC GAAC,CFTNFA TCCAG.ACAGTCAAA TCATCTTCTC GAAC,RABTNFM CCCAGATGGT CACCCTCAGA TCAGCTTCTC GGGC,RNTNFAA CCCAGACCCT CACACTCAGA TCATCTTCTC AAAA,Output of Pileup,ClUSTAL和PILEUP存在的问题,最终的比对结果取决于最初的双序列比对，起初的序列相似度越高比对越准确,如果比对序列间长度差异较大则会生成异常的引导树(,guide,trees)从而严重影响多序列比对,所选的记分与罚分标准并不一定适合一组序列中的所有序列,针对累进比对方法的不足产生了迭代方法,迭代方法策略,在比对过程中不断重新比对各亚组序列,把亚组序列再排成包括所有序列在内的整体比对,获得最优的总比对分数（由成对比对分数相加而成）,迭代方法(Iterative Methods),迭代方法程序,MultAlin(Corpet 1988),在累进比对的过程中重新计算成对比对的分数,根据这些分数来完善比对记分的进化树,DIALIGN,在双序列比对中使用对角点阵图找到不包含空位的局部比对区域,找到不同长度的对角线,找到可以使比对产生最大权重和的加权过的对角线,一种由计算机科学家发明的普通机器学习算法,一种很好的解决进化改变问题的方法,原理：通过重排模拟进化过程中空位的插入与重组来尝试多种的MSA方案，以达到越来越高的MSA记分,缺点：序列超过20条时会变的非常慢,与模拟退火算法相近，模拟退火算法是通过其概率途径来调整已有的比对来获得高记分的MSA,遗传算法(Genetic Algorithms),局部序列比对,局部比对(Local Alignment)方法能够确定序列中高度保守的区域,概形分析,(Profile Analysis),区块分析,(Block Analysis),概形分析(Profile Analysis),优势：,用来寻找一个可能与之匹配的目标序列,用来在一个数据库中搜索一个可能的新的蛋白,(pfsearch),通过搜索一个,profile,数据库来找到提交的序列属于哪一家族,(pfscan),比对两个,MSA,(profile to profile),缺点：,所产生的概形仅仅代表MSA本身的序列族变异，如果MSA中的几个序列相似，则衍生的概形将偏向于这些序列,概形分析(Profile Analysis),通过对一组序列进行整体MSA分析，把其中高度保守的区域提出分成小的MSA,这些小的MSA根据其序列与结构的比对得到一个记分矩阵,根据这个矩阵列出每个位置上的残基分数，称为位置特异记分表(Position Specific Scoring Table)或概形(Profile),概形(Profile)类似于一个小的MSA，包括匹配、错配、插入和缺失,不同物种HSP70蛋白的profile图,左边第一列为一致序列(consensus sequence),其余的行的数值表示一致序列中每一个氨基酸出现的频率的对数与随机频率对数的比值，如出现空位，则必须减去空位行在相应位置上的数值。如用其寻找一个长度为100aa的序列，则检查的串为110,211,，最高记分区段将是概形最相似部分。图中Z表示,谷氨酸 or 谷氨酰胺;B表示天冬氨酸 or 丙氨酸,ACDVWY,sequence,profile,Profile-sequence alignment,A,C,D,.,.,Y,ACDVWY,profile,profile,Profile-profile alignment,用CLUSTALX进行Profile比对,区块分析,与概形分析相似，区块也代表MSA中的保守区,区块无插入与缺失，每一个位置只有匹配与错配,每一条序列中的同一区块具有相同的长度,BLOCKS,数据库,blocks.fhcrc.org/,MSA中的统计学方法,(Statistical Methods）,最大期望运算法则,(Expectation Maximization Algorithm,EM),吉布斯取样器,(Gibbs Sampler),隐马尔可夫模型,(Hidden Markov Model,HMM),位置特异性记分矩阵,(Position-Specific Scoring Matrix,PSSM),序列标语,(Sequence Logo),最大期望运算法则,用来从未比对的蛋白序列中寻找保守功能域,从DNA序列中找蛋白质结合位点,通过EM算法找到的这些模体(Motif)允许空位的存在,EM算法策略,先对模体所在每一个序列中的位置和大小进行一个大致预测，并将序列中的这些部分比对，这一比对估计模体中每一位置上的残基或核甘酸的大致组成,使用期望步骤：从上述已有的模体中通过每列中的组成来估算每一序列的每一位置上找到这一位点的概率，这些概率又反过来为该位点期望的碱基和氨基酸分布提供新的信息,使用最大化步骤：使用以上所得数据重复上面的步骤，直到期望步骤的数据不再发生变化为止，这样就得到了每个序列的最好比对和每列残基的最好估计,MEME(Multiple EM for Motif Elicitation),MEME程序是由加州大学san Diego 分校的超级计算中心所创立,MEME可对单个DNA或蛋白质序列或一系列DNA或蛋白质序列中对一个或多个无间隔的模式(Pattern)定位,MEME的三种模体(Motif)模型：,OOPS每条序列中预期出现一次motif,ZOOPS每条序列出现零次或一次motif,TCM每条序列中出现任意次数的motif,在线MEME工具：,MEME,Discover motifs(highly conserved regions)in groups of related DNA or protein sequences,meme.sdsc.edu/meme/website/meme.html,MAST,Search sequence databases using motifs,meme.sdsc.edu/meme/website/mast.html,MEME结果,吉布斯取样器(Gibbs Sampler),随机地从所有序列中抽出一个或几个作为外围序列用来计算背景噪音，然后对剩下的序列随机地选择假设存在的模体的开始位置，并来回移动其位置，直到模体概率相对于背景概率之比达到最大值，来发现所有序列共有的最可能模式,调整序列比对以获得较好的记分，但保留寻找其它更好位置的余地。当在几个序列中选择了模体的正确开始位置后，模体的组成便开始反映在其余序列中所能找到的模体,集合最佳模体，并确定模体在每一序列中的精确位置,被广泛应用于蛋白序列中发现复杂和可变的模体,bayesweb.wadsworth.org/gibbs/gibbs.html,隐马尔可夫模型(HMM),定义：一种统计模型，它考虑有关匹配、错配和间隔的所有可能的组合来生成一组序列排列,HMM用来序列分析、产生概形HMM、分析序列组成和模式并通过预测开放阅读框(Open Reading Frame,ORF）来定位基因及预测蛋白质结构,原理：先产生一个序列家族模型，并用先验信息初始化，然后用一组序列(序列条数,20),来训练HMM模型。训练过程中包括的序列越多，分析的精确性越高,隐马尔可夫模型(HMM),优点：植根于概率论，无须序列的顺序信息，无需插入/缺失和罚分，可以用到很多先验信息,缺点：需要至少20条序列，有时需要更多才能了解进化历史,分析工具：HMMER(,hmmer.wustl.edu/,),Pfam,:,www.sanger.ac.uk/Software/Pfam/,(protein domain alignments and profile HMMs),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）,How to create a HMM,多序列比对,相关序列选取,模型构建,模型训练,参数调整,应用,确立模型,Example:1.Sequence selection,选取相关的序列,2.Alignment,Save result as ms format,多序列比对,模型建立,3.Hmmbuild,4.Hmmt,5.Hmmcalibrate,模型建立,用相关序列对模型进行训练,参数调整,位置特异性记分矩阵,对于序列保守区进行MSA分析可以产生位置特异记分矩阵(Position-specific scoring matrix,PSSM),与Profile相似，都是用一个数值表示每一个氨基酸或核苷酸在每一位置上出现的频率，不同的是PSSM使用频率的对数值(log,2,)为其数值,用PSSM来搜寻一条序列，以找到此序列具有PSSM所代表的序列模体(motif)的可能位置,用来搜索整个数据库以寻找额外的具有相同模体(motif)的序列,寻找蛋白质家族所共有的序列模式、转录因子结合位点和内含子与外显子交界区共有的序列模式,PSSM用途,序列标语(Sequence Logos),序列标语是一种用图形来表示模体(motif)中每一列残基信息的,在线序列LOGO：,weblogo.berkeley.edu,X轴表示模式的位置，Y轴上字母高度代表该字母在此位置上出现的频率,MSA编辑,通过编辑比对得到更为合理的MSA,这并不是一种,欺骗,行为,如何选择合适的MSA编辑器？,支持氨基酸彩色显示,能识别多种MSA格式,有合适的视窗界面,可用鼠标进行序列的添加、删除和移动,MSA编辑器,CINEMA(Colour Interactive Editor for Multiple Alignments),广泛使用的序列和点阵图编辑工具,特点是拖放式编辑，使用分割屏幕来显示比对的不同区域，多模体的选择与操作，显示蛋白质结构,www.biochem.ucl.ac.uk/bsm/dbbrowser/CINEMA2.02/index2.html,CINEMA,MSA编辑器,GDE(Genetic Data Environment),用于UNIX系统，如要在MS-DOS或Macintosh使用需要X-Windows客户端软件,