序列长度为 n 的双序列比对 n2 比对 比对数目成指数增长 例如：序列长度为n，序列数为N 的 多序列比对数目是nN
对于数目较少且较短的序列来说都不 切实际
多维的动态规划算法
Sequence 1
Sequence 2
分而治之方法
分而治之 (Divide and Conquer, DCA)方法 将MSA的空间复 杂度减小 DCA在线MSA
http://bioweb.pasteur.fr/seqanal/int erfaces/dca-simple.html
So in effect …
Sequence 1
Sequence 2
SP(Sum of Pairs)方法
为了找到最佳比对，并解决动态 规则算法的计算复杂问题， Carrillo & Lipman (1988)发明了 SP(Sum of Pairs)方法
进行所有序列间的双序列比对
基于双序列比对分数产生一个相邻连 接进化树(neighbor-join tree) 根据进化树提供的序列间关系按顺序 对序列进行比对 比对可以用以下两种方法： - slow/accurate - fast/approximate
CLUSTALW
******** CLUSTAL W (1.8) Multiple Sequence Alignments ******** 1.Sequence Input From Disc 2. Multiple Alignments 3. Profile / Structure Alignments 4. Phylogenetic trees S. Execute a system command H. HELP X. EXIT (leave program)
Your choice:1<rtn>
CLUSTALW
Sequences should all be in 1 file.
7 formats accepted: NBRF/PIR, EMBL/SwissProt, Pearson (Fasta), GDE, Clustal, GCG/MSF, RSF. Enter the name of the sequence file: anti.fasta<rtn> Sequence format is Pearson Sequences assumed to be PROTEIN Sequence 1: ANP4_PSEAM Sequence 2: ANP_LIMFE Sequence 3: ANPA_PSEAM Sequence 4: ANPX_PSEAM Sequence 5: ANPY_PSEAM 85 aa 97 aa 82 aa 91 aa 91 aa
• 依据进化树，开始对关系较 近的序列进行两两比对 • 逐渐加入关系较远的序列进 行比对 • 构建多序列比对
Human Mouse Dmel Cele Scer
Multiple alignment
一般累进比对方法
d
1 3
1 3 2 5
1 3 2 5
root
1 3 2 5 4
累进算法的一些问题
比对的准确性高度依赖于开始选择的 双序列比对 序列关系越远发生的错误可能越高 选择合适的打分矩阵和罚分准则较困 难
局部序列比对
概形分析 (Profile Analysis) 区块分析 (Block Analysis) 统计学方法 (Statistical Methods）
在多序列比对前要考虑的问题
比对的优劣与序列条数正相关 避免在比对中包括相似度 >80%的序 列 每个亚群应分别先比对，然后再整体 比对
动态规划算法(Dynamic Programming)
Mac Vector界面的ClustalW
ClustalX介绍
ClustalX介绍
ClustalX介绍
ClustalX介绍
ClustalX介绍
Example
Multiple sequence alignment of 7 neuroglobins using clustalx
PILEUP
多序列比对
(Multiple Alignments)
我们为什么做多序列比对?
寻找蛋白质家族，识别多个序列的保守区 域
相似的蛋白质序列往往具有相似的结构与 功能 辅助预测新序列的二级或三级结构
可以直观地看到基因的哪些区域对突变敏 感 PCR引物设计
我们为什么做多序列比对?
分析多个序列建进 化树的初使步骤 寻找个体之间单核苷酸多态性(SNPs)
SP方法通过对一个随机数据矩阵 中氨基酸对的所有可能组合的记 分求和来获得矩阵记分
SP 方法例子
S S I I S K K E
-8 - 8 + 4 = -12
使用 BLOSUM62 矩阵, 空位罚分为 -8 在第一列, 有三种两两 比对组合方式： -, S -, S S,S 每一列有k(k-1)/2 个双 序列比对
4. Phylogenetic trees S. Execute a system command H. HELP X. EXIT (leave program) Your choice: 2<rtn>
ClustalW
*************** ****** MULTIPLE ALIGNMENT MENU ****** *************** 1. Do complete multiple alignment now (Slow/Accurate) 2. Produce guide tree file only 3. Do alignment using old guide tree file 4. Toggle Slow/Fast pairwise alignments = SLOW 5. Pairwise alignment parameters 6. Multiple alignment parameters 7. Reset gaps between alignments? = OFF 8. Toggle screen display = ON 9. Output format options S. Execute a system command H. HELP or press [RETURN] to go back to main menu Your choice: 1<rtn>
Enter a name for the CLUSTAL output file [anti.aln]:<rtn>
Enter name for new GUIDE TREE file [anti.dnd]:<rtn>
Start of Pairwise alignments Aligning... Sequences (1:2) Aligned. Score: 62 Sequences (1:3) Aligned. Score: 59 Sequences (1:4) Aligned. Score: 84 Sequences (1:5) Aligned. Score: 83 Sequences (2:3) Aligned. Score: 68 Sequences (2:4) Aligned. Score: 80 Sequences (2:5) Aligned. Score: 79 Sequences (3:4) Aligned. Score: 81 Sequences (3:5) Aligned. Score: 80 Sequences (4:5) Aligned. Score: 98 Guide tree file created: [anti.dnd] Start of Multiple Alignment There are 4 groups Aligning... Group 1: Sequences: 2 Score:1476 Group 2: Sequences: 3 Score:1499 Group 3: Sequences: 4 Score:1190 Group 4: Sequences: 5 Score:1404 Alignment Score 3470 Consensus length = 102 CLUSTAL-Alignment file created [anti.aln]
累进算法(Progressive Methods)
针对基于动态规划算法的MSA程序比对序 列数目有限， Feng & Doolittle(1987)发明 了累进算法
CLUSTAL 和 PILEUP 是目前常用的基于 累进算法的比对软件 CLUSTAL 是免费软件,目前应用非常广泛
trasbg.fr/BioInfo/ClustalX/Top.html
通过序列比对发现直系同源(Orthologs)与 旁系同源(Paralogs)基因 寻找同源基因(相似的序列往往具有同源 性)
多序列比对与进化研究例子
图中NYLS为树根
一个多序列比对例子
VTISCTGSSSNIGAG-NHVKWYQQLPG VTISCTGTSSNIGS--ITVNWYQQLPG LRLSCSSSGFIFSS--YAMYWVRQAPG LSLTCTVSGTSFDD--YYSTWVRQPPG PEVTCVVVDVSHEDPQVKFNWYVDG-ATLVCLISDFYPGA--VTVAWKADS-AALGCLVKDYFPEP--VTVSWNSG--VSLTCLVKGFYPSD--IAVEWWSNG--
PILEUP是GCG(Genetics Computer Group) 软件包中的MSA分析工具 与CLUSTAL一样使用累进式整体比对方 法(Progressive Global Alignment) PILEUP开始的双序列比对使用 Needleman-Wunsch动态规划算法，所以 是全局序列比对，善于比较相似度较高 的序列