为确定两个或多个序列之间的相似性以至于同源性，而将它们按照一定的规律排列。将两个或多个序列排列在一起，标明其相似之处。序列中可以插入间隔（通常用短横线“-”表示）。对应的相同或相似的符号（在核酸中是A, T（或U）, C, G，在蛋白质中是氨基酸残基的单字母表示）排列在同一列上。这一方法常用于研究由共同祖先进化而来的序列，特别是如蛋白质序列或DNA序列等生物序列。在比对中，错配与突变相应，而空位与插入或缺失对应。序列比对还可用于语言进化或文本间相似性之类的研究。术语“序列比对”也指构建上述比对或在潜在的不相关序列的数据库中寻找significant alignments。
基因组重测序中序列比对介绍
重测序基因组数据比对，是指将测序仪下机fastq数据（NGS read序列，通常100-150bp），与人类参考基因组（reference）进行匹配，允许错配（mismatch），插入缺失（indel），目的是在参考基因组找到序列最相似的位置，通常是基因组分析(包括 variation calling，ChIP-seq，RNA-seq，BS-seq)流程的第一步。
常用算法
图一
汉明距离（Hamming distance）表示两个（相同长度）字对应位置不同的数量，我们以d（x,y）表示两个字x,y之间的汉明距离。对两个字符串进行异或运算，并统计结果为1的个数，那么这个数就是汉明距离。图中read1最佳位置的方法，就是通过查找最小汉明距离的实现的。
编辑距离（Edit distance）是针对二个字符串（例如英文字）的差异程度的量化量测，量测方式是看至少需要多少次的处理才能将一个字符串变成另一个字符串。图中read3最佳位置，通过查找最我辑距离的方法实现。
图二
全局比对（Global alignment）：全局比对是指将参与比对的两条序列里面的所有字符进行比对。全局比对在全局范围内对两条序列进行比对打分，找出最佳比对，主要被用来寻找关系密切的序列。其可以用来鉴别或证明新序列与已知序列家族的同源性，是进行分子进化分析的重要前提。其代表是Needleman-Wunsch算法。图一中，read3使用全部比对。
局部比对（Local alignment）：与全局比对不同，局部比对不必对两个完整的序列进行比对，而是在每个序列中使用某些局部区域片段进行比对。其产生的需求在于、人们发现有的蛋白序列虽然在序列整体上表现出较大的差异性，但是在某些局部区域能独立的发挥相同的功能，序列相当保守。这时候依靠全局比对明显不能得到这些局部相似序列的。其次，在真核生物的基因中，内含子片段表现出了极大变异性，外显子区域却较为保守，这时候全局比对表现出了其局限性，无法找出这些局部相似性序列。其代表是Smith-Waterman局部比对算法。图一中，read2使用局部比对。
图三
Smith-Waterman算法介绍
Smith-Waterman是由Temple F. Smith和Michael S. Waterman于1981年提出的一种进行局部序列比对（相对于全局比对）的算法，用于找出两个核苷酸序列或蛋白质序列之间的相似区域。该算法的目的不是进行全序列的比对，而是找出两个序列中具有高相似度的片段。S-W算法基于动态规划，它接受任意长度、任意位置、任意序列的对齐，并确定是否能找到最优的比对。
简单地说就是，动态规划找到问题中较小部分的解，然后把它们放在一起，形成整个问题的一个完整的最优最终解。
它优于BLAST和FASTA算法，因为它搜索了更大的可能性，具有更高的敏感性。
S-W算法不是一次查看整个序列，而是对多个长度的片段进行比较，寻找能够最大化得分的片段。算法本身本质上是递归的：
图四
算法步骤如下：
基因组分析***** 微信 公众号推出 《50篇文章深入理解NGS》系列文章， 第三篇文章 《基因组序列比对算法介绍（一）》，争取每周更新一篇高质量生信干货帖子。
关注 "基因组分析" 微信公众号，了解最新最全生信分析知识。
序列比对通过比较生物分子序列，发现它们的相似性，找出序列之间共同的区域，同时辨别序列之间的差异，从而揭示生物序列的功能、结构和进化的信息。最常见的比对是蛋白质序列之间或核酸序列之间的两两比对，通过比较两条序列之间的相似区域和保守性位点，寻找二者可能的分子进化关系。还可以对多条蛋白质或核酸序列同时进行比较，寻找这些有进化关系的序列之间共同的保守区域、位点和概型，从而探索导致它们产生共同功能的序列模式。此外，还可以通过比较蛋白质序列和核酸序列相比来探索核酸序列可能的表达框架；把蛋白质序列与已知三维结构信息的蛋白质相比，从而获得蛋白质折叠类型的信息。欢迎分享，转载请注明来源：民族网
