序列比对算法哪年出现

Ⅰ 基因组序列比对算法介绍（一）

基因组重测序中序列比对介绍

重测序基因组数据比对，是指将测序仪下机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》系列文章， 第三篇文章 《基因组序列比对算法介绍（一）》，争取每周更新一篇高质量生信干货帖子。

关注 "基因组分析" 微信公众号，了解最新最全生信分析知识。

Ⅱ 序列比对算法

序列比对算法是生物信息学领域中不可或缺的一部分，其主要目标是寻找序列之间的相似性，这在数据库搜索、基因组分析和功能预测等应用中极为重要。在序列比较过程中，理解和掌握相似性、同源性概念以及序列比较的指标和算法对于深入研究生物序列分析至关重要。

序列比较的基本概念涉及由ATCG（RNA为AUCG）组成的核酸序列和由氨基酸缩写组成的蛋白质序列。这些序列通常以FASTA格式存储，如图1所示，其中第一行为序列名称或注释，之后为序列主体，每行60-80个字母，具体格式根据数据库和文件类型而定。

在序列比较中，相似性与同源性是核心概念。相似性是指通过算法或工具快速找到序列间的相似之处，这在大型数据库中尤为关键。同源性则表明两个序列具有共同的祖先，意味着它们在结构和功能上可能存在相似之处。通过序列的相似性，我们可以推断未知序列的结构和功能，这是蛋白质功能预测等研究领域的重要工具。

同源性可以分为直系同源和旁系同源。直系同源是指不同物种间共享的序列，来源于同一个祖先序列；旁系同源则指由于物种内部基因复制而产生的序列差异。例如，人α珠蛋白、β珠蛋白和肌红蛋白为旁系同源，而它们的基因也是旁系同源。

序列比较的指标包括一致度和相似度。一致度描述了在相同长度的序列中，对应位置上相同残基的比例，而相似度则考虑了替换积分矩阵（subsitution matrix）统计的不同位置残基之间的相似性量化关系。在计算相似度时，还需考虑序列不同长度的问题，通过引入空位罚分制度，使不同长度序列对齐后进行比较。

DNA序列替换记分矩阵包括等价矩阵、转换—颠换矩阵和BLAST矩阵。等价矩阵简单地以相同碱基为正，不同碱基为零，但由于其不考虑碱基的理化信息，实际应用较少。转换—颠换矩阵根据转换和颠换发生的频率不同，给予相应得分数，而BLAST矩阵则基于大量实际比对结果，优化了转换和颠换的得分。

蛋白质替换记分矩阵主要有等价矩阵、PAM矩阵、BLOSUM矩阵、遗传密码矩阵和疏水矩阵。等价矩阵与DNA替换矩阵类似，简单地以相同氨基酸为正，不同氨基酸为零。PAM矩阵基于进化原理，反映了自然界易接受的氨基酸替换频率。BLOSUM矩阵则通过统计相似度大于特定阈值的序列，得到更为精确的替换得分矩阵。遗传密码矩阵和疏水矩阵则分别从密码子变化和氨基酸疏水性变化的角度考虑序列的相似性。

双序列比对操作实例展示了如何使用蛋白质序列比对网站，如Pairwise Sequence Alignment，结合选择的替换记分矩阵，对人血红蛋白的α和β亚基进行比对。通过计算得到的相似度、一致度和最终比对得分，有助于理解序列间的相似性和同源性。

序列比对的算法包括打分矩阵法、动态规划模型和Blast算法。打分矩阵法通过枚举所有可能的比对组合来寻找最优解。动态规划模型则通过构建状态转移矩阵，以动态规划的思想逐步求解最优比对路径。Blast算法则采用种子-延伸策略，快速查找局部相似性，并评估比对的显着性，通过E值衡量随机匹配的可能性。

全局比对和局部比对的区别在于，全局比对旨在寻找序列间的整体最优匹配，而局部比对则关注于识别具有高度相似性的局部序列区域。空位罚分的改进通过引入状态的概念，使得动态规划模型在空位开始与空位延伸之间进行更精确的区分。

BLAST算法是序列比对的常用方法，它首先找到高度相似的种子片段，以此为基础向两端扩展比对，并通过统计显着性评估比对质量，以避免假阳性结果。此外，BLAST还采取了屏蔽低复杂度区域和考虑相似邻居words等策略，以提高速度和灵敏度。

隐马尔可夫链（HMM）在序列比对中进一步引入了生成概率的概念，使得模型不仅考虑状态转移概率，还能预测观察到的符号序列，从而在比对过程中提供更精确的分析。

综上所述，序列比对算法是生物信息学中的一项关键技术，通过理解相似性、同源性概念以及序列比较指标，结合不同算法和策略，可以高效地分析和理解生物序列之间的关系，对生物功能预测、基因组比较和进化研究等领域具有重要意义。

Ⅲ 详细介绍双序列比对、blast 以及多序列比对的区别,以及均适用于哪些场 景

