理学多序列比对教学内容.ppt

《理学多序列比对教学内容.ppt》由会员分享，可在线阅读，更多相关《理学多序列比对教学内容.ppt（41页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、基基 础础 生生 物物 信信 息息 学学 及及 应应 用用理学多序列比对基基 础础 生生 物物 信信 息息 学学 及及 应应 用用n本章内容：本章内容：多序列比对多序列比对多序列比对程序及应用多序列比对程序及应用基基 础础 生生 物物 信信 息息 学学 及及 应应 用用第一节、多序列比对第一节、多序列比对（Multiple sequence alignmentMultiple sequence alignment）n概念概念n多序列比对的意义多序列比对的意义n多序列比对的打分函数多序列比对的打分函数n多序列比对的方法多序列比对的方法基基 础础 生生 物物 信信 息息 学学 及及 应应 用用1

2、1、概念、概念n多序列比对（多序列比对（Multiple sequence alignmentMultiple sequence alignment）align multiple related sequences to achieve align multiple related sequences to achieve optimal matching of the sequences.optimal matching of the sequences.为了便于描述，对多序列比对过程可以给出下面的定义：把多序为了便于描述，对多序列比对过程可以给出下面的定义：把多序列比对看作一张二维表，表中

3、每一行代表一个序列，每一列代表列比对看作一张二维表，表中每一行代表一个序列，每一列代表一个残基的位置。将序列依照下列规则填入表中：一个残基的位置。将序列依照下列规则填入表中：（a a）一个序列所有残基的相对位置保持不变；）一个序列所有残基的相对位置保持不变；（b b）将不同序列间相同或相似的残基放入同一列，即尽可能将序列）将不同序列间相同或相似的残基放入同一列，即尽可能将序列间相同或相似残基上下对齐（下表）。间相同或相似残基上下对齐（下表）。基基 础础 生生 物物 信信 息息 学学 及及 应应 用用1 234567891YDGGAV-EALYDGG-EALFEGGILVEALFD-GILVQA

4、VYEGGAVVQAL表表1 1 多序列比对的定义多序列比对的定义 表表示示五五个个短短序序列列（I-VI-V）的的比比对对结结果果。通通过过插插入入空空位位，使使5 5个个序序列列中中大多数相同或相似残基放入同一列，并保持每个序列残基顺序不变大多数相同或相似残基放入同一列，并保持每个序列残基顺序不变基基 础础 生生 物物 信信 息息 学学 及及 应应 用用n与双序列比对一样，多序列比对的方法建立在某个数学或与双序列比对一样，多序列比对的方法建立在某个数学或生物学模型之上。生物学模型之上。n因此，正如我们不能对双序列比对的结果得出因此，正如我们不能对双序列比对的结果得出“正确或错正确或错误误”

5、的简单结论一样，多序列比对的结果也没有绝对正确的简单结论一样，多序列比对的结果也没有绝对正确和绝对错误之分，而只能认为所使用的模型在多大程度上和绝对错误之分，而只能认为所使用的模型在多大程度上反映了序列之间的相似性关系以及它们的生物学特征。反映了序列之间的相似性关系以及它们的生物学特征。基基 础础 生生 物物 信信 息息 学学 及及 应应 用用2 2、多序列比对的意义、多序列比对的意义n用于描述一组序列之间的相似性关系，以便了解一个分用于描述一组序列之间的相似性关系，以便了解一个分子子家族的基本特征家族的基本特征，寻找，寻找motifmotif，保守区域等。，保守区域等。n用于描述一组同源序列

6、之间的亲缘关系的远近，应用到用于描述一组同源序列之间的亲缘关系的远近，应用到分子进化分析中。分子进化分析中。序列同源性分析序列同源性分析：是将待研究序列加入到一组与之：是将待研究序列加入到一组与之同源，但来自不同物种的序列中进行多序列同时比同源，但来自不同物种的序列中进行多序列同时比较，以确定该序列与其它序列间的同源性大小。较，以确定该序列与其它序列间的同源性大小。n其他应用，如构建其他应用，如构建profileprofile，打分矩阵等，打分矩阵等基基 础础 生生 物物 信信 息息 学学 及及 应应 用用3 3、多序列比对的打分函数、多序列比对的打分函数n多序列比对的打分函数（多序列比对的打

7、分函数（scoring functionscoring function）为）为逐对加和（逐对加和（sum-of-pairssum-of-pairs，SPSP）函数）函数 nSPSP：It is the sum of the scores of all possible pairs of It is the sum of the scores of all possible pairs of sequences in a multiple alignment based on a particular sequences in a multiple alignment based on a p

