《[理学]多序列比对》由会员分享，可在线阅读，更多相关《[理学]多序列比对（41页珍藏版）》请在金锄头文库上搜索。
1、基础生物信息学及应用,李裕强 2009.09,第部分 生物分子信息的分析,第七章 多序列比对,本章内容： 多序列比对 多序列比对程序及应用,第一节、多序列比对 （Multiple sequence alignment）,概念 多序列比对的意义 多序列比对的打分函数 多序列比对的方法,1、概念,多序列比对（Multiple sequence alignment） align multiple related sequences to achieve optimal matching of the sequences. 为了便于描述，对多序列比对过程可以给出下面的定义：把多序列比对看作一张二维表，
2、表中每一行代表一个序列，每一列代表一个残基的位置。将序列依照下列规则填入表中： （a）一个序列所有残基的相对位置保持不变； （b）将不同序列间相同或相似的残基放入同一列，即尽可能将序列间相同或相似残基上下对齐（下表）。,表1 多序列比对的定义,表示五个短序列（I-V）的比对结果。通过插入空位，使5个序列中大多数相同或相似残基放入同一列，并保持每个序列残基顺序不变,与双序列比对一样，多序列比对的方法建立在某个数学或生物学模型之上。 因此，正如我们不能对双序列比对的结果得出“正确或错误”的简单结论一样，多序列比对的结果也没有绝对正确和绝对错误之分，而只能认为所使用的模型在多大程度上反映了序列之间的
3、相似性关系以及它们的生物学特征。,2、多序列比对的意义,用于描述一组序列之间的相似性关系，以便了解一个分子家族的基本特征，寻找motif，保守区域等。 用于描述一组同源序列之间的亲缘关系的远近，应用到分子进化分析中。 序列同源性分析：是将待研究序列加入到一组与之同源，但来自不同物种的序列中进行多序列同时比较，以确定该序列与其它序列间的同源性大小。 其他应用，如构建profile，打分矩阵等,3、多序列比对的打分函数,多序列比对的打分函数（scoring function）为逐对加和（sum-of-pairs，SP）函数 SP： It is the sum of the scores of al
4、l possible pairs of sequences in a multiple alignment based on a particular scoring matrix. The purpose of most multiple sequence alignment algorithms is to achieve maximum SP scores.,其中，c1,c2,ck是一列中的k个字符，p是关于一对字符相似性的打分函数。,手工比对 在运行经过测试并具有比较高的可信度的计算机程序（辅助编辑软件如bioedit，seaview，Genedoc等）基础上，结合实验结果或文献资料，
5、对多序列比对结果进行手工修饰，应该说是非常必要的。 为了便于进行交互式手工比对，通常使用不同颜色表示具有不同特性的残基，以帮助判别序列之间的相似性。 计算机程序自动比对 通过特定的算法（如穷举法，启发式算法等），由计算机程序自动搜索最佳的多序列比对状态。,4、多序列比对的方法,穷举法,穷举法（exhaustive alignment method） 将序列两两比对时的二维动态规划矩阵扩展到多维矩阵。即用矩阵的维数来反映比对的序列数目。这种方法的计算量很大，对于计算机系统的资源要求比较高，一般只有在进行少数的较短的序列的比对的时候才会用到这个方法 DCA (Divide-and-Conquer
6、Alignment）：a web-based program that is semiexhaustive http:/bibiserv.techfak.uni-bielefeld.de/dca/,启发式算法,启发式算法（heuristic algorithms）： 大多数实用的多序列比对程序采用启发式算法（heuristic algorithms），以降低运算复杂度。 随着序列数量的增加，算法复杂性也不断增加。用O（m1m2m3mn）表示对n个序列进行比对时的算法复杂性，其中mn是最后一条序列的长度。若序列长度相差不大，则可简化成O（mn），其中n表示序列的数目，m表示序列的长度。显然，随着
7、序列数量的增加，序列比对的算法复杂性按指数规律增长。,第二节 多序列比对程序及应用,Progressive Alignment Method Iterative Alignment Block-Based Alignment,1、Progressive Alignment Method,Clustal: Clustal，是由Feng和Doolittle于1987年提出的。 Clustal程序有许多版本 ClustalW（Thompson等，1994）是目前使用最广泛的多序列比对程序 它的PC版本是ClustalX 作为程序的一部分，Clustal 可以输出用于构建进化树的数据。,Clustal
8、W 程序：ClustalW 程序可以自由使用 在NCBI/EBI的FTP服务器上可以找到下载的软件包。ClustalW 程序用选项单逐步指导用户进行操作，用户可根据需要选择打分矩阵、设置空位罚分等。 ftp:/ftp.ebi.ac.uk/pub/software/ EBI的主页还提供了基于Web的ClustalW服务，用户可以把序列和各种要求通过表单提交到服务器上，服务器把计算的结果用Email返回用户（或在线交互使用）。 http:/www.ebi.ac.uk/clustalw/,Progressive Alignment Method,ClustalW 程序 ClustalW对输入序列的格
9、式比较灵活，可以是FASTA格式，还可以是PIR、SWISS-PROT、GDE、Clustal、GCG/MSF、RSF等格式。 输出格式也可以选择，有ALN、GCG、PHYLIP和GDE等，用户可以根据自己的需要选择合适的输出格式。 用ClustalW得到的多序列比对结果中，所有序列排列在一起，并以特定的符号代表各个位点上残基的保守性，“*”号表示保守性极高的残基位点；“.”号代表保守性略低的残基位点。,Progressive Alignment Method,ClustalW 算法 ClustalW是一种渐进的比对方法(Progressive Alignment Method)（see ne
10、xt） 先将多个序列两两比对构建距离矩阵，反应序列之间两两关系； 然后根据距离矩阵计算产生系统进化指导树，对关系密切的序列进行加权； 然后从最紧密的两条序列开始，逐步引入临近的序列并不断重新构建比对，直到所有序列都被加入为止。,Progressive Alignment Method,global alignment,Clustal W 使用 输入地址：http:/www.ebi.ac.uk/clustalw/ 设置选项 （next）,Progressive Alignment Method,邮件或交互式在线获取结果,比对严谨性：full比fast严谨但费时,系统发育树输出选项,序列输入 注意
11、格式,Clustal W 使用 一些选项说明 PHYLOGENETIC TREE有三个选项 TREE TYPE：构建系统发育树的算法，有四个个选择none、nj（neighbour joining）、phylip、dist CORRECT DIST：决定是否做距离修正。对于小的序列歧异（10），选择与否不会产生差异；对于大的序列歧异，需做出修正。因为观察到的距离要比真实的进化距离低。 IGNORE GAPS：选择on，序列中的任何空位将被忽视。 详细说明参见 http:/www.ebi.ac.uk/clustalw/clustalw_frame.html,Progressive Alignme
12、nt Method,Clustal W 使用 输入5个16S RNA 基因序列 AF310602 AF308147 AF283499 AF012090 AF447394 点击“RUN”,Progressive Alignment Method,比对结果页面,调出“jalview alignment edit”程序，对比对数据进行编辑,两两比对结果,点击查看比对文件,比对结果,版本号,以系统发育图显示,The “.dnd“ file is a file that describes the phylogenetic tree,分支图,jalview alignment edit程序，对比对数据进
13、行编辑,同一序列,系统树构建方法选择,Progressive Alignment Method,T-Coffee (Tree-based Consistency Objective Function for alignment Evaluation）： Progressive alignment method www.ch.embnet.org/software/TCoffee.html In processing a query, T-Coffee performs both global and local pairwise alignment for all possible pairs
14、 involved. A distance matrix is built to derive a guide tree, which is then used to direct a full multiple alignment using the progressive approach. Outperforms Clustal when aligning moderately divergent sequences Slower than Clustal,Progressive Alignment Method,PRALINE： web-based： http:/ibivu.cs.vu
15、.nl/programs/pralinewww/ First build profiles for each sequence using PSI-BLAST database searching. Each profile is then used for multiple alignment using the progressive approach. the closest neighbor to be joined to a larger alignment by comparing the profile scores does not use a guide tree Incor
16、porate protein secondary structure information to modify the profile scores. Perhaps the most sophisticated and accurate alignment program available. Extremely slow computation.,Progressive Alignment Method,DbClustal: http:/igbmc.u-strasbg.fr:8080/DbClustal/dbclustal.html Poa (Partial order alignments): http:/www.bioinformatics.ucla.edu/poa/,2、Iterative Alignment,PRRN： web-based program http:/
