序列比对研究现状与展望

—掌握序列比对，华夏儿女将不仅仅是1%！

­

黄洁琳 

（班级：08级生物科学二班  学号：20082501032）

 

摘要： 序列比对是生物信息学研究的一个基本方法,寻求更快更灵敏的序列比对算法一直是生物信息学研究的热点.本文给出了生物序列比对问题的定义,综述了目前常用的各类比对算法,并对每一类算法的优缺点以及应用范围进行了分析,最后指出序列比对算法目前存在的问题以及未来的发展方向.

关键字：生物信息学；序列比对；方法比较；现状；展望

 

Current and prospect of bio-sequence alignment

                -To know the sequence, Chinese will more than 1%!

HUANG Jielin 

(Class：08Class Two of Biological Science   StuNo：20082501032)

Abstract： Sequence alignment is a basic and important tool in bioinformatics6 The research of fast and sensitive biology sequence alignment algorithm is acurrent hot topicof bioinformatics6 This paper introduces a definition of sequence align ment;as well as the research advance of alignment algorithms at present, and describes the advantage and limit of the algorithms and applicablefields. Lastly,the problems and development directions are pointed out6

Key words: Bioinformatics； Sequence Alignment； Methods Compared； The Status； Looking

 

0         前言

随着被号称为“生命阿波罗计划”的人类基因组计划的实施完成和蛋白质序列数据库规模的指数级增长，越来越多的生物体序列数据被人们所检测而出，通过这些序列数据的比对分析，人们有望能从中发掘出不同生物的蛋白质表达以及基因表达。但与序列测定的快速发展相比，人们探测分析这些序列的方法的进步却显得过于缓慢，单纯依靠实验手段研究、理解这些生物大分子的生物意义已经远远不能满足目前生物信息学的发展要求。我们迫切期望能拥有一种快速且准确的序列分析方法！

生物序列分析问题涉及的内容很多，其核心问题是比较各种不同类型的生物体序列的相互关系。序列比对通过比较生物分子序列，发现它们的相似性，找出序列之间的共同区域。同时辨别序列之间的差异，从而揭示生物序列的功能，结构和进化信息。这无疑是生物信息学在近代生命科学研究当中的基本而且关键的一环。

本文给出了生物序列比对问题的定义，综述了目前常用的各类比对算法，分析了每一类算法的应用范围，最后指出了序列比对目前存在的问题以及未来发展方向。

1  序列比对问题的定义

组成生物DNA序列的是由腺嘧呤、鸟嘧呤、胞嘧啶和胸腺嘧啶四种核苷酸组成，分别记为A、G、C和T。生物的蛋白质是由20种氨基酸构成的多肽链，记为A、R、N、D、C、Q、E、G、H、I、L、K、M、F、P、S、T、W、Y、V。在弄清DNA和蛋白质的化学性质之后不久，人们发现用单个字母来代表链的结构是很方便的，这种方式不仅可以节约存储空间，而且提供了共享信息序列信息较为方便的形式。它代表了分子独特的和准确的性质，并且忽略了在实验时无法访问的细节（比如DNA和许多蛋白质的原子结构）。序列比对问题正是在这种基础上建立连起来的。

1.1 序列比对的定义

序列比对就是运用某种特定的数学模型或算法，找出两个或多个序列之间的最大匹配碱基或残基数，比对的结果反映了算法在多大程度上反映了序列之间的相似性关系以及它们的生物学特征^[4]。根据文献^[5]，有如下的数学定义：

定义：序列比对问题可以表示为一个五元组MSA = (Σ’, S , A , F) ，其中：

(1) Σ’= Σ∪{ - } 为序列比对的符号集，“- ”表示空位( gap)， Σ表示基本字符集，对于DNA 序列, Σ= { a , c , g , t} 代表4个碱基；对于蛋白质序列, Σ由20个字符组成，每个字符代表一种氨基酸残基；

