第三章 序列比对.doc

第三章 序列比对
1 序列比对的概念
序列比对的定义是：根据特定的计分规则，两个或多个符号序列按位置比较后排列，尽可能反映序列间的相似性，这一过程称为序列比对。

2 序列比对的意义
生物信息学形成早期的主要研究内容就是序列比对，而当时序列比对研究的课题主要是生物大分子的进化。核酸序列与蛋白质序列的突变是经实验证明的生物学现象，而现代生物学认为正是这种生物大分子序列的不断变化形成了生物进化的分子基础。即在地质年代早期的地球生物中的核酸、蛋白质等序列经过几十亿年的演变后，成为了现今极其多样化的生物大分子序列。我们并不知道这些分子序列祖先演化的实际过程，但可以找到现存序列的相似性，根据相似性去推导演化的过程。正是通过序列比对找出序列之间的相似性。序列比对找到的是相似性，可用这相似性去进行同源性分析。后文所讲到的分子系统发育分析，就是通过序列比对，再进行聚类分析，然后依据所得结果确定被测分子序列的亲缘关系，构建进化树。
序列比对的一个用途就是用于搜索相似序列。当你获得一段DNA序列或氨基酸序列后，发现对它一无所知时，可以在核酸序列数据库中搜索关于这一序列的信息，一个有效的方法是采用比对算法在数据库中找到一系列与该序列有相似性的序列，并按相似程度由高到低排列。现在应用的多个序列搜索软件的本质差异基本上是比对算法的差异，随着数据库规模的扩大，对快速搜索的要求越来越高，而优化比对算法是解决问题的方案之一。
在基因组测序中，序列比对更是有重要作用。基因组测序一般要将若干个拷贝的长核酸序列打断成有重叠区域的许多小片断，测序仪对小片断进行测序，然后把已知碱基排列顺序的小片断用比对算法找到有重叠区的另外的片断，把它们边接起来还原成原来的长核酸序列，得到长核酸序列的碱基排列顺序。
序列比对还可以寻找序列中的特定位点。当一个基因的某一位点发生突变时，它与原基因进行比对时就能发现这个位点，这在寻找致病基因时尤为重要。同时，通过比对，可找出不同序列间一些保守性的区域，它们可能行使重要的功能。经常会用比对确认氨基酸序列的保守区以了解该区的特定结构与功能。
在进行蛋白质结构预测、基因预测时，比对也是一种基本的研究手段之一。蛋白质结构预测中，大部分的成果都是来自序列比对，研究的模式主要是有若干已知结构及氨基酸顺序的序列，把待测的序列与已知结构的序列进行比对，通过相似性去预测待测序列局部或全部的结构。而在蛋白质的分类中，有的方法就是利用比对获得氨基酸序列的相似性，以此相似性为基础进行分类。在基因预测中常要在待测序列中搜寻起始密码子、结束密码子、多聚A帽子序列等特自位点以增加预测的命中率。

3 全局比对与局部比对
根据对比对后要排列的片断范围可将比对分为全局比对与局部比对。
3.1 全局比对
全局比对是全部待研究的全部序列的全部符号参加比较，最后也是全部序列的全部符号进行排列与计分，比对的结果中各序列长度相同。例如，按特定的计分规则（字母相同+1分、字母不同-1分、一个空格“-”对一个字母-2分），以下序列1与序列2的全局比对是：

序列1 T A C A G T T G G A T C C G T
序列2 T T T G G A

序列1 T A C A G T T G G A T C C G T
序列2 T - - - - T T G G A - - - - -

比对的得分是1-2-2-2-2+1+1+1+1+1-2-2-2-2-2=-12，比对的结果中16个位置有6个位置字母相同，9个位置字母对空格。
3.2 局部比对
局部比对是全部序列的全部符号参加比较，最后只将各序列中得分高的片断中的符号进行排列与计分，即只排列局部的序列片断。上述的例子中将序列1与序列进行全部比对时得分较低，以下把它们进行局部比对，看看有怎样的变化：

序列1 T A C A G T T G G A T C C G T
序列2 T T T G G A

序列1 T T G G A
序列2 T T G G A

比对的得分是1+1+1+1+1=5，比对的结果中5个位置有的字母全部相同，分别是序列1的第6至10个字母与序列2的第2至6个字母相匹配。可见，用全局比对去寻找只有局部相似性的序列间的联系时很可能得不到有用的信息，而用局部比对则能把相似片断找出来。不同来源序列间在生物学上有意义的相似往往只出现在序列的局部区域，因此局部比对在实际中更常用。