序列比对是将两个或多个序列排列在一起，标明其相似之处。使用间隔表示未比对上，比对上的相同或相似的符号排列在同一列上。序列比对是生物信息学以及基因组学与进化的基础之一，其基本思想是：在生物学中普遍存在的序列决定结构、结构决定功能的规律，通过将核酸序列或者蛋白质序列的一级结构看成由基本字符构成的字符串，通过序列比对我们可以找到相似的序列并由此发现生物序列中的功能、结构和进化信息。
全局比对：全局比对是指将参与比对的两条序列里面的所有字符进行比对。全局比对在全局范围内对两条序列进行比对打分，找出最佳比对，主要被用来寻找关系密切的序列。其可以用来鉴别或证明新序列与已知序列家族的同源性，是进行分子进化分析的重要前提。其代表是Needleman-Wunsch算法。
局部比对：与全局比对不同，局部比对不必对两个完整的序列进行比对，而是在每个序列中使用某些局部区域片段进行比对。其产生的需求在于、人们发现有的蛋白序列虽然在序列整体上表现出较大的差异性，但是在某些局部区域能独立的发挥相同的功能，序列相当保守。这时候依靠全局比对明显不能得到这些局部相似序列的。其次，在真核生物的基因中，内含子片段表现出了极大变异性，外显子区域却较为保守，这时候全局比对表现出了其局限性，无法找出这些局部相似性序列。其代表是Smith-Waterman局部比对算法。
双重序列比对：双序列比对是指对两条序列M和N进行比对，找到其相似性关系，这种寻找生物序列相似性关系的过程被称为双序列比对。其算法可以主要分成基于全局比对的Needleman-Wunsch算法和基于局部比对的Smith-Waterman局部比对算法
多重序列比对：多序列比对是双序列比对推广，即把两个以上字符序列对齐，逐列比较其字符的异同，使得每一列字符尽可能一致，以发现其共同的结构特征的方法称为多序列比对。多序列比对算法可以分成渐进法和同步法。其可以发现不同的序列之间的相似部分，从而推断它们在结构和功能上的相似关系，主要用于分子进化关系，预测蛋白质的二级结构和三级结构、估计蛋白质折叠类型的总数，基因组序列分析等。
基因组比对：是多序列比对的一种特例，指对基因组范围内的序列信息进行比对的过程。通过对不同亲缘关系物种的基因组序列进行比较，能够鉴定出编码序列、非编码调控序列及给定物种独有的序列。而基因组范围之内的序列比对，可以了解不同物在核苷酸组成、同线性关系和基因顺序方面的异同，进而得到基因分析预测与定位、生物系统发生进化关系等方面的信息。
BLAST：BLAST[1]（Basic Local Alignment Search Tool）是在在1990年由Altschul等人提出的双序列局部比对算法，是一套在蛋白质数据库或DNA数据库中进行相似性比较的分析工具。BLAST是一种启发式算法，用于在大型数据库中寻找比对序列，是一种在局部比对基础上的近似比对算法，可以在保持较高精度的情况下大大减少程序运行的时间。
算法思想描述：
双重序列比对主要分成以Needleman-Wunsch算法为代表的全局比对和以Smith-Waterman局部比对算法为代表的局部比对，BLAST是局部比对的一种推广。多重比对算法可以主要分成动态规划算法、随机算法、迭代法和渐进比对算法。
（1）双重序列比对：
Needleman-Wunsch算法：该算法是基于动态规划思想的全局比对的基本算法，动态规划的比对算法的比对过程可以用一个以序列S为列，T为行的(m+1)×(n+1)的二维矩阵来表示，用
sigma表示置换矩阵。
在计算完矩阵后，从矩阵的右下角单元到左上单元回溯最佳路径（用箭头表示），根据最佳路径给出两序列的比对结果。其中，斜箭头表示2个残基匹配，水平箭头表示在序列S的相应位置插入一个空位，垂直方向的箭头表示在序列T的相应位置插入一个空位。

Smith-Waterman算法：该算法是一种用来寻找并比较具有局部相似性区域的动态规划算法，这种算法适用于亲缘关系较远、整体上不具有相似性而在一些较小的区域上存在局部相似性的两个序列。该算法的基本思想是：使用迭代方法计算出两个序列的相似分值，存在一个得分矩阵M中，然后根据这个得分矩阵，通过动态规划的方法回溯找到最优的比对序列。与全局比对相比，这种算法的改变是把矩阵单元值为负者一律取为0，这是因为分值为负的比对丧失了比对的生物学意义，因此把得分为负值的子序列丢弃。

BLAST: BLAST算法的基本思想是通过产生数量更少的但质量更好的增强点来提高比对的速度。算法的原理主要分为以下五步：（1）过滤：首先过滤掉低复杂度区域，即含有大量重复的序列；（2）Seeding：将Query序列中每k个字组合成一个表，即将一个序列拆分成多个连续的‘seed words’（通常蛋白质k=3，核酸k=11）；（3）比对：列出我们所关心的所有可能的字组，再配合置换矩阵给出高分值的字组并组织成快速搜索树结构或者哈希索引，因此此步骤可以快速搜索出大数据集中的所有匹配序列，找到每个seed words在参考序列中的位置；（4）延伸：当找到seed words的位置后，接下来需要将seed word延伸成长片段，延伸过程中，得分值也在变化，当得分值小于阈值时即停止延伸，最后得到的片段成为高分片段对，HSP（High-scoring segment pair）；（5）显着性分析，最后我们使用如下公式计算E值，E值衡量了在随机情况下，数据库存在的比当前匹配分数更好的比对的数目，因此可以用该值作为指标评价HSP比对序列的可信度。
其中，m是数据库长度，n是query的长度，S是HSP分数，其他两个参数是修正系数。

