第2章配对序列比对2bak.doc

第四节 全局序列比对(Global Sequence Alignment) 在介绍全局比对之前，我们得首先说明的是对任何比对方法（包括全局比对，局部比对）主要包括两部分： 第一部分就是计算最大相似得分数，也就是这两个序列比对的最优化计算过程。 第二部分是在根据这个最大相似得分数，通过“回溯”方式确定两个序列的比对结果即第一个序列中的各字符（在DNA中为对应的碱基，在蛋白质中为对应的氨基酸残基）与第二个序列中哪个字符相匹配。通过这个结果可以确定相应保守区，可变区，这样据此可推断这两个序列是否有同源关系以及其同源性程度。这部分工作在比对中一般称为“回溯”（traceback）。 我们首先考虑两个序列 和 ，现在要求解的问题是如何通过计算求出这两个序列的比对结果，以确定其相似程度。 为使读者对比较容易理解全局比对的算法，我们这里通过一个具体例子的计算来说明。由于蛋白质有20个氨基酸残基，相应的得分表比较复杂，为此我们这里的例子采用一小段DNA序列来说明其具本计算过程。 实例，两个序列S=ACCTGA 和T=CATGTAT，对应的得分矩阵假设为： 表2-3 四个碱基的得分矩阵 A T C G * A 2 -1 -1 -1 -1 T -1 2 -1 -1 -1 C -1 -1 2 -1 -1 G -1 -1 -1 2 -1 * -1 -1 -1 -1 2 为此我们首先假设代表序列S中第a个字符即与序列T中第b个字符之间的相似分数，比如当a=3时，; b=4时，，根据得分矩阵，;同样的。这样我们可得到与序列S和T对应的表格σ即图2-7： i j 0 1 2 3 4 5 C A T G T 0 0 -1 -1 -1 -1 -1 1 A -1 -1 2 -1 -1 -1 2 C -1 2 -1 -1 -1 -1 3 G -1 -1 -1 -1 2 -1 4 C -1 2 -1 -1 -1 -1 5 T -1 -1 -1 2 -1 2 6 G -1 -1 -1 -1 2 -1 图2-20 序列S=ACCTGA 和T=CATGTAT之间的各碱基之间对应得分即σ 得到对应的σ矩阵。然后我们根据比对的两大组成，首先就可在此基础上应用动态规划法计算各子序列之间最优的比对得分即相应的最佳相似性分数即比对的第一部分。然后应用回溯法给出比对结果。 第一步，计算两个序列的最优（大）相似性分数。 1，我们假设是序列和 (0 ≤ i ≤ n, 0 ≤ j ≤ m)。m,和n分别为这两个序列的长度，在本例子中n=5;m=6。 2，初始条件： 3，迭代，相应的迭代公式：对1 ≤ i ≤ n, 1 ≤ j ≤ m ，有 这里的迭代公式对生物学工作者而言，可能比较复杂，为此，我们将它表示成相应的图： 图2-21 迭代过程示意图 这样整个比对过程就可如下图所示： （0，0） （m,n） 图2-22 整个动态规划计算示意图 4，寻找第m列（即最后一列）中所有元素的最大值: 5，寻找第n行（即最后一行）中所有元素的最大值： 6，寻找最优比对值，即 现在我们以图2-20为例为说明上面公式的应用。 根据初始条件，图2-20变为图2-23 i j 0 1 2 3 4 5 C A T G T 0 0 -1 -2 -3 -4 -5 1 A -1 -1 2 -1 -1 -1 2 C -2 2 -1 -1 -1 -1 3 G -3 -1 -1 -1 2 -1 4 C -4 2 -1 -1 -1 -1 5 T -5 -1 -1 2 -1 2 6 G -6 -1 -1 -1 2 -1 图2-23 序列S=ACCTGA 和T=CATGTAT比对初始值设置 图2-23中红色部分即是根据初条件计算得到（其它单元格中没有变） 在迭代过程中，根据迭代公式计算V（1，1）（此时i=1,j=1）： 据此可以得知的前一个单元是。 然后计算，此时i=1,j=2，即： 据此可推断出的前一个单元为。此时图2-24变为（其它单元格中没有变）图2-24 i j 0 1 2 3 4 5 C A T G T 0 0 -1 -2 -3 -4 -5 1 A -1 -1 1 -1 -1 -1 2 C -2 2 -1 -1 -1 -1 3 G -3 -1 -1 -1 2 -1 4 C -4 2 -1 -1 -1 -1 5 T -5 -