比对算法

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

相似与一致与同源

一致度：如果两个序列（蛋白质或核酸）长度相同，那么它们的一致度定义为对应位置上相同的残基（氨基酸或碱基）的数目占总长度的百分比。
相似度：如果两个序列长度相同，则相似度定义为它们对应位置上相似的残基与相同的残基的数目和占总长度的百分数。
同源性只能用有没有来形容，不能说“70%同源”这种胡话，类似于“这个布尔函数^[1]有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分

和上一张差不多

转换/颠换矩阵^[2]

将一致的计+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基于局部比对。

GCM矩阵/遗传密码子矩阵

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

疏水矩阵

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

比对序列

动态规划

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

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

（有人知道这个点是怎么来的吗？道理上来说贪心算法不一定是全局最优）

1950由理查德贝尔曼（算法、数学家，并非生物学家）提出。

切记局部最优不是全局最优——~~信息巨佬补~~

~~来补了！以下是信息学内容：~~

其实应该是局部最优不一定是全局最优。

如果局部最优就是全局最优，可以应用贪心法；局部最优不是全局最优则动态规划。

动态规划原理包括最优子结构、无后效性。

最优子结构的意思是：对于一个给定的问题，当该问题的最优解可以由其子问题的最优解获得时，则该问题具有“最优子结构”性质。

无后效性，也就是马尔可夫性，后面的决策不能对前面的决策产生影响。

下面证明Needleman-Wunsch算法的正确性。定义f(i,j)表示序列A到了第i个碱基，序列B到了第j个碱基，最小罚分。

f(i,j)=min{f(i-1, j)-2, f(i, j-1)-2, f(i-1, j-1)+【A[i]与B[j]的是否匹配？+1或-1】}

无后效性显然。

前两个表示空位，最后一个表示匹配或错配。不难发现，对于问题f(i,j)，这样的子问题划分一定是完全的。f(i,j)的转移一定是A+B形式的，B是常数，A是前面走出来的罚分，我要A+B最小，A就要最小，也就是子问题的罚分也必然要最小。

那什么样的问题不满足最优子结构呢？还是一个走格子问题：绝对值走格子

在上面这个问题中，延续之前的状态定义f(i,j)表示走到格子(i,j)的和的最小绝对值。子问题划分还是完全的，但是如果当前A[i][j]碰到一个很大的负数，则前面我们希望有一个尽可能贴近A[i][j]的正数和最好，而非越小越好。

解决上面这个问题，重新定义状态：f(i,j,x)表示走到格子(i,j)，和的绝对值是x，是否可行。这种可行性的问题，只要子问题出现可行的，则当前问题就可行，显然满足最优子结构。但是要考虑此算法的时间空间复杂度问题，如果网格中每个数的绝对值都很小，也许就是一种可行的动态规划解法。如果x范围极大，动态规划则不可行，只能老老实实用meet-in-the-middle算法了。

希望以上能够帮助读者理解动态规划和贪心的区别，以及动态规划的正确性证明。