seed extension算法（Needleman-Wunsc

比较两条序列的相似性，不可能用眼睛去比较。因此，序列比对法是序列比对的标准方法。
这篇文章主要讲科学家使用动态规划算法，运用特定的算法找出两个或多个序列之间产生最大相似度得分的空格插入和序列排列方案。该算法更多得应用在比对软件的seed extensio步骤。
例如：将测序获得的reads比对到参考基因组时，如何将携带变异的reads，通过空格插入 或 序列排列而 mapping到正确的参考序列？

1. 序列比较相关的指标

描述序列相似的两个指标：

• 一致度：如果两个序列（蛋白质或核酸）长度相同，那么它们的一致度定义为它们对应位置上相同的残基（一个字母，氨基酸或碱基）的数目占总长度的百分数。
• 相似度：如果两个序列（蛋白质或核酸）长度相同，那么它们的相似度定义为它们对应位置上相似的残基与相同的残基的数目和占总长度的百分数。（残基两两相似的量化关系被替换记分矩阵所定义）

替换记分矩阵：反映残基之间相互替换率的矩阵，它描述了残基两两相似的量化关系。(分为DNA替换记分矩阵和蛋白质替换记分矩阵，这里只记录了DNA替换记分矩阵)

2. DNA序列的替换记分矩阵

3种常见的DNA序列的替换记分矩阵

• 1. 等价矩阵：最简单的替换记分矩阵，其中，相同核苷酸之间的匹配得分为1，不同核苷酸间的替换得分为0。由于不含有碱基的理化信息和不区别对待不同的替换，在实际的序列比较中较少使用。
• 2. 转换-颠换矩阵：核酸的碱基按照环结构特征被划分为两类，一类是嘌呤（腺嘌呤A、鸟嘌呤G），它们有两个环；另一类是嘧啶（胞嘧啶C、胸腺嘧啶T），它们只有一个环。如果DNA碱基的替换保持环数不变，则为转换，如A-->G、C-->T；如果环数发生变化，则为颠换，如A-->C、T--> G。在进化过程中，转换发生的频率远比颠换高。为了反映这一情况，通常该矩阵中 “转换” 的得分为 -1，而 “颠换” 的得分为 -5.
• 3. BLAST矩阵：经过大量实际比对发现，如果令被比对的两个核苷酸相同时得分为+5，反之为-4，则比对效果较好。这个矩阵广泛地被DNA序列比较所采用。

3. 序列比对法的概念

序列比对（alignment）: 也叫对位排列、联配、对齐等。运用特定的算法找出两个或多个序列之间产生最大相似度得分的空格插入和序列排列方案。

举例理解：
序列s和t的比对：把s和t这两个字符串上下排列起来，在某些位置插入空格（空位，gap），然后依次比较它们在每一个位置上字符的匹配情况，从而找出使这两条序列产生最大相似度得分的排列方式和空格插入方式。

3.1 全局比对和局部比对

双序列比对：比较两条序列（根据算法不同分位全局比对和局部比对）

• 全局比对：用于比较两个长度近似的序列
• 局部比对：用于比较一长一短两条序列

3.2 空位罚分体系

存在意义：补偿插入和缺失对序列相似性的影响
目前常用的空位罚分体系有两种：

• liner penalty
  -- 1个gap罚b分
  -- n个空位罚 n*b分
• affine penalty（更符合进化原理）
  -- 空位引入（gap open penalty）罚分大
  -- 空位延伸（gap extension penalty）罚分小

4. Needleman-Wunsch算法

1970年，Saul Needleman 和 Christian Wunsch两人首先将 动态规划算法 应用于两条序列的全局比对，这个算法后称为Needleman-Wunsch算法。
对于以下两条序列：
序列p: ACGTC（在得分矩阵中横向排列）
序列q: AATC（在得分矩阵中纵向排列）

得分矩阵（0，0）处的值固定为0，参考 替换记分矩阵 完善序列比对的得分矩阵

Needleman-Wunsch算法-全局比对

追溯箭头就是红色部分（从右下角到左上角）
其他任何一种插入空位的比对结果，得分都不会超过21分，因为我们在得分矩阵的创建过程中，每一步都是在上一步最优的情况下得出的当前最优结果。

因此，序列p和序列q产生最大相似度得分的空格插入和序列排列方案为：
序列p：ACGTC
序列q：A - ATC

全局比对的结果

5. Smith-Waterman算法

与Needleman-Wunsch算法的全局比对十分类似，Smith-Waterman算法作为局部比对的算法，只是在筛选最大值是增加了常量0。
也就是说，如果最优比对到达某个位置的时候，它的得分小于0，此时最好开始一个新的局部比对，而不是在原有比对基础上继续延伸。

Smith-Waterman算法-局部比对

局部比对的结果不是在右下角，而是在整个矩阵中找最大值，最大值才是局部比对的最大得分。箭头的追溯也是从刚刚找到的最大值追溯到没有箭头为止。

局部比对的结果

如何计算 一致度 和 相似度？
如果两个序列长度相同：
一致度=（一致字符的个数 / 全局比对长度）*100%
相似度=（一致及相似的字符的个数 / 全局比对长度）*100%
如果两个序列长度不同：
一致度=（一致字符的个数 / 全局比对长度）*100%
相似度= （一致及相似的字符的个数 / 全局比对长度）*100%
attention⚠️: 无论两个序列长度是否相同，都要先做双序列全局比对，然后根据比对结果及比对长度计算它们的一致度和相似度。

Smith-Waterman算法的优势：

• 寻找两条序列中局部保守的结构域
• 两条长度差异较大的序列的比对
• 两条整体相似度不高的序列中的保守位点
• 两条序列重叠区域的寻找