(2) 为序列集，其中 ， c_ij ∈ Σ， L_i 为第i个序列的长度；

(3) 矩阵 ， ( M ≥ max{ L₁ ， L₂ ， ⋯， L_N} ， a_ij ∈ Σ′是序列集S 的一个比对结果，

其中：矩阵的第i行是参与比对的第i个序列的扩张序列(即插入空位的序列，如果移去所有的“- ”将得到原来的序列) ；矩阵中的每一列不允许同时为“- ”；

(4) F 是比对A 的相似性度量函数，用来表示比对A 中各扩张序列的相似度；

(5) 序列比对问题MSA 就是通过适当的空位插入，构建一个使得相似性度量函数F( A) 达到最大的比对A。

由上述定义可知：序列比对问题就是通过适当的空位插入来模拟生物分子进化过程中的突变现象，以反映它们间的进化关系。下图是一个比对的结果

1.2  序列比对结果的评价标准

对于序列比对的结果，通常用计分矩阵来计算其分值，以得到一个评价优劣的标准。其中基于进化距离的计分矩阵是由Dayhoff等人在20世纪70年代后期提出的^[6]，他们对进化过程中氨基酸彼此间的替换作了详细的频率研究，这导致产生了在一个短的进化过程中氨基酸彼此间替换的相对频率表，称为单点可接受突变（PAM）计分矩阵，常用的PAM250计分矩阵是由PAM矩阵自乘250次后得到的，表示进化距离较远^[7]。另外一种常用的计分矩阵BLOSUM^[8]是根据Blocks数据库中蛋白质序列高度保守部分的比对结果自动产生的，带有编号的矩阵表示的是此序列有此百分比或以上相同的残基。

序列比对的理论基础是进化学说，如果两个序列之间相似性较高，就可以推测出二者在进化上可能有共同的祖先。经序列内残基的替换、残基或序列片段的缺失，以及序列中某些氨基酸残基比其他位置上的残基更保守，这些信息揭示了这些保守位点上的残基对蛋白质的结构和功能是至关重要的。但并不是所有保守的残基都一定是结构功能重要的，可能它们只是由于历史的原因而被保留了下来，而不是由于进化压力而保留下来的。而序列比对可以发现隐含在生物序列中的功能、结构及进化的信息。序列的最优比对对于这些信息的发现时十分重要的。

 

2   序列比对分类

序列比对类型可以从两个不同角度来划分：一是从序列个数，序列比对可分为两序列比对和多序列比对；另一个是从比对范围，可分为从头到尾全程比较的全局比对和只考虑部分区域相似性的局域比对。下面，就介绍当今使用最为广泛的几种序列比对，并对其优劣以及适用范围进行说明。

2.1  两序列对比算法

    到目前为止，两序列比对问题已基本解决，标准方法是采用可以保证得到一个数学优化的比对结果的动态规划比对算法^[1]。两序列的动态规划比对算法是多序列比对的重要理论基础。

2.1.1 点阵分析法

2.1.1.1 简介

    进行点阵分析时，首先要建立一个矩阵，两条序列的长度分别是矩阵的行数和列数。一条序列（A）置于矩阵顶部，而另一条序列（B）则列在矩阵的左侧。从B的第一个字符开始，然后沿着该矩阵的第一行移动，在A中具有同样字符用的单元用点标志。然后将B中的第二个字符与整个A序列比较，在匹配的位置以点标志。重复该过程，直到整个矩阵填充完毕。知识按行填充的模式。按列填充模式也是同样的道理。矩阵中的点表示了所有可能的匹配。所有的相似区域表现在图上都是斜对角线方向的一连串点。对角线以外的孤立点表示随机匹配，没有任何生物学意义。

2.1.1.2 优劣分析

点阵法的主要优点在于能将所有可能的比对结果用该矩阵的对角线表现出来，点阵法还能显示插入/缺失及序列内部正向和反向重复的存在，这是其他对比方法所很难做到的。而其局限性在于大部分的点阵分析软件无法给出一个真正的比对结果。

2.1.2  动态规划算法

2.1.2.1 简介

    动态规划算法是一种能高效给出最优比对的算法。其基本思想是将待求解问题分解成若干个小的子问题，先求解子问题，并储存子问题的解而避免重复计算，然后从这些子问题的解中得到原问题的解。

动态规划比对算法的具体操作如下：对于长度分别为n,m的序列A（a₁,a₂,a₃,…,a_n）和B（b₁,b₂,b₃,…,b_m）,其比对过程可用一个一序列A为列，B为行的（n+1）*(m+1)二维矩阵来表示（如下图），每个单元的评价值可由（1）式递归计算，其中g(k)=u+kv是连续k个gap的空位罚分，s(a_i,b_j)是两个残基的相似度。

 

 

从右下单元到左上单元回溯最佳路径（由箭头表示），路径中每个单元的评价值是根据前面各单元的评价值决定的。最后，根据最佳路径从左上到右下给出两序列的比对结果。若箭头为对角线，则在比对后的序列中，两个残基相对应。若箭头为水平方向，则在A序列的相应位置插入一个“_”。若箭头为垂直方向，则在B序列的相应位置插入一个“_”，比对结果可能不唯一。序列A，B有三个最优比对结果，每个比对结果有三个保守残基被对齐（大写字符）

2.1.2.2 优劣分析

动态规划算法与其他比对算法相比，其优势在于能保证可以给出最优比对结果，但其缺陷也是明显的，动态规划算法对计算步骤和计算机内存的要求会成平方或立方增长，当序列较长时，这种方法的效率会变得很低。

2.1.3  词或K串法

2.1.3.1 简介

词或K串法同常在FASTA和BLAST中使用，这个方法通过搜索序列间完全相同的一短串字符串（即词或K串0，然后通过动态规划方法吧这些词语连接成比对结果。

2.1.3.2 优劣分析

词或K串法的优点在于其速度很快，使用与搜索整个数据库，寻找与待查询序列比对结果最好的序列，得到的比对结果在统计上是完全可靠的。

2.2  多条序列对比算法

从理论上来说，两序列的动态规划比对算法可以推广到多序列比对中去，但现已证明：基于SP度量的多序列比对是一个NP问题^[2]。实际上，除了个数较少，序列较短的比对问题外，多序列比对基本上都是采用启发式算法。本文重点介绍目前国际上最具代表性的两类算法：迭代比对算法和渐进比对算法。

2.2.1  迭代比对算法

2.2.1.1 简介

迭代比对算法是另一类有效的多序列比对算法，它基于一个能产生比对的算法，并通过迭代方式精细多序列比对，直到比对结果不再改进为止。基于遗传算法的多序列比对SAGA 算法是一种实用的迭代算法。该算法的思想是将序列集中不等长的序列以两端加空位方式补齐，构造初始群体中的个体，将初始群体中的个体按一定的概率进行遗传操作(复制、联锁互换、突变)产生新的个体构成新种群，对新种群的个体重复上述的遗传操作，直到满足终止条件。个体适应度函数用WSP度量。

2.2.1.2 优劣分析

该算法的优点在于可以对任意多个序列同时比对，而不会受到限制。主要缺点是速度慢，易于陷入局域优化解。这类算法不能提供获得优化比对结果的保证，但却具有鲁棒性和对比对序列个数不敏感等特性。

2.2.2  渐进比对算法

2.2.2.1 简介

渐进比对算法是最常用的启发式多序列比对算法。算法的基本假设是要比对的序列是同源的。算法的基本思想是由近至远将序列或子比对结果按双重比对算法逐步进行比对，重复这一过程直到所有序列都加入为止。CLU STALW是一个使用最广的渐进比对程序，该算法主要由三个步骤组成：计算距离矩阵、构建指导树、依据指导树进行渐进比对。CLU STALW对于亲缘关系较近的序列比对效果较好，但是对于分歧较大的序列, 比对的准确率明显降低。

2.2.2.2 优劣分析

这类算法的主要优点在于简单、快速，所占内存较少。而其缺点也是很明显的，在比对初期引进的空位插入错误无法在比对后期因加入其它序列而改正，易陷入局部最优解。

 

3  序列比对算法现存问题及未来展望

3.1 现存问题

在人类基因组计划中，中国承担着其中1%的任务。随着人类基因组计划的实施，通过基因组测序、蛋白质序列测定和结构解析等试验，分子生物学家得到了大量的有关生物分子的原始数据。然而，面对如此丰富的数据，我们掌握的信息却很匮乏，产生分子遗传学数据的能力大大超出了我们分析这些数据的能力。生物信息学而临的情况是拥有了大量的数据，却不能有效地分析利用这些数据。

序列比对是生物信息学研究的强有力工具，但也是一大难题，随着生物学信息的大量积累，对序列比对算法的敏感性和运算速度也有很大的要求，而当今序列比对的软件都具有或这或那的局限性，分析结果始终未能尽如人意。如何寻找出一种能兼顾各方面序列，可以体现出其速度或准确性优势的序列比对方法，并将其设计成软件，大规模使用，是当前人们所急需解决的问题，也是未来几年里生物信息学所要解决的难题。

3.2  未来展望

     专家认为，1％测序任务的完成，必将大大促进中国生物信息学、生物功能基因组和蛋白质等生命科学前沿领域的发展，也将为中国基因资源开发利用，医药卫生、农业等生物高技术产业的发展开辟更加广阔的前景。

现已有较多的智能算法应用到了序列比对中，但是应看到还有许多方法效果还不好，并且计算智能中的其他一些方法并没有应用进来，这除了有这些算法的适应范围的因素外，还有一个重要的问题就是数学建模的问题。如果建模得当，那么新的算法应用进来，也是大有前景的。

在人类基因组计划——“生命阿波罗计划”的实施当中，“黄种人的基因，中国人来测，履行大国责任”这是我们当时提出的口号，而在当今这日新月异的信息爆炸社会，我们也更应掌握更多更优秀更有效的序列比对方法，分析相关的基因序列，将“黄种人的序列，中国人来测，再次履行大国责任”的口号再次向世界喊出！同时向世人证明：只要目标集中，措施有力，中国科学家也有能力参与国际重大科技合作研究，跻身于国际生命科学前沿，并作出重要贡献。华夏儿女将不仅仅是1%！

参考文献

[1]  黄宛.临床心电图学.第5版[M].北京：人民卫生出版社,1998;551-555

[2]  藏益民，朱妙章，牛国保，等.临床心血管生理学及其进展[M].北京：世界图书出版公司，1993;281-285.

[3]  陶士珩.生物信息学[M].科学出版社，2007-08.

[4]T K Attwood, D J Parry-Smith 著. 罗静初等译. 生物信息学概论[M].北京:北京大学出版社,2001:141-145.

[5]张敏.生物序列比对算法研究现状与展望[J].大连大学学报,2004,25(4):75-78

[6] Dayhoff,M.O.,et al.1978.A model of evolutionary change in proteins.In Atlas of Protein Sequence and Structure (ed.Dayhoff,M.O.), Vol.5,pp.345-352. Natl.Biomed.Res.Found., Washington DC,USA.

[7]王翼飞,史定华.生物信息学-智能化算法及其应用[M].北京：化学工业出版社,2006:72-75.

[8]  周康.关于DNA序列比对算法的简述[J].武汉工业学院学报，2005-06,24（2）：17-21.

[9]  杨凡，唐东明，白勇，赵明渊.多重序列比对研究进展[J].生物医学工程学杂志，2010-08，27(4).

[10]  李成渊，龙海侠，孙俊，须文泼.基于剖面隐马氏模型的多序列比对[J].食品与生物技术学报，2010-07，29（4）.