4 计分方法
计分规则是比对的重要条件，计分方法的生物学意义常常就决定了比对所反映的生物学特征。在使用差异较大的不同计分方法时将会产生不同的比对结果。根据所代表的生物学意义可以粗略地将计分方法分为三类：匹配计分、结构与性质计分、可观察变换计分。
匹配计分的规则是字符进行比较时只有3至4个分值：两个字母相同一个分值、两个字母不同给一个分值、字母对空格给1至2个分值。例如常用的生物信息学软件BLAST中的核酸比对计分就是采用匹配计分。
由于这种方法简单，较容易用它说明比对的一般原理，所以本章的核酸序列比对都采用这种方法，其中当两字母相同时取+1分，两字母不同时取-1分，空格对字母时每个空格计-2分。
匹配计分的优点是简单易掌握，缺点是没有考虑不匹配时的相似性质。
5 比对的算法过程
有不少的序列比对算法已出现在文献及应用软件中，其中一些得到广泛的应用，如动态规划法、累进方法等。两序列比对与多序列比对的算法有差异，所以一般是分开介绍。两序列比对的经典方法是动态规划法，点阵法也用得较多，我国学者沈世镒等创造了统计判决算法。多序列比对的常用方法是累进方法、隐马尔可夫模型、动态规划法等，也有些算法相对简单，如星比对方法。
5.1 两个序列比对
全局比对动态规划法是Needle与Wunsch在1970年提出，一直沿用至今，这个算法是生物信息学的基础算法之一。动态规划算法是把一个大问题分成多级的小问题，逐级求每个小问题的最优答案，各级问题的最优答案加起来就是这个大问题的最优答案。
如果不加限制空格的加入，任两个序列的比对结果都会有无限多个，因为只要加入不同的空格数目就行了。因此首先规定空格对空格无效。
动态规划算法将比对全过程分为若干步，每一步增加一个位置。因为空格对空格无效，所以增加一个位置时有三种情况：第一个序列增加一个字母而第二个序列增加一个空格；第一个序列增加一个空格而第二个序列增加一个字母；两个序列都增加一个字母。这样要进行n步的话就可能有3n种可能。动态规划算法的巧妙之处是把第一序列已比对字母且第二序列已比对字母都相同的各种比对结果放在一起进行判断，只留最优结果。例如对序列gc与at进行比对，其中中间过程中的三个结果（都是第一序列的g已比对且第二序列的a已比对）：
g– -g g
-a a- a
是放在一起的，并且被判断，只留出最优结果（即舍去了第1与第2个比对结果）。用这种筛选方面一直进行下去，直到所有的字母都进行过比对为止。最后所得的最优解就是动态规划算法的最后结果。因此，用动态规划算法进行两序列比对的过程可用矩阵显示，矩阵中的每一元素可表示第一序列已比对字母且第二序列已比对字母相同的各种比对结果的最优者，最后的一格（即右下格）的最优结果就是整个比对的最优结果。在具体算的过程中，每一格只用最优比对的得分来表示。
矩阵的计算过程可表示如下：对于序列I，序列J，如果采用特定的计分规则（字母相同+1分；字母不同-1分；字母对空格-2分），除左上第一格外，每一格均有：
Mi-1,j-2 （表示纵向增加一个位置是字母对空格，因此减2分）
Mij=max Mi-1,j-1+S(i,j) （表示斜向增加一个位置是字母对字母）
Mi,j-1-2 （表示横向增加一个位置是空格对字母，因此减2分）
其中Mij指在i列、j行的元素所在的计分；
Max指要三种可能得分中的最高分的那种；
Mi-1,j指第i-1列、第j行的元素（即Mij的水平左方的那个元素）的计分；
Mi-1,j-1指第i-1列、第j-1行的元素（即Mij的水平左斜上方那个元素）的计分；
Mi,j-1指第i列、第j-1行的元素（即Mij的垂直上方那个元素）的计分；
S(i,j)指第i列字母i与第j行字母j的比较，相同为+1，不同为-1。
以下用2个例子说明动态规划算法。
例1：用动态规划法对以下序列进行比对：① ac；② at
解：先画出矩阵Mij（其中i表示列，j表示行），将序列①写在矩阵的最上面的横行上，将序列②写在矩阵的最左面的纵行上。分别根据最优化原理在每个矩阵的元素上填入最优比对或最高分数。
图1表示中间过程的最优比对。

0

a

c
0
-
-
←
- a
- -
←
- a c
- - -

↑
↖

a
- -
- a

- a
- a
←
- a c
- a -

↑

↑
↖

t
- - -
- a t

- a -
- a t

- a c
- a t

图1 例1中间过程的最优比对

