比对算法

介绍三种关于序列比对的算法，矩阵，进化树与更多

相似与一致与同源

• 一致度：如果两个序列（蛋白质或核酸）长度相同，那么它们的一致度定义为对应位置上相同的残基（氨基酸或碱基）的数目占总长度的百分比。
• 相似度：如果两个序列长度相同，则相似度定义为它们对应位置上相似的残基与相同的残基的数目和占总长度的百分数。
• 同源性只能用有没有来形容，不能说“70%同源”这种胡话，类似于“这个布尔函数有80%是0”
• 也就是说，一致度要求完全一样，相似度只要性质差不多也能算进去
• 同源性是定性概念，一致度和相似度是定量概念

比对类型

局部比对找出两个序列中高相似度的片段

全局比对构建打分矩阵，打分。。。

半局部比对对一条序列使用局部比对，另一条使用全局比对，如此求得最大匹配度

比对矩阵

如果希望对蛋白质或核酸序列进行比对，需要借助于矩阵（对于计分表的更高端叫法）打分，分高者相似

核酸矩阵

等价矩阵

将一致的计算为一分，不一致的计算为0分

等价矩阵

	A	T	C	G
A	1	0	0	0
T	0	1	0	0
C	0	0	1	0
G	0	0	0	1

BLAST矩阵

将一致的计算为+4分，不一致的计算为-5分

和上一张差不多

转换/颠换矩阵

将一致的计+1，转换计算-1，颠换计算-5

	A	T	C	G
A	1	-5	-5	-1
T	-5	1	-1	-5
C	-5	-1	1	-5
G	-1	-5	-5	1

蛋白质矩阵

PAM矩阵

PAM矩阵是目前蛋白质序列比较中最广泛使用的记分方法之一，基础的PAM-1 矩阵反应的是进化产生的每一百个氨基酸平均发生一个突变的量值（统计方法得到）。

PAM-1是由相似度大于85%的序列计算产生

PAM-1 自乘n次，可以得到PAM-n，即发生了多次突变。也就是说PAM越大，相似度越小。n即允许发生的点突变数。

BLOSUM矩阵

BLOSUM 矩阵都是通过对大量符合特定要求的序列计算而来。如BLOSUM62表示计算了相似度>62%的蛋白质序列得到结果

PAM基于全局比对，BLOSUM基于局部比对

比较PAM和BLOSUM

GCM矩阵/遗传密码子矩阵

两个氨基酸之间密码子所需的突变次数越多，替换代价越大（多用于进化树）

疏水矩阵

疏水性相近的氨基酸得分更高

比对序列

动态规划

核心原理是，如果你每一步都是最优解，那最后也一定是最优解

也就是说，因为你在列表走格子的时候每次都取了最优解，所以比对结果也应该是最优解

1950由理查德贝尔曼开发

打点法

compare cat brothers

首先您需要找到两条序列THEFASTCAT和THEFATCAT

将他们将两条序列用这一张图中的方法分别列出，形成一个二维表格，在字母相同（实际上是氨基酸相同）的位置打上点

如果您发现打点后产生了对角线或者与其相同的平行线，这些区域具有一致性

可用于寻找序列中的重复片段

许多名字里带有Dot的软件可以用打点法比对序列如Dnadot，（dotlet似乎属于SIB

全局比对之Needleman-Swunch算法

1970年由名字里的二人开发

换一种方法理解打点法，您会发现她很像一种打分，只不过是0/1

Needlemanswunch矩阵初始化

下面我们使用更加酷炫的动态规划（走格子），Needleman-Swunch的走格子步骤如下

1，初始化矩阵，将两条序列用上一张图中的方法分别列出并且在开头处空一格，形成一个二维表格，在表格的左上角的边缘打上0，-1，-2，。。。一直到表格结束

2