8、articular scoring matrix.scoring matrix.The purpose of most multiple sequence alignment The purpose of most multiple sequence alignment algorithms is to achieve maximum SP scores.algorithms is to achieve maximum SP scores.基基 础础 生生 物物 信信 息息 学学 及及 应应 用用其中，c1,c2,ck是一列中的k个字符，p是关于一对字符相似性的打分函数。基基 础础 生生 物物

9、 信信 息息 学学 及及 应应 用用n手工比对手工比对在运行经过测试并具有比较高的可信度的计算机程序（辅助在运行经过测试并具有比较高的可信度的计算机程序（辅助编辑软件如编辑软件如bioeditbioedit，seaviewseaview，GenedocGenedoc等）基础上，结合实等）基础上，结合实验结果或文献资料，对多序列比对结果进行手工修饰，应该验结果或文献资料，对多序列比对结果进行手工修饰，应该说是非常必要的。说是非常必要的。为了便于进行交互式手工比对，通常使用不同颜色表示具有为了便于进行交互式手工比对，通常使用不同颜色表示具有不同特性的残基，以帮助判别序列之间的相似性。不同特性的残基

10、，以帮助判别序列之间的相似性。n计算机程序自动比对计算机程序自动比对通过特定的算法（如穷举法，启发式算法等），由计算机程通过特定的算法（如穷举法，启发式算法等），由计算机程序自动搜索最佳的多序列比对状态。序自动搜索最佳的多序列比对状态。4 4、多序列比对的方法、多序列比对的方法基基 础础 生生 物物 信信 息息 学学 及及 应应 用用穷举法穷举法n穷举法（穷举法（exhaustive alignment methodexhaustive alignment method）将序列两两比对时的二维动态规划矩阵扩展到多维矩阵。即用将序列两两比对时的二维动态规划矩阵扩展到多维矩阵。即用矩阵的维数来反映