M11是个初始化元素，只列出空格对应空格。假如没有最优化过程，则M21填入1个比对（如上所示）；M31也是填入1个比对（如上所示）；M12也是填入1个比对（如上所示）；M22则可填入3个比对（分别来自1个由M12的比对中序列①增加a与序列②增加空格、1个由M11的比对中序列①增加a与序列②增加a、1个由M21的比对中序列①增加空格与序列②增加a）；M32则可填入5个比对（分别来自3个由M22的比对中序列①增加c与序列②增加空格、1个由M21的比对中序列①增加c与序列②增加a、1个由M31的比对中序列①增加空格与序列②增加a）；M13也是填入1个比对（如上所示）；M23则可填入5个比对（分别来自1个由M13的比对中序列①增加a与序列②增加空格、1个由M12的比对中序列①增加a与序列②增加t、3个由M22的比对中序列①增加空格而序列②增加t）；M33则可填入13个比对（分别来自5个由M23的比对中序列①增加c与序列②增加空格、3个由M22的比对中序列①增加c与序列②增加t、5个由M32的比对中序列①增加空格与序列②增加t）。
由于每个矩阵元素都求最优解，所以M22的三个比对中
- - a - a - a -
- a - - a - - a
取中间的比对，其余两个舍去，用箭头表示这个比对来自M11。M32中只有三种比对结果

- a c - a c - a c -
- a - - - a - - - a

取左边的比对，其余两个舍去，用箭头表示这个比对来自M22。M23中只有三种比对结果

- - - a - - a - a -
- a t - - a t - a t

取右边的比对，其余两个舍去，用箭头表示这个比对来自M22。M33中只有三种比对结果

- a - c - a a - a c -
- a t - - a t - a - t

取中间的比对，其余两个舍去，用箭头表示这个比对来自M22。M33的结果也是整个比对最后的结果。
图2 表示中间过程的最优比对的分值。

0

a

c
0
0
←
-2
←
-4

↑
↖

a
-2

1
←
-1

↑

↑
↖

t
-4

-1

0

图2 中间过程的打分

图2每一格的分值与图1每一格的比对是一一对应的。
图2中的第一行中的每一格（除第一格外）中的分值都是由左边的格中的分值算出，每移动一格就相当于横向的序列多了一个字母而纵向的序列多了一个空格，因此向右移动一格就要减2分，如M31的-4是由M21中的-2减2分而得到的并且把箭头M31指向M21。
第一列中的每一格（除第一格外）中的分值都是由上边的格中的分值算出，每移动一格就相当于纵向的序列多了一个字母而横向的序列多了一个空格，因此向下移动一格就要减2分，如M13的-4是由M12中的-2减2分而得到的。
除第一行与第一列以外的每一格中的分值都是由上边、左上角、左边的格中的分值分别算出3个分值，再取最大者。上边的格中的分值减2分算出一个值，左边的格中的分值减2分算出第二个值，原理与上述的一样。当一个格向右下角每移动一格就相当于纵向的序列多了一个字母而横向的序列也多了一个字母，如果这两个字母相同则加1分，如果字母不同则减1分。如M22可由三个方向推出3个分值：左边的M12（-2分）减2分得-4；上边的M21（-2）减2分得-4；左上角的M11（0分）加1分得1分。如M33可由三个方向推出3个分值：左边的M23（-1分）减2分得-3；上边的M32（-1）减2分得-3；左上角的M22（1分）减1分得0分。
例2：用动态规划法对以下序列进行全局比对：1）acgt；2)atcgt
解：画出矩阵Mij（其中i表示列，j表示行），每格算出最高分数，如图3所示。

0

a

c

g

t
0
0
←
-2
←
-4
←
-6
←
-8

↑
↖

a
-2

1
←
-1
←
-3
←
-5

↑

↑
↖

↖

↖

t
-4

-1

0
←
-2
←
-4

↑

↑
↖

↖

↖

c
-6

-3

0

-1
←
-3

↑

↑

↑
↖

g
-8

-5

-2

1
←
-1

↑

↑

↑

↑
↖

t
-10

-7

-4

-1

2

图3 例2中间过程的打分
每一格的评分都是由三种可能的评分方案中寻找最高分，其余方案不再继续。三种可能的方案分别来自左、左上、上三个方向，用反向箭头表示，一直从左上端进行到右下端，根据箭头方向往回找。
回溯确定每一个位置的两个字符，即每一个位置向左对应的字符与向上对应的字符。
比对结果是
a - c g t
| | | |
a t c g t
1 -2 1 1 1
得分是1-2+1+1+1=2。
5.1.3 点阵法
点阵法用于比较两段具有连续相似区域的序列。两个序列的一条横写，另一条纵写。在字母相同的位置画圆点（或其他标记），然后用-45º线段连结对角相连的圆点。图4是表示两个序列（actgtagcct和accgagcct）的点阵图，从中可找到4个连续匹配的局部比对。

a
c
t
g
t
a
g
c
c
t
a

c

c

g

a

g

c

c

t

图4 两个序列的点阵图

7