当序列差异较大时，上述问题更加明显。
例如
三条序列：
Seq1: ARKCV Seq2: ARCV Seq3: AKCV
若Seq1,2先比对， 再加入Seq3：
ARKCV AR-CV A-KCV ARKCV A-RCV A-KCV
ARKCV AR-CV AK-CV
Seq1,3先比对，再 加入Seq2: Seq2,3先比对，再 加入Seq1:
rij 2 lg 2(q / e)
BLOSUM62打分矩阵
BLOSUM & PAM
序列相似性与PAM及BLOSUM矩阵的大致 对应关系：
序列相似性 % PAM数值
99 1 90 11 80 23 70 38 60 56 50 80 40 30 20
112 159 246
BLOSUM数值
90
渐进比对
每条序列的权值
ClustalW的打分原则
Score:BLOSUM62的分数
ClustalX的使用
1. FASTA序列格式，多序列：
ClustalX的使用 ——导入序列文件
执行比对
文件导出
多序列比对：结果处理
BioEdit, GeneDoc等软件
GeneDoc软件，导入.aln文件
PAM矩阵
71个蛋白质家族的1572种变化； 序列相似性 > 85%； 功能同源的蛋白质 通过中性进化，引入 可接受的点突变； 进化模型：
A. 基本假设：中性进化，Kimura,1968; B. 进化的对称性: A->B = B->A; C. 扩展性：通过对较短时间内氨基酸替代关系 的计算来计算较长时间的氨基酸替代关系；
BLOSUM62矩阵构建步骤：
1. 提取Prosite数据库中504个家族的2万多蛋 白质序列（含1961个Blocks），合并其中 相似性≥62%的序列； 2. 统计各BLOCK的氨基酸对数量f； 3. 计算氨基酸对的出现频率q； 4. 计算每种氨基酸的期望频率p； 5. 计算氨基酸对出现的期望频率e； 6. 计算BLOSUM62矩阵分量rij
80
62-45
第三节， 多序列比对
不同物种中，许多基因的功能保守，序列相 似性较高，通过多条序列的比较，发现保守 与变异的部分； 可构建HMM模型，搜索更多的同源序列； 构建进化树的必须步骤； 比较基因组学研究； 两类：全局或局部的多序列比对；
全局性的多序列比对
Made by GENEDOC
1. 渐进方法：progressive methods
代表：ClustalW/X, T-Coffee
2. 迭代方法：iterative methods
代表: PRRP, DIALIGN
3. 部分有向图算法：
Partial Order Algorithm (POA)
4. 全局多序列比对的隐马尔科夫模型
Dayhoff: PAM系列矩阵 Henikoff: BLOSUM系列矩阵
核苷酸替代：转换 & 颠换
转换：嘌呤被嘌呤 替代，或者嘧啶被 嘧啶替代 颠换：嘌呤被嘧啶 替代，或者嘧啶被 嘌呤替代
1，核酸序列比对的打分方法
等价/匹配计分： 相同的核酸记1分，否则记0分 BLAST中核酸比对计分： 相同的核酸记5分，否则记-4分 转换-颠换矩阵计分： 转换记 -1分，颠换记 -5分
profile HMM
5. 整合算法： MUSCLE
1. Progressive methods
ClustalW/X T-Coffee
(1) ClustalW/X
Clustal: 1988年开发； ClustalW: 1994年，Julie D. Thompson 等人改进、发展； ClustalX: 1997年，图形化软件；
双序列比对
时间复杂度：O(n2)
Gap V
4
D
S
C
Y
Gap
V E
0
-11 -22
-11
4 -7
2
-22
-7 6
-33
-18 -5
-44
-29 -16
-55
-40 -27
S L
C Y
-33 -44
-55 -66
-18 -29
-40 -51
-5 -16
-27 -38
10 -1
-12 -23
-1 9
8 -3
(1) 对两条序列，计算距离采用k-mer的思想； (2) 用UPGMA算法构建引导树； (3) 使用渐进算法进行多序列比对；
优点：两条序列之间的距离不采用动态规划 算法进行比对，节省时间。
MUSCLE
2. Improved progressive:
(1)基于k-mer得到的树可能会产生次优结果，因
ClustalW/X：计算过程
1. 将所有序列两两比对，计算距离矩阵； 2. 构建邻接进化树(neighbor-joining tree)/ 指导树(guide tree)； 3. 将距离最近的两条序列用动态规划的算法 进行比对； 4. “渐进”的加上其他的序列。
两两比对，构 建距离矩阵
指导树的构建
生物信息学
第三章 序列比对 Ⅱ
本章内容提要
第一节：双序列比对算法的介绍
Dot matrix 动态规划算法
(Needleman-Wunsch, Smith-Waterman算法)
FASTA和BLAST算法
第二节：打分矩阵及其含义 第三节：多序列比对
第二节 打分矩阵及其含义
1，核酸序列比对的打分方法 2，蛋白序列比对的打分方法
PAM1矩阵，乘以10000
PAM2矩阵
基本假设：每个氨基酸的突变的概率独立于 前次突变。因此，PAM2=PAM1*PAM1
PAM250矩阵
PAM250: 每100个氨基酸残基发生250次突 变； 蛋白质序列仍然有15-30%左右的相似性；
PAM250打分矩阵
打分矩阵的使用
PAM250: ~15-30%的序列相似 性； PAM120: ~40%的序列相似性； PAM80: ~50% PAM60: ~60% 如何选择最合适的矩阵？ 多种尝试…
A A T C G 1 0 0 0 T 0 1 0 0 C 0 0 1 0 G 0 0 0 1 A T C G A 5 T -4 C -4 -4 5 -4 G -4 -4 -4 5 A T C G
A
T C G
1
-5
-5 -1
-1 -5 1 -5
-4 5 -4 -4 -4 -4
-5 1 -5 -1 -1 -5
PAM1矩阵
两个蛋白质序列的~1%氨基酸发生变化； 定义进化时间以氨基酸的变异比例为准， 而不是时间；因为各个蛋白质家族进化的速 度并不相等； PAM2 = PAM1*PAM1 PAM3 = (PAM1)3 PAM25
选取多个家族的相似性>85%的保守序列； 根据匹配计分进行多重比对(不含空位)； 以比对结果构建进化树，反映氨基酸替换关系； 计算每种氨基酸转换成其它氨基酸的次数； 计算每种氨基酸突变率； 计算每对氨基酸突变率，得到突变概率矩阵， 将此矩阵自乘n次； 将突变概率矩阵转化为PAMn打分矩阵。
PAM矩阵的问题及改进
PAM系列矩阵存在的问题：
A. 氨基酸的打分矩阵，不关心核酸； B. 进化模型的构建需要系统发育树的分析，因此 ，成为一个循环论证的问题：序列比对矩阵构 建打分进行新的序列比对； C. 数据集很小；
打分矩阵的改进
A. 选用大量的序列数据，构建PAM矩阵； B. BLOSUM系列矩阵; C. 核酸的打分矩阵;
PAM系列矩阵
Margaret Dayhoff, 1978; 通过对物种进化的研究，根据一种氨基酸被 另一种氨基酸替代的频度而提出的，最常用 的是PAM250; 假设，蛋白质序列各部位进化的速率是均等 的；氨基酸变化频率不随进化时间改变，短 期进化历史内观察到的置换可以推广到较长 的历史。 Accepted point mutation (PAM): 可接受 的点突变，氨基酸的改变不显著影响蛋白质 的功能；
/CBBresearch/Schaff er/msa.html /general/software/packages/m sa/manual/manual.php
MSA： 打分方式
多序列比对：方法改进
-5 1
等价矩阵
BLAST矩阵
转换-颠换矩阵
2，蛋白序列比对的打分方法
等价/匹配计分： 相同的氨基酸记1分，否则记0分 结构域性质计分： SGM矩阵(Structure-Genetic Matrix) 主要根据氨基酸的结构和化学性质的相似程度 来记分(如D和E，S和T，V和I有很高的相似性)，同 时还考虑密码子之间相互转换的难易程度。 可观测变换计分： PAM矩阵 (Point Accepted Mutation) BLOSUM矩阵 (BLOcks SUbstitution Matrix)
2. 迭代方法
部分解决渐进算法存在的问题,主要是 ClustalW/X存在的问题； PRRP DIALIGN
(1) PRRP
1. 先用“渐进”算法进行 多序列比对;
2. 基于多序列比对的结果 构建进化树；
3. 重新计算序列之间的距 离，再用“渐进”算法进行 多序列比对； 4. 重复上述步骤，直到结 果不再发生改变为止。
-12 -3
7 15
多序列比对：最优算法
多项式时间复杂度要求：≤O(n3)
三条序列：时间复杂度：O(lmn) = O(n3) 四条序列：时间复杂度：O(n4)，非多项式时间！ … m条序列：时间复杂度：O(nm)！