生物序列比对算法综述

开篇：润墨网以专业的文秘视角，为您筛选了一篇生物序列比对算法综述范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

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

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

随着生命科学研究的兴起和计算机技术的飞速发展，生物信息学已成为自然科学的核心领域之一[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算法是一种基于后缀树数据结构的全基因组比对方法，利用后缀树的数据结构有效地将算法的时间和空间复杂度由（N 3）降到了（N）。与BLAST算法相比，其后缀树法在速度上快得多，且能处理大量的插入和删除片段，能识别重复片段和单核酸多态性等多种全基因组序列中的复杂片段。

1.2 多序列比对

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

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

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

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

2 序列比对算法比较

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

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

3 结语

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

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

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

参考文献：

[1]许忠能著.生物信息学[M].北京：清华大学出版社，2009.

[2]何万双.双序列比对算法研究[D].湖南：国防科技大学，2006.

[3]王非，杨欣.生物序列比对算法的实现与集成[J].计算机与应用化学，2004，21（4）：583-586.

[4]张涛涛，郭茂祖等.哈尔滨工业大学计算机科学与技术学院[J].生物信息学，2008，6（2）：65-84.