生物序列比对算法综述

【摘 要】随着生物信息学的快速发展,序列比对算法成为研究的热点问题.本文介绍序列比对算法的概念及研究,并针对几种常用的序列比对算法进行比较.同时也简单说明序列比对算法的改进方向.

【关 键 词】生物信息学序列比对准确率时空效率

随着生命科学研究的兴起和计算机技术的飞速发展,生物信息学已成为自然科学的核心领域之一[1].基因序列比对是生物信息处理的最基本方法,对发现基因功能、比较基因、探究生物进化等具有非常重要的作用.

1序列比对算法概述

所谓序列比对[2],是指两个或多个序列按字母比较,尽可能确切地反映它们之间的相似和相异性,用于阐明序列之间的同源关系.通过序列比对,找出序列之间的相似性,发现与结构相联系的保守序列片段,以及检测新测定序列与数据库中已知结构和功能的序列之间的相似性关系,从而以足够的可信度确定新序列的结构和功能信息.

目前已知的序列比对方法很多.本文主要针对常用的算法,按照比对的序列数目进行相关介绍：

1.1双序列比对

根据算法结构的不同,将双序列比对算法分为三类[3]：动态规划的优化方法,启发式算法和大型数据库搜索设计的概率方法.

1.1.1动态规划的优化算法

Needleman-Wunsch算法是最早的序列比对算法,属于全局序列比对,在生物信息处理中应用广泛.Smith-Waterman算法是一种局部相似性的动态规划算法,在识别局部相似性时具有很高的灵敏度,是双序列比对算法中最基本的算法.

1.1.2启发式算法

1）FASTA算法

FASTA是双序列比对启发式算法,采用了改进的wilbllr和Lipmall算法以集中反映具有显著意义的比对结果.

它的基本思想是：一个能揭示出真实序列关系的比对至少包含一个两条序列都拥有的片段,把查询序列中的所有片段编成Hash表,然后在数据库搜索时查询这个Hash表,以检索出可能的匹配,这样命中的片段就能很快地被鉴定出来.

2）BLAST算法

BLAST算法可以兼顾搜寻的速度以及搜寻结果的精确度,它比FASTA速度更快.它的基本思想是：产生比FASTA更少而更有意义的增强点,以提高整个算法的速度.BLAST算法在不失敏感性的前提下大大提高了算法的效率.

3）BLAT算法

Blat算法最初用于人类基因组拼接和注释过程中的大规模数据比对任务上.其速度快、共线性输出结果简单易读,存在的局限性是对于特殊的任务需要选择合适的软件,如：用于远亲缘物种间的核酸序列比对时,比对精度就不够高；在重复搜索短小匹配片段的同时,会产生过多的没有生物学意义的序列比对碎片.

1.1.3大型数据库搜索设计的概率方法为基础的算法

MUMmer算法是一种基于后缀树数据结构的全基因组比对方法,利用后缀树的数据结构有效地将算法的时间和空间复杂度由（N3）降到了（N）.与BLAST算法相比,其后缀树法在速度上快得多,且能处理大量的插入和删除片段,能识别重复片段和单核酸多态性等多种全基因组序列中的复杂片段.

1.2多序列比对

多序列比对的常用算法有累进算法、隐马尔科夫模型、迭代比对法等.

累进方法是最常用的启发式多序列比对算法.其中的CLUSTAL算法是由Feng和Doolittle提出的,基于相似序列通常具有进化相关性这一检测设的算法,它是多序列比对算法中使用最广泛的.

隐马尔科夫模型是目前较先进的多序列比对方法,跟常规的方法相比,它可以发现序列久远的同源性.

迭代方法也基于一个能产生比对的算法,并通过迭代方式精细多序列比对,直到比对结果不再改进为止.这类算法不能提供获得优化比对结果的保证,但却具有鲁棒性和对序列个数不敏感等特性.

2序列比对算法比较

通过上述介绍,本文对几种最常用的基因序列比对算法进行如下比较（如表1）：

在实际试验中处理生物信息数据时,考虑各种序列比对算法的速度和适用范围,启发式算法的应用最为广泛.进一步,虽然BLAT算法的适用范围较BLAST小,但两者原理相似,且BLAT速度更快,便于处理大量的基因数据,在进行简单的DNA基因序列比对任务时,研究者更青睐BLAT算法.

3结语

序列比对是生物信息学中最重要、最基本的方法,对于从大量生物数据中提取有价值的信息有重大的意义.

我国在序列比对方面研究较为落后,且目前提出的算法较少,大多数都是在几种基本序列比对算法的基础上进行的改进.如：张涛涛、郭茂祖等介绍了一种参数序列比对方法[4],该方法把最佳比对作为权值和罚分的函数,可以系统地得到参数的选择对最佳比对结果的影响.

准确率和运算速度是评价序列比对算法的重要依据,因此,获得比对准确率更高、时间空间效率更好的序列比对算法是生物信息学研究的一个重要课题.