用计算机科学的术语来说，比对两个序列就是找出 两个序列的最长公共子序列（longest common subsequence，LCS），它反映了两个序列的最高 相似度。
动态规划法示意 （A）使用动态规划法寻找两个序列的最长公共部分；
（B）动态规划表的填写。
四、序列比对的作用
获得共性序列 序列测序 突变分析 种系分析 保守区段分析 基因和蛋白质功能分析
其他多序列全局比对方法
迭代法 基于一致性的方法 遗传算法
五、多序列局部比对
全局比对，其共同特征是序列中所有对应字符均假 定可以匹配，所有字符具有同等的重要性，空格的 插入是为了使整个序列得到比对，包括使两端对齐。
局部比对不假定整个序列可以匹配，重在考虑序列 中能够高度匹配的一个区段，可赋予该区段更大的 计分权值，空格的插入是为了使高度匹配的区段得 到更好的比对。
对于一个比对，不论使用什么计分函数进行计分， 相似性被定义为总等值于最大的计分：
对于k个序列，如果用一个函数cost（）对每一列
的所有替换操作进行计分，则多个序列之间的距 离等值于最小的计分：
对相似性的计分
编辑距离（edit distance）：一般用海明距离表示。
三、算法实现的比对
二、相似与距离的定量描述
相似性可定量地定义为两个序列的函数，即它可有 多个值，值的大小取决于两个序列对应位置上相同 字符的个数，值越大则表示两个序列越相似。
编辑距离（edit distance）也可定量地定义为两 个序列的函数，其值取决于两个序列对应位置上差 异字符的个数，值越小则表示两个序列越相似。
核苷酸转换矩阵
（三）蛋白质序列比对的替换计分矩阵
等价矩阵 遗传密码矩阵（GCM） 疏水性矩阵（hydrophobic matrix ） PAM矩阵 BLOSUM矩阵
PAM矩阵是从蛋白质序列的全局比对结果推导出来 的，而BLOSUM 矩阵则是从蛋白质序列块（短序列） 比对推导出来的。
可按照规则建立得分矩阵：
S（i,0） = 0, 0 ≤ i ≤ m S（0,j） = 0, 0 ≤ j ≤ n
配 S（i,j）=max
缺失不罚分
S（i-1,j-1）+ w（ai,bj） 匹配或错
S（i-1,j）+ w（ai,-） S（i,j-1）
插入
例如，对于序列a=ACACACTA，序列b=AGCACACA， 计分规则w（匹配）=+2；w（a,-）=w（-,b）=w
PAM/BLOSUM矩阵编号与序列亲缘关系的比较
二、双序列全局比对
动态规划算法的思想
⑴ a, b是使用某一字符集∑的序列（DNA 或蛋白
质序列）；
⑵ m = a的长度； ⑶ n = b的长度； ⑷ S（i,j） 是按照某替换计分矩阵得到的前缀
a[1...i]与b[1...j]最大相似性得分；
⑸ w（c,d）是字符c和d按照替换计分矩阵计算的得分。
其次，根据序列间进化距离的离异度（divergence） 在比对的不同阶段使用不同的氨基酸替换矩阵；
第三，采用了与特定氨基酸相关的空缺（gap）罚分 函数，对亲水性氨基酸区域中的空缺予以较低的罚分；
第四，对在早期配对比对中产生空缺的位置进行较少 的罚分，对引入空缺和扩展空缺进行不同的罚分。
生物信息学
生物信息学
第二章 序列比对
南方医科大学 吉林大学
朱浩 李瑛
第一节 引 言
Section 1 Introduction
一 、同源、相似与距离
（一） 同源
两个序列享有一个共同的进化上的祖先，则这两 个序列是同源的。
对于两个序列，他们或者同源或者不同源，不能 说他们70%或8
处理子序列与完整序列（或短序列与长序列）比对
的一般过程是：设短序列a和长序列b，它们的长度 分别为La和Lb，比对是在b序列中寻找La长度的a序
列的过程。
四、多序列全局比对
多序列比对主要涉及四个要素： ①选择一组能进行比对的序列（要求是同源序列）； ②选择一个实现比对与计分的算法与软件； ③确定软件的参数； ④合理地解释比对的结果；
对2个序列进行全局和局部比对可得到完全不同的结果
基于隐马尔可夫模型的多序列比对方法
隐马尔可夫模型和3个蛋白质序列PHSFTYVMT、PGSFTYW、 RFTGFW的最小公共超图
同源可分为垂直同源（ortholog）和水平同源（paralog）
垂直同源与水平同源
（二）相似性与距离
相似性、距离：是两个定量描述多个序列相似度 的度量。
相似性：被比对序列之间的相似程度。 距离：被比对序列间的差异程度。 相似性既可用于全局比对也可用于局部比对，而
距离一般仅用于全局比对，因为它反映了把一个 序列转换成另一个序列所需字符替换的耗费。
第二节 比对算法概要
Section 2 Alignment Algorithms
一、替换计分矩阵
（一）通过点矩阵对序列比较进行计分
A.两条序列完全相同
B.两条序列有一个共同的子序列
C.两条序列反向匹配
D.两条序列存在不连续的两条子序列
（二）DNA序列比对的替换计分矩阵
等价矩阵（unitary matrix） 转换-颠换矩阵（transition-transversion matrix） BLAST矩阵
对于接近或超过100个序列的多序列比对，渐进多序 列比对具有较高效率。最流行的渐进多序列比对软 件是Clustal家族。
ClustalW有以下特点： 首先，在比对中对每个序列赋予一个特殊的权值以
降低高度近似序列的影响和提高相距遥远的序列的 影响（如下图）。
ClustalW中对序列赋权的方法
与双序列比对一样，多序列比对也有全局比对 和局部比对。
（一）动态规划法进行多序列比对
计算三序列比对
（A）计算三个序列间的一个比对单元（i,j,k）依赖于其7个前导项； （B）计算u=ATGTTAT，v=ATCGTAC，w=ATGC三序列比对的三维得分矩
阵δ。
（二）渐进多序列比对
三个序列的配对比对未必能组合成一个多序列比对