双序列比对算法综述
摘 要：在生物信息学中，基因序列比对是最基本、最重要的操作。本文首先介绍了序列比对的划分方式，提出了双序列比对算法的研究意义；接着对典型的双序列比对算法的研究现状进行了较为详细的阐述，包括算法的原理、对比等；然后通过收集双序列比对算法的优化方案，总结出当前算法的发展趋势，得出结论。
关键词：生物信息，序列比对，双序列比对，动态规划，点阵图
1 引言
序列比对问题是指将基因序列进行比对，将其中相似性的部分标示出来，通过标示出的序列相似度来确定序列间的同源性关系。在生物信息学中，基因序列的比对是最基本、最重要的操作，是进行基因识别、信息分析、结构预测等问题的前提。本文将介绍一种最基础的比对方式——双序列比对。
2 背景与意义
序列比对有多种划分方式。根据比对数量的不同，可分为双序列比对和多序列比对。双序列比对即通过两个基因序列的比对，找到相似的基因片段，从而推测目标基因可能具有的功能以及可能的分子进化关系。而多序列比对通过多个基因序列的比对，寻找到它们相同的位点、区域，推测具有共同功能的序列模式。
就序列本身而言，对序列进行整体比对的方式称为全局比对，对序列进行部分比对的方式称为局部比对。全局比对适用于总体相似度高的同源序列；局部比对适用于长度差别大、亲缘关系远的序列，可找出两条序列中相似度最高的片段。
由于双序列比对是基因序列比对最早采取的方式，也是生物信息学最基本的研究方法，所以我决定先从这种最基本的方式入手，了解双序列比对算法的研究现状及发展趋势，为进一步的学习做好铺垫。
3 双序列比对算法研究现状
3.1 典型双序列比对算法介绍
3.1.1 基于动态规划的双序列比对算法
Needleman-Wunsch算法
1970年，Needleman和Wunsch最早提出了一种基于动态规划思想的序列全局比对算法：使用迭代的方式求出两个基因序列之间的对比得分，并把结果存放在二维得分矩阵里面，然后运用动态规划方法在二维得分矩阵中进行回溯从而找到序列最佳比对路径，即序列比对的最优结果。
Hirschberg算法
1975年，Hirschberg提出了一种基于动态规划的全局比对算法，采用了分而治之的思想。该算法最大的优点是能减少序列联配问题的空间需求，其空间复杂度为O（m+n），但Hirschberg算法的时间需求却是N.W的两倍。
Smith-Waterman算法
1981年，Smith和Waterman 提出了一种基于N.W算法的确定局部相似性的动态规划算法，寻找两条基因序列之间局部范围内的相似性，忽略了匹配区域之前或之后的错配。后续对局部序列比对的研究与改进都是基于本算法进行的。
3.1.2 基于启发式的双序列比对算法
（1）FASTA算法
1985年，Pearson和Lipman共同研究提出了FASTA算法，它是一种 S.W算法的快速近似算法，速度和敏感度介于S.W算法和Blast之间，亦可进行全局比对。
1988年，他們对其进行了改良：序列比对时至少要有一个或一段它们共同拥有的字或片段，将要处理的序列中的所有字编写成Hash表，以便于数据库的查询，检索出有一定关系的匹配，从而有效地降低查询命中字的时间。
（2）BLAST算法
1990年，Altschul等人提出了BLAST算法，该算法采用一种短片段匹配算法和一种有效的统计模型来找出目的序列和数据库之间的最佳局部比对效果。这种双序列局部比对算法被广泛使用在蛋白质DNA序列分析和其他序列相似性比对的问题中。
3.1.3 基于点阵图的双序列比对算法
点阵法最早由 Gibb 提出。该算法是在一个坐标中的相应位置处进行描点，坐标中两条序列的连续相同区域会形成一条直线。用点阵图来表示双序列比对较为直观。
3.2 典型双序列比对算法比较
在上述算法中，用于双序列全局比对的有N.W算法、Hirschberg算法和FASTA算法。其中最早的算法是Needleman-Wunsch算法，它也是最经典的双序列全局比对算法。
而针对局部比对问题，可用的算法有S.W算法、FASTA算法、BLAST算法等。其中最具代表性的双序列局部比对算法是Smith-Waterman算法，其灵敏度非常高。
如果已知待比较的序列非常相似，一般采用点阵法来比较。因为这种方法可以通过观察矩阵的对角线，迅速发现可能的序列比对，并且可以很容易地发现插入、删除序列和重复序列。
但由于绝大多数点阵计算机程序不能显示出精确的序列，所以其他两种算法的使用更为普遍。当序列条数不太多、序列长度不太长时，建议选择动态规划算法；当需要进行大规模序列比对时，启发式算法则可得到更优的结果。
4 双序列比对算法的优化
根据观察上述算法，我们不难发现：双序列比对算法在得到最优结果的同时，普遍存在着增加时间、空间复杂度的问题，较高的复杂度是该算法研究的一个难题。为此，在上述典型算法的基础上，人们陆续提出了许多改进方法，如：
（1）基于遗传算法的双序列比对
由于序列比对问题可以看成是一个组合优化问题，而遗传算法是一种求解大规模问题的全局性优化算法，因此可以用来解决序列比对问题。
在遗传算法中，存在着几个关键的设计：个体编码方法的设计，初始种群的设计，适应度函数的设计，选择算子的设计，遗传算子的设计，算法停止准则的设计。
（2）基于蚁群算法的双序列比对
蚁群算法是一种现代智能仿生算法，它通过模拟蚁群在觅食过程中寻找最短路径的方法来求解最优化问题。在利用蚁群算法求解 TSP 问题的基础上，将其算法思想用于求解序列比对问题上。双序列比对问题可以归结于：在分值矩阵中，求解出一条分值最大且路径最短的问题。
（3）对Needleman-Wunsch算法的分布式并行优化
针对高性能计算设备昂贵、资源有限、N.W算法中比对数据存在依赖性的特点，可在MPI编程技术巧异构机群上将算法进行分布式并行化。
该算法将比对得分矩阵进行划分，通过确定最优迭代次数与子节点获得的子序列长度来充分利用各个节点计算资源，使得计算任务连续执行。回溯中采用LIFO通信策略，有效降低算法整体的时间及空间复杂度。
综上，双序列比对主要可通过引入遗传算法、蚁群算法以及并行分布式的方式对算法进行提速优化，目前已有较多研究成果。
5 结论
本文从双序列比对入手，首先介绍了序列比对的两种划分方式；接着对基于动态规划、基于启发式和基于点阵图的双序列比对算法的研究现状进行了较为详细的阐述；最后，介绍了基于遗传算法、蚁群算法等优化方法，用于解决双序列比对算法普遍存在的时间、空间复杂度较大的问题。
另外，在完成论文的过程中，笔者发现很多优化算法都是在已有算法的基础上，结合另一种新思想发展而来。在这个信息技术高速发展的时代，利用好身边的工具，跳出固有思维，不囿于传统，也许就能有新的收获。
参考文献
[1] 汪浩.基因序列比对算法的优化研究[D].中国农业科学院.2015.
[2] 李丹.双序列比对算法的研究与改进.电子技术与软件工程[J]，2017：148.
[3] 范慧.基于遗传算法的序列比对方法的研究[D].湖南大学，2012.
[4] 李川.双序列比对算法研究与并行优化[D].西安电子科技大学，2011.
[5] 冯百龙.双序列比对Needleman-Wunsch算法的分布式并行优化研究[D].内蒙古农业大学，2015.