BBQ（生信基础问题13）：序列比对专题

一： 前言

测序的数据下机之后，我们一般是需要进行回贴到参考基因组上进行后续分析的（序列比对这一步一般都比较耗时间。很多开发软件的生信程序员都想办法在各种优化mapping的效率。从SOAP到BWA,bowtie,bowtie2到最近的hisat，hisat2等）这次的BBQ我们主要聚焦在序列比对上：

我们一起思考几个问题：

1:我们为什么要进行序列比对？
2:目前有哪些序列比对的方法？这些方法是如何实现的呢？
3:如果遇到了indel怎么办？
4:此外，我们经常听说的mapping和alignment都有比对的意思。那么在生信上它们是一个意思吗？

二：什么是序列比对？序列比对的作用和意义是什么？

2.1：序列比对：

序列比对（sequence alignment）：是利用特定的数学模型或者是算法，找到两个或对个序列之前的最大匹配的碱基数或者是氨基酸残基数，其结果反映了序列之前的相似性关系及它们的生物学特征

2.2：序列比对的作用：

2.2.1：基于相似性的鉴定及功能预测（如果序列保守的话，那么功能也可能会相似）
2.2.2：可能在同源进化上有共同祖先（序列相似性是构建演化树的重要依据之一）

2.3:Question

2.3.1：什么是同源？
2.3.2：序列相似一定同源吗？
2.3.3：同源蛋白的序列会一定相似吗？

2.4:Answer

2.4.1：同源，最基本的意义就是具有共同祖先。同源性一般是指两种核酸分子的核苷酸序列之间或两种蛋白质分子的氨基酸序列之间的相似程度。
2.4.2：序列相似不一定同源，有可能高级结构不同，导致其功能不同
2.4.3：即使是同源蛋白其序列也不一定会相似，如肌红蛋白和β球蛋白，他们的氨基酸序列相似性不到40%

三：如何进行序列比较？

举个栗子：（图中序列比对的上的用“|”来表示）
以图片中的两条DNA序列进行比较，如果直接是按照其首尾排序而不采取任何措施，得到的结果如下：

直接排序

但是如果采取了一定的方式呢？（比如说向后移动了2个碱基的位置）

向后移动了2个bp后的比对结果
是不是可以直接看到比对的结果明显得到了改善和提升？
那么问题来了：

如何进行序列排序比对？原理是什么？

3.1全局序列比对（Needleman-Wunsch算法）

全局比对是全部待研究的序列都参加比较
（也就是两条序列无论长短，所有序列都必须比对上，如果序列长度不一样，通过插gap补齐）

3.2局部序列比对（Smith-Waterman算法）

不必对两个完整的序列进行比对，取每个序列中使用某些部分来获得最大得分。
（重点是找到匹配得分最高的序列，长度不一定要完全一样）
（有一些蛋白的结构相差甚远，但是如果有相同的功能域的话是不是也可以有类似的表达功能？利用局部序列比对是不是可以找到这些相似的序列呢？）

局部序列比对的选择 这两种比对方式都是基于动态规划算法

          错配or插gap看看那个分值大选哪个呗~

动态规划矩阵

下一个框框里的分值等于它前面斜上，左上，垂直上方三个数值的分值+它这次自身匹配的分值的和取最大

这里贴一个讲全局比对算法很好的帖子：
比对算法的原理及代码实现
既然是需要通过得分来得到最优解，那么就必须得有一个初始的打分矩阵。
以BBQ的第13问中的打分矩阵为例，我们来完成这个这个表格。

矩阵打分表和需要比对的序列
计算结果
全局比对结果

如果是局部比对呢？比对的原则是从最大的数值开始比对，然后比对到0结束，我们来看一下比对的打分矩阵的是什么样的

！！！Notice：
Smith-Waterman算法仅在此基础上加入一个0值，让上述三个方向上的值与0，共四个值比较大小。而且在最开始初始化矩阵时将初始行初始列的值都设为0。这样整个矩阵中的值没有负值。因此可以从任何位置开始，后面回溯时从矩阵中最大的值开始回溯

局部比对结果3种解，用不同的颜色标记出来了

什么时候利用全局比对，什么时候利用局部比对呢？
个人理解：如果是比对同源性方面的话可以进行全局比对，如果是寻找保守的特殊功能域的话可以进行局部序列比对。

Reference:
生物信息学100个基础问题 —— 第13题 从双序列比对开始学起
生物信息学：导论与方法(北京大学)
比对算法的原理及代码实现
---------------------------------------------分割线----------------------------------------------------------
附上学习笔记

BBQ（生信基础问题13）：序列比对，BLAST专.png