生物序列比对算法综述作者：艾冬梅赵清玉张德坤来源：《中国科技纵横》2013年第18期【摘要】随着生物信息学的快速发展，序列比对算法成为研究的热点问题。
本文介绍序列比对算法的概念及研究，并针对几种常用的序列比对算法进行比较。
同时也简单说明序列比对算法的改进方向。
【关键词】生物信息学序列比对准确率时空效率随着生命科学研究的兴起和计算机技术的飞速发展，生物信息学已成为自然科学的核心领域之一[1]。
基因序列比对是生物信息处理的最基本方法，对发现基因功能、比较基因、探究生物进化等具有非常重要的作用。
1 序列比对算法概述所谓序列比对[2]，是指两个或多个序列按字母比较，尽可能确切地反映它们之间的相似和相异性，用于阐明序列之间的同源关系。
通过序列比对，找出序列之间的相似性，发现与结构相联系的保守序列片段，以及检测新测定序列与数据库中已知结构和功能的序列之间的相似性关系，从而以足够的可信度确定新序列的结构和功能信息。
目前已知的序列比对方法很多。
本文主要针对常用的算法，按照比对的序列数目进行相关介绍：1.1 双序列比对根据算法结构的不同，将双序列比对算法分为三类[3]：动态规划的优化方法，启发式算法和大型数据库搜索设计的概率方法。
1.1.1 动态规划的优化算法Needleman-Wunsch算法是最早的序列比对算法，属于全局序列比对，在生物信息处理中应用广泛。
Smith-Waterman算法是一种局部相似性的动态规划算法，在识别局部相似性时具有很高的灵敏度，是双序列比对算法中最基本的算法。
1.1.2 启发式算法1）FASTA算法FASTA是双序列比对启发式算法，采用了改进的wilbllr和Lipmall算法以集中反映具有显著意义的比对结果。
它的基本思想是：一个能揭示出真实序列关系的比对至少包含一个两条序列都拥有的片段，把查询序列中的所有片段编成Hash表，然后在数据库搜索时查询这个Hash表，以检索出可能的匹配，这样命中的片段就能很快地被鉴定出来。
序列比对的基本方法序列比对是生物信息学中重要的一项任务，它用于比较和分析不同生物序列之间的相似性和差异性。
序列比对方法既可以应用于DNA序列之间的比较，也可以用于蛋白质序列之间的比较。
本文将介绍序列比对的基本方法，包括全局比对、局部比对和多序列比对。
一、全局比对全局比对是将整个序列进行比对，得到两个序列之间的最佳匹配。
最常用的全局比对方法是Needleman-Wunsch算法，该算法用动态规划的方式计算两个序列之间的最佳匹配。
其基本思想是在两个序列中插入一个空位，并为每个空位赋予一定的惩罚分数，然后通过计算每种插入方式的得分来确定最佳插入位置，从而得到最佳匹配。
二、局部比对局部比对是在两个序列中寻找最佳匹配的子序列。
最常用的局部比对算法是Smith-Waterman算法，该算法也是基于动态规划的方法。
不同于全局比对，局部比对将得分为负值的子序列直接设为0，从而忽略掉匹配较差的部分。
该算法在序列比对中应用广泛，可以用于发现序列中的保守区域以及识别重复序列。
三、多序列比对多序列比对是指将多个序列进行比对，从而得到它们之间的相似性和差异性。
多序列比对方法有多种，包括ClustalW、MAFFT和Muscle等。
这些方法常用于计算进化关系，识别保守区域和功能位点等。
其中，ClustalW是最常用的多序列比对软件之一，它使用的是基于目标函数的方法，在多个序列中寻找最佳的全局匹配。
MAFFT和Muscle则分别使用多种算法来处理不同类型的序列，从而提高比对的准确性和效率。
四、快速比对算法传统的序列比对方法在处理大规模序列数据时效率较低。
为了提高比对速度，研究者提出了一系列快速比对算法，如BLAST、 FASTA和Smith-Waterman-Gotoh算法等。
这些算法常用于初步比对和预测，可以在较短的时间内找到相似序列，从而提高工作效率。
其中，BLAST是最常用的快速比对算法之一，其基本思想是将查询序列与参考数据库中的序列进行比对，并根据匹配得分对结果进行排序，从而找到相似序列。
生物信息学中的多序列比对方法生物信息学是一门研究生命科学数据的计算机科学学科，主要用于从大量基因组、蛋白质组、代谢组等生命组学数据中发现、分析和研究基因、蛋白质、代谢途径等生命过程的规律。
其中的多序列比对（Multiple Sequence Alignment，MSA）技术是一个比较重要的研究方法，其主要应用于多种生物信息学研究方向，如物种分类、基因结构和功能研究、蛋白质结构和功能研究等。
本文就生物信息学中的多序列比对方法进行简要介绍。
一、多序列比对的意义及难点多序列比对是将多条生物序列进行比对，在把它们对齐之后确定它们之间的共同位点及其差异位点的过程，从而分析出序列间的相似性和异质性等结构、功能上的关联。
这一过程主要分为四步：选择序列、生成比对矩阵、进行比对分析和生成比对结果。
通过多序列比对可以揭示序列进化、注释微小RNA、寻找共同结构域、定位功能残基等关键性生物学问题。
多序列比对的难点主要包括以下几个方面：（1）大数据量。
由于生物序列的数据量是非常庞大的，比如对于人和马之间的比对，需要对他们的约3000万个碱基进行比对，而且每个人的基因组或每个生物的蛋白质组都是高度复杂和大量重复的，因此进行多序列比对的计算复杂度非常大，需要使用高效的计算方法，充分利用计算资源。
（2）序列多样性。
生物序列相互之间具有高度的多样性，包括同一物种内的不同个体、不同物种之间的比对和不同基因家族的比对等，这些差异给多序列比对带来很大的挑战，需要使用不同的比对算法、策略和参数，才能得到最优的结果。
（3）精度和可信度。
生物序列不同的比对方法可能会得到不同的结果，因此必须对比和评估多种方法的参数和性能指标，同时要考虑到数据的来源、质量和格式等，以提高比对结果的精度和可信度。
（4）效率和实时性。
多序列比对通常是大数据、高计算量的任务，因此需要使用高性能计算环境或分布式计算架构，同时要考虑到任务的时间复杂度、并行度和负载均衡等问题，从而提高比对效率和实时性。