（2）多重序列比对

动态规划算法：其基本思想是将一个二维的动态规划矩阵扩展到三维或者多维，多序列比对的积分是n个序列中两两进行比对所得积分之和。矩阵的维度反映了参与比对的序列数。这种方法对计算资源要求比较高[6]。
随机算法：主要包括遗传算法和模拟退火算法，遗传算法是一类借鉴生物界进化规律演化来的全局意义上的自适应随机搜索方法。当用遗传算法进行生物序列分析时，每一代包含固定数量的个体，这些个体用他们的适应度来评价。变异则模拟了生物进化过程中的偶然残基突变现象。对产生的新一代群体进行重新评价、选择、交叉、变异，如此循环往复，使群体中最优个体的适应度不断提高，直到达到一个阈值，算法结束。模拟退火的基本思想是用一物质系统的退火过程来模拟优化问题的寻优方法，当物质系统达到最小能量状态时，优化问题的目标函数也相应地达到了全局最优解。这两种方法都是对构造好的目标函数进行最优解搜索，但实际比对效果并不好[6,7]。
迭代法：迭代法的代表是Muscle[8], Muscle是一个新的渐进比对和迭代比对的综合算法，主要由两部分构成，第一部分是迭代渐进比对：第一次渐进比对的目的是快速产生一个多序列比对而不强调准确率，以此为基础再对渐进比对进行改良。经过两次渐进比对，形成一个相对准确的多序列比对；第二部分是迭代比对：该过程类似于Prrp算法[9]，即通过不断的迭代，逐步优化最终比对结果。其主要特点包括：使用kmer counting进行快速的距离测量，使用一个新的图谱比对打分函数进行渐进比对，使用依赖于数的有限分隔进行细化。
渐进比对算法：该算法以Feng和Doolittle提出的最为经典[10]。渐进比对算法的基本思想是迭代地利用两序列动态规划比对算法,先由两个序列的比对开始，逐渐添加新序列，直到所有序列都加入为止。但是不同的添加顺序会产生不同的比对结果。确定合适的比对顺序是渐进比对算法的一个关键问题。通常，整个序列的比对应该从最相似的两个序列开始，由近至远逐步完成。作为全局多序列比对的渐进比对算法有个基本的前提假设:所有要比对的序列是同源的，即由共同的祖先序列经过一系列的突变积累，并经自然选择遗传下来的，分化越晚的序列之间相似程度就越高。因此，在渐进比对过程中，应该对近期的进化事件比远期的进化事件给予更大的关注。由于同源序列是进化相关的，因此可以按着序列的进化顺序，即沿着系统发育树(指导树)的分支，由近至远将序列或已比对序列按双序列比对算法逐步进行比对，重复这一过程直到所有序列都己添加到这个比对中为止[10]。其三个步骤为：（1）利用双序列比对方法对所有的序列进行两两比对，得到相似性分值；（2）利用相似性矩阵（或距离矩阵）产生辅助导向树；（3）根据导向树进行渐进比对。渐进比对算法是最常用、简单又有效的启发式多序列比对方法，它所需时间较短、所占内存较小，其算法很多，主要有CLUSTAL W, T-Coffee和DiAlign等，其中 CLUSTAL W应用最广泛。
应用：
类型+应用
双重序列对比：判断两个序列的同源性和一致性。（1）全局多序列比对可以鉴别或证明新序列与己有序列家族的同源性;帮助预测新蛋白质序列的二级和二级结构，是进行分子进化分析的重要前提。适合序列相似性较高，序列长度近似时的比对；（2）局部比对考虑序列部分区域的相似性。局部多序列比对可以用来刻画蛋白质家族和超家族。适合于未知两个序列相似程度的，可能存在一些片段极其相似而另一些片段相异的序列比对情况。
多重序列比对：多重比对经常用来研究序列间的进化关系，构建进化树；探究序列间的保守性。主要用于分子进化关系，预测蛋白质的二级结构和三级结构、估计蛋白质折叠类型的总数，基因组序列分析等。
基因组比对：通过对不同亲缘关系物种的基因组序列进行比较，能够鉴定出编码序列、非编码调控序列及给定物种独有的序列。而基因组范围之内的序列比对，可以了解不同物在核苷酸组成、同线性关系和基因顺序方面的异同，进而得到基因分析预测与定位、生物系统发生进化关系等方面的信息。
其中，BLAST作为最重要的比对工具，意义特殊，拿出来单独讨论。BLAST可以分成Basic BLAST和 Specialized BLAST, BLAST包括常规的nucleotide blast, Protein blast和Translating blast；Specialize blast可以对特殊生物或特殊研究领域的序列数据库进行检索。