《多序列比对》PPT课件.ppt

基础生物信息学及应用 李裕强2009 09 第 部分生物分子信息的分析 第七章多序列比对 本章内容 多序列比对多序列比对程序及应用 第一节 多序列比对 Multiplesequencealignment 概念多序列比对的意义多序列比对的打分函数多序列比对的方法 1 概念 多序列比对 Multiplesequencealignment alignmultiplerelatedsequencestoachieveoptimalmatchingofthesequences 为了便于描述 对多序列比对过程可以给出下面的定义 把多序列比对看作一张二维表 表中每一行代表一个序列 每一列代表一个残基的位置 将序列依照下列规则填入表中 a 一个序列所有残基的相对位置保持不变 b 将不同序列间相同或相似的残基放入同一列 即尽可能将序列间相同或相似残基上下对齐 下表 表1多序列比对的定义 表示五个短序列 I V 的比对结果 通过插入空位 使5个序列中大多数相同或相似残基放入同一列 并保持每个序列残基顺序不变 与双序列比对一样 多序列比对的方法建立在某个数学或生物学模型之上 因此 正如我们不能对双序列比对的结果得出 正确或错误 的简单结论一样 多序列比对的结果也没有绝对正确和绝对错误之分 而只能认为所使用的模型在多大程度上反映了序列之间的相似性关系以及它们的生物学特征 2 多序列比对的意义 用于描述一组序列之间的相似性关系 以便了解一个分子家族的基本特征 寻找motif 保守区域等 用于描述一组同源序列之间的亲缘关系的远近 应用到分子进化分析中 序列同源性分析 是将待研究序列加入到一组与之同源 但来自不同物种的序列中进行多序列同时比较 以确定该序列与其它序列间的同源性大小 其他应用 如构建profile 打分矩阵等 3 多序列比对的打分函数 多序列比对的打分函数 scoringfunction 为逐对加和 sum of pairs SP 函数SP Itisthesumofthescoresofallpossiblepairsofsequencesinamultiplealignmentbasedonaparticularscoringmatrix ThepurposeofmostmultiplesequencealignmentalgorithmsistoachievemaximumSPscores 其中 c1 c2 ck是一列中的k个字符 p是关于一对字符相似性的打分函数 手工比对在运行经过测试并具有比较高的可信度的计算机程序 辅助编辑软件如bioedit seaview Genedoc等 基础上 结合实验结果或文献资料 对多序列比对结果进行手工修饰 应该说是非常必要的 为了便于进行交互式手工比对 通常使用不同颜色表示具有不同特性的残基 以帮助判别序列之间的相似性 计算机程序自动比对通过特定的算法 如穷举法 启发式算法等 由计算机程序自动搜索最佳的多序列比对状态 4 多序列比对的方法 穷举法 穷举法 exhaustivealignmentmethod 将序列两两比对时的二维动态规划矩阵扩展到多维矩阵 即用矩阵的维数来反映比对的序列数目 这种方法的计算量很大 对于计算机系统的资源要求比较高 一般只有在进行少数的较短的序列的比对的时候才会用到这个方法DCA Divide and ConquerAlignment aweb basedprogramthatissemiexhaustivehttp bibiserv techfak uni bielefeld de dca 启发式算法 启发式算法 heuristicalgorithms 大多数实用的多序列比对程序采用启发式算法 heuristicalgorithms 以降低运算复杂度 随着序列数量的增加 算法复杂性也不断增加 用O m1m2m3 mn 表示对n个序列进行比对时的算法复杂性 其中mn是最后一条序列的长度 若序列长度相差不大 则可简化成O mn 其中n表示序列的数目 m表示序列的长度 显然 随着序列数量的增加 序列比对的算法复杂性按指数规律增长 第二节多序列比对程序及应用 ProgressiveAlignmentMethodIterativeAlignmentBlock BasedAlignment 1 ProgressiveAlignmentMethod Clustal Clustal 是由Feng和Doolittle于1987年提出的 Clustal程序有许多版本ClustalW Thompson等 1994 是目前使用最广泛的多序列比对程序它的PC版本是ClustalX作为程序的一部分 Clustal可以输出用于构建进化树的数据 ClustalW程序 ClustalW程序可以自由使用在NCBI EBI的FTP服务器上可以找到下载的软件包 ClustalW程序用选项单逐步指导用户进行操作 用户可根据需要选择打分矩阵 设置空位罚分等 ftp ftp ebi ac uk pub software EBI的主页还提供了基于Web的ClustalW服务 用户可以把序列和各种要求通过表单提交到服务器上 服务器把计算的结果用Email返回用户 或在线交互使用 http www ebi ac uk clustalw ProgressiveAlignmentMethod ClustalW程序ClustalW对输入序列的格式比较灵活 可以是FASTA格式 还可以是PIR SWISS PROT GDE Clustal GCG MSF RSF等格式 输出格式也可以选择 有ALN GCG PHYLIP和GDE等 用户可以根据自己的需要选择合适的输出格式 用ClustalW得到的多序列比对结果中 所有序列排列在一起 并以特定的符号代表各个位点上残基的保守性 号表示保守性极高的残基位点 号代表保守性略低的残基位点 ProgressiveAlignmentMethod ClustalW算法ClustalW是一种渐进的比对方法 ProgressiveAlignmentMethod seenext 先将多个序列两两比对构建距离矩阵 反应序列之间两两关系 然后根据距离矩阵计算产生系统进化指导树 对关系密切的序列进行加权 然后从最紧密的两条序列开始 逐步引入临近的序列并不断重新构建比对 直到所有序列都被加入为止 ProgressiveAlignmentMethod globalalignment ClustalW使用输入地址 http www ebi ac uk clustalw 设置选项 next ProgressiveAlignmentMethod 邮件或交互式在线获取结果 比对严谨性 full比fast严谨但费时 系统发育树输出选项 序列输入注意格式 ClustalW使用一些选项说明PHYLOGENETICTREE有三个选项TREETYPE 构建系统发育树的算法 有四个个选择none nj neighbourjoining phylip distCORRECTDIST 决定是否做距离修正 对于小的序列歧异 10 选择与否不会产生差异 对于大的序列歧异 需做出修正 因为观察到的距离要比真实的进化距离低 IGNOREGAPS 选择on 序列中的任何空位将被忽视 详细说明参见http www ebi ac uk clustalw clustalw frame html ProgressiveAlignmentMethod ClustalW使用输入5个16SRNA基因序列AF310602AF308147AF283499AF012090AF447394点击 RUN ProgressiveAlignmentMethod 比对结果页面 调出 jalviewalignmentedit 程序 对比对数据进行编辑 两两比对结果 点击查看比对文件 比对结果 版本号 以系统发育图显示 The dnd fileisafilethatdescribesthephylogenetictree 分支图 jalviewalignmentedit程序 对比对数据进行编辑 同一序列 系统树构建方法选择 ProgressiveAlignmentMethod T Coffee Tree basedConsistencyObjectiveFunctionforalignmentEvaluation Progressivealignmentmethodwww ch embnet org software TCoffee htmlInprocessingaquery T Coffeeperformsbothglobalandlocalpairwisealignmentforallpossiblepairsinvolved Adistancematrixisbuilttoderiveaguidetree whichisthenusedtodirectafullmultiplealignmentusingtheprogressiveapproach OutperformsClustalwhenaligningmoderatelydivergentsequencesSlowerthanClustal ProgressiveAlignmentMethod PRALINE web based http ibivu cs vu nl programs pralinewww FirstbuildprofilesforeachsequenceusingPSI BLASTdatabasesearching Eachprofileisthenusedformultiplealignmentusingtheprogressiveapproach theclosestneighbortobejoinedtoalargeralignmentbycomparingtheprofilescoresdoesnotuseaguidetreeIncorporateproteinsecondarystructureinformationtomodifytheprofilescores Perhapsthemostsophisticatedandaccuratealignmentprogramavailable Extremelyslowcomputation ProgressiveAlignmentMethod DbClustal http igbmc u strasbg fr 8080 DbClustal dbclustal htmlPoa Partialorderalignments http www bioinformatics ucla edu poa 2 IterativeAlignment PRRN web basedprogramhttp prrn ims u tokyo ac jp Usesadoublenestediterativestrategyformultiplealignment Basedontheideathatanoptimalsolutioncanbefoundbyrepeatedlymodifyingexistingsuboptimalsolutions Thisprocessisrepeatedovermanycyclesuntilthereisnofurtherimprovementintheoverallalignmentscores 1 aninitialrandomalignmentisgeneratedthatisusedtoderiveaUPGMAtreeWeightsaresubsequentlyappliedtooptimizethealignment 2 thesequencesarerandomlydividedintotwogroups 3 Thetwogroups eachtreatedasasinglesequence arethenalignedtoeachotherusingglobaldynamicprogramming TheprocessisrepeatedthroughmanycyclesuntilthetotalSPscorenolongerincreases 4 Atthispoint theresultingalignmentisusedtoconstructanewUPGMAtree Newweightsareappliedtooptimizealignmentscores 3 Block BasedAlignment Theprogressiveanditerativealignmentstrategiesarelargelyglobalalignmentbasedandmaythereforefailtorecognizeconserveddomainsandmotifsamonghighlydivergentsequencesofvaryinglengths Forsuchdivergentsequencesthatshareonlyregionalsimilarities alocalalignmentbasedapproachhastobeused Block BasedAlignment DIALIGN2 awebbasedprogramhttp bioweb pasteur fr seqanal interfaces dialign2