11、比对的序列数目。这种方法的计算量很大，矩阵的维数来反映比对的序列数目。这种方法的计算量很大，对于计算机系统的资源要求比较高，一般只有在进行少数的较对于计算机系统的资源要求比较高，一般只有在进行少数的较短的序列的比对的时候才会用到这个方法短的序列的比对的时候才会用到这个方法DCA(Divide-and-Conquer AlignmentDCA(Divide-and-Conquer Alignment）：）：a web-based a web-based program that is semiexhaustive program that is semiexhaustive http:/bibi

12、serv.techfak.uni-bielefeld.de/dca/http:/bibiserv.techfak.uni-bielefeld.de/dca/基基 础础 生生 物物 信信 息息 学学 及及 应应 用用启发式算法启发式算法n启发式算法（启发式算法（heuristic algorithmsheuristic algorithms）：大多数实用的多序列比对程序采用大多数实用的多序列比对程序采用启发式算法启发式算法（heuristic algorithmsheuristic algorithms），以降低运算复杂度。），以降低运算复杂度。随着序列数量的增加，算法复杂性也不断增加。用随着序

13、列数量的增加，算法复杂性也不断增加。用O O（m1m2m3mnm1m2m3mn）表示对）表示对n n个序列进行比对时的算法复杂性，个序列进行比对时的算法复杂性，其中其中mnmn是最后一条序列的长度。若序列长度相差不大，则是最后一条序列的长度。若序列长度相差不大，则可简化成可简化成O O（m mn n），其中），其中n n表示序列的数目，表示序列的数目，m m表示序列的长表示序列的长度。显然，随着序列数量的增加，序列比对的算法复杂性度。显然，随着序列数量的增加，序列比对的算法复杂性按指数规律增长。按指数规律增长。基基 础础 生生 物物 信信 息息 学学 及及 应应 用用第二节第二节 多序列比对程

14、序及应用多序列比对程序及应用nProgressive Alignment MethodProgressive Alignment MethodnIterative AlignmentIterative AlignmentnBlock-Based AlignmentBlock-Based Alignment基基 础础 生生 物物 信信 息息 学学 及及 应应 用用1 1、Progressive Alignment MethodProgressive Alignment MethodnClustal:Clustal:ClustalClustal，是由，是由FengFeng和和DoolittleDo

15、olittle于于19871987年提出的。年提出的。ClustalClustal程序有许多版本程序有许多版本ClustalWClustalW（ThompsonThompson等，等，19941994）是目前使用最广泛的多序列）是目前使用最广泛的多序列比对程序比对程序它的它的PCPC版本是版本是ClustalXClustalX作为程序的一部分，作为程序的一部分，Clustal Clustal 可以输出用于构建进化可以输出用于构建进化树的数据。树的数据。基基 础础 生生 物物 信信 息息 学学 及及 应应 用用nClustalW ClustalW 程序：程序：ClustalW ClustalW

16、程序可以自由使用程序可以自由使用在在NCBI/EBINCBI/EBI的的FTPFTP服务器上可以找到下载的软件包。服务器上可以找到下载的软件包。C ClustallustalW W 程序用选项单逐步指导用户进行操作，用户程序用选项单逐步指导用户进行操作，用户可根据需要选择打分矩阵、设置空位罚分等。可根据需要选择打分矩阵、设置空位罚分等。ftp:/ftp.ebi.ac.uk/pub/software/ftp:/ftp.ebi.ac.uk/pub/software/EBIEBI的主页还提供了基于的主页还提供了基于WebWeb的的C ClustallustalW W服务，用户可以服务，用户可以把序列

17、和各种要求通过表单提交到服务器上，服务器把序列和各种要求通过表单提交到服务器上，服务器把计算的结果用把计算的结果用EmailEmail返回用户（或在线交互使用）。返回用户（或在线交互使用）。http:/www.ebi.ac.uk/clustalw/http:/www.ebi.ac.uk/clustalw/Progressive Alignment MethodProgressive Alignment Method基基 础础 生生 物物 信信 息息 学学 及及 应应 用用nClustalW ClustalW 程序程序C ClustallustalW W对输入序列的格式比较灵活，可以是对输入序列

18、的格式比较灵活，可以是FASTAFASTA格式，还可格式，还可以是以是PIRPIR、SWISS-PROTSWISS-PROT、GDEGDE、ClustalClustal、GCG/MSFGCG/MSF、RSFRSF等格式。等格式。输出格式也可以选择，有输出格式也可以选择，有ALNALN、GCGGCG、PHYLIPPHYLIP和和GDEGDE等，用户可以等，用户可以根据自己的需要选择合适的输出格式。根据自己的需要选择合适的输出格式。用用C ClustallustalW W得到的多序列比对结果中，所有序列排列在一起，得到的多序列比对结果中，所有序列排列在一起，并以特定的符号代表各个位点上残基的保守性

19、，并以特定的符号代表各个位点上残基的保守性，“*”“*”号表示保号表示保守性极高的残基位点；守性极高的残基位点；“.”“.”号代表保守性略低的残基位点。号代表保守性略低的残基位点。Progressive Alignment Method基基 础础 生生 物物 信信 息息 学学 及及 应应 用用nClustalW ClustalW 算法算法C ClustallustalW W是一种渐进的比对方法是一种渐进的比对方法(Progressive(Progressive Alignment Method)Alignment Method)（see nextsee next）先将多个序列两两比对构建距离矩

20、阵，反应序列之间两两关先将多个序列两两比对构建距离矩阵，反应序列之间两两关系；系；然后根据距离矩阵计算产生系统进化指导树，对关系密切的然后根据距离矩阵计算产生系统进化指导树，对关系密切的序列进行加权；序列进行加权；然后从最紧密的两条序列开始，逐步引入临近的序列并不断然后从最紧密的两条序列开始，逐步引入临近的序列并不断重新构建比对，直到所有序列都被加入为止。重新构建比对，直到所有序列都被加入为止。Progressive Alignment MethodProgressive Alignment Method基基 础础 生生 物物 信信 息息 学学 及及 应应 用用global alignment

21、基基 础础 生生 物物 信信 息息 学学 及及 应应 用用nClustal W Clustal W 使用使用输入地址：输入地址：http:/www.ebi.ac.uk/clustalw/http:/www.ebi.ac.uk/clustalw/设置选项设置选项 （nextnext）Progressive Alignment MethodProgressive Alignment Method基基 础础 生生 物物 信信 息息 学学 及及 应应 用用邮件或交互式在线获取结果比对严谨性：full比fast严谨但费时系统发育树输出选项序列输入注意格式基基 础础 生生 物物 信信 息息 学学 及及 应

22、应 用用nClustal W Clustal W 使用使用一些选项说明一些选项说明PHYLOGENETIC TREEPHYLOGENETIC TREE有三个选项有三个选项 TREE TYPETREE TYPE：构建系统发育树的算法，有四个个选择：构建系统发育树的算法，有四个个选择nonenone、njnj（neighbour joiningneighbour joining）、）、phylipphylip、distdistCORRECT DISTCORRECT DIST：决定是否做距离修正。对于小的序列歧异（：决定是否做距离修正。对于小的序列歧异（1010），选择与否不会产生差异；对于大的序列

23、歧异，需做出），选择与否不会产生差异；对于大的序列歧异，需做出修正。因为观察到的距离要比真实的进化距离低。修正。因为观察到的距离要比真实的进化距离低。IGNORE GAPSIGNORE GAPS：选择：选择onon，序列中的任何空位将被忽视。，序列中的任何空位将被忽视。详细说明参见详细说明参见 http:/www.ebi.ac.uk/clustalw/clustalw_frame.htmlhttp:/www.ebi.ac.uk/clustalw/clustalw_frame.htmlProgressive Alignment Method基基 础础 生生 物物 信信 息息 学学 及及 应应 用

24、用nClustal W Clustal W 使用使用输入输入5 5个个16S RNA 16S RNA 基因序列基因序列AF310602AF310602AF308147AF308147AF283499AF283499AF012090AF012090AF447394AF447394点击点击“RUN”“RUN”Progressive Alignment Method基基 础础 生生 物物 信信 息息 学学 及及 应应 用用比对结果页面调出“jalview alignment edit”程序，对比对数据进行编辑基基 础础 生生 物物 信信 息息 学学 及及 应应 用用两两比对结果点击查看比对文件基基

25、础础 生生 物物 信信 息息 学学 及及 应应 用用比对结果版本号基基 础础 生生 物物 信信 息息 学学 及及 应应 用用以系统发育图显示 The.dnd file is a file that describes the phylogenetic tree 分支图基基 础础 生生 物物 信信 息息 学学 及及 应应 用用jalview alignment editjalview alignment edit程序，对比对数据进行编辑程序，对比对数据进行编辑同一序列 基基 础础 生生 物物 信信 息息 学学 及及 应应 用用系统树构建方法选择 基基 础础 生生 物物 信信 息息 学学 及及 应

26、应 用用Progressive Alignment MethodProgressive Alignment MethodnT-CoffeeT-Coffee(Tree-based Consistency Objective Function for (Tree-based Consistency Objective Function for alignment Evaluationalignment Evaluation）：）：Progressive alignment method Progressive alignment method www.ch.embnet.org/software/

27、TCoffee.htmlwww.ch.embnet.org/software/TCoffee.htmlIn processing a query,T-Coffee performs both global and In processing a query,T-Coffee performs both global and local pairwise alignment for all possible pairs involved.local pairwise alignment for all possible pairs involved.A distance matrix is bu

28、ilt to derive a guide tree,which is A distance matrix is built to derive a guide tree,which is then used to direct a full multiple alignment using the then used to direct a full multiple alignment using the progressive approach.progressive approach.Outperforms ClustalOutperforms Clustal when alignin

29、g moderately divergent when aligning moderately divergent sequencessequencesSlower than ClustalSlower than Clustal基基 础础 生生 物物 信信 息息 学学 及及 应应 用用Progressive Alignment MethodProgressive Alignment MethodnPRALINEPRALINE：web-basedweb-based：http:/ibivu.cs.vu.nl/programs/pralinewww/http:/ibivu.cs.vu.nl/prog

30、rams/pralinewww/First build profiles for each sequence using PSI-BLAST database First build profiles for each sequence using PSI-BLAST database searching.searching.Each profile is then used for multiple alignment using the Each profile is then used for multiple alignment using the progressive approa

31、ch.progressive approach.the closest neighbor to be joined to a larger alignment by comparing the the closest neighbor to be joined to a larger alignment by comparing the profile scoresprofile scoresdoes not use a guide treedoes not use a guide treeIncorporate protein secondary structure information

32、to modify the Incorporate protein secondary structure information to modify the profile scores.profile scores.Perhaps the most sophisticated and accurate alignment program Perhaps the most sophisticated and accurate alignment program availableavailable.Extremely slow computation.Extremely slow compu

33、tation.基基 础础 生生 物物 信信 息息 学学 及及 应应 用用基基 础础 生生 物物 信信 息息 学学 及及 应应 用用基基 础础 生生 物物 信信 息息 学学 及及 应应 用用基基 础础 生生 物物 信信 息息 学学 及及 应应 用用Progressive Alignment MethodProgressive Alignment MethodnDbClustal:DbClustal:http:/igbmc.u-strasbg.fr:8080/DbClustal/dbclustal.htmlhttp:/igbmc.u-strasbg.fr:8080/DbClustal/dbclus

34、tal.htmlnPoa(Partial order alignments):Poa(Partial order alignments):http:/www.bioinformatics.ucla.edu/poa/http:/www.bioinformatics.ucla.edu/poa/基基 础础 生生 物物 信信 息息 学学 及及 应应 用用2 2、Iterative AlignmentIterative AlignmentnPRRNPRRN：web-based program web-based program http:/prrn.ims.u-tokyo.ac.jp/http:/prr

35、n.ims.u-tokyo.ac.jp/Uses a double nested iterative strategy for multiple alignment.Uses a double nested iterative strategy for multiple alignment.Based on the idea that an optimal solution can be found by Based on the idea that an optimal solution can be found by repeatedly modifying existing subopt

36、imal solutionsrepeatedly modifying existing suboptimal solutions基基 础础 生生 物物 信信 息息 学学 及及 应应 用用This process is repeated over many cycles until there is no further improvement in the overall alignment scores.1、an initial random alignment is generated that is used to derive a UPGMA treeWeights are subse

37、quently applied to optimize the alignment.2、the sequences are randomly divided into two groups3、The two groups,each treated as a single sequence,are then aligned to each other using global dynamic programming.The process is repeated through many cycles until the total SP score no longer increases.4、

38、At this point,the resulting alignment is used to construct a new UPGMA tree.New weights are applied to optimize alignment scores.基基 础础 生生 物物 信信 息息 学学 及及 应应 用用3 3、Block-Based AlignmentBlock-Based AlignmentnThe progressive and iterative alignment strategies are The progressive and iterative alignment

39、strategies are largely global alignment based and may therefore fail to largely global alignment based and may therefore fail to recognize conserved domains and motifs among highly recognize conserved domains and motifs among highly divergent sequences of varying lengths.For such divergent divergent

40、 sequences of varying lengths.For such divergent sequences that share only regional similarities,a local sequences that share only regional similarities,a local alignment based approach has to be used.alignment based approach has to be used.基基 础础 生生 物物 信信 息息 学学 及及 应应 用用Block-Based AlignmentBlock-Bas

41、ed AlignmentnDIALIGN2DIALIGN2：a web based program a web based program http:/bioweb.pasteur.fr/seqanal/interfaces/dialign2.htmlhttp:/bioweb.pasteur.fr/seqanal/interfaces/dialign2.html It places emphasis on block-to-block comparison rather than It places emphasis on block-to-block comparison rather th

42、an residue-to-residue comparison.The sequence regions between the residue-to-residue comparison.The sequence regions between the blocks are left unaligned.blocks are left unaligned.The program has been shown to be especially suitable The program has been shown to be especially suitable for for align

43、ing divergent sequencesaligning divergent sequences with only local similarity.with only local similarity.基基 础础 生生 物物 信信 息息 学学 及及 应应 用用Block-Based AlignmentBlock-Based AlignmentnMatch-BoxMatch-Box：web-based server web-based server http:/www.fundp.ac.be/sciences/biologie/bms/matchbox_suhttp:/www.fund

44、p.ac.be/sciences/biologie/bms/matchbox_submit.shtmlbmit.shtmlAims to identify conserved blocks(or boxes)among Aims to identify conserved blocks(or boxes)among sequences.sequences.The server requires the user to submit a set of The server requires the user to submit a set of sequences in the FASTA fo

45、rmat and the results are sequences in the FASTA format and the results are returned by e-mail.returned by e-mail.基基 础础 生生 物物 信信 息息 学学 及及 应应 用用n启发式算法可以在合理的计算时间内得到较优的启发式算法可以在合理的计算时间内得到较优的可行解。局域搜索启发式算法应用广泛。局域搜可行解。局域搜索启发式算法应用广泛。局域搜索的一般步骤如下：索的一般步骤如下：1 1、从一个初始可行解出发从一个初始可行解出发 2 2、找出相邻的可行解找出相邻的可行解 3 3、从相邻的可行解中找出更好的可行解从相邻的可行解中找出更好的可行解 n一般地，局域搜索启发式算法会得到一个局部最一般地，局域搜索启发式算法会得到一个局部最优解，而这个局部最优解有时就是全局最优解。优解，而这个局部最优解有时就是全局最优解。基基 础础 生生 物物 信信 息息 学学 及及 应应 用用此课件下载可自行编辑修改，仅供参考！此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢感谢您的支持，我们努力做得更好！谢谢