第2章配对序列比对2bak

第四节全局序列比对(GlobalSequenceAlignment)在介绍全局比对之前，我们得首先说明的是对任何比对方法（包括全局比对，局部比对）主要包括两部分：第一部分就是计算最大相似得分数，也就是这两个序列比对的最优化计算过程。第二部分是在根据这个最大相似得分数，通过“回溯”方式确定两个序列的比对结果即第一个序列中的各字符（在DNA中为对应的碱基，在蛋白质中为对应的氨基酸残基）与第二个序列中哪个字符相匹配。通过这个结果可以确定相应保守区，可变区，这样据此可推断这两个序列是否有同源关系以及其同源性程度。这部分工作在比对中一般称为“回溯”（traceback）。我们首先考虑两个序列nssS,,1和nttT,1，现在要求解的问题是如何通过计算求出这两个序列的比对结果，以确定其相似程度。为使读者对比较容易理解全局比对的算法，我们这里通过一个具体例子的计算来说明。由于蛋白质有20个氨基酸残基，相应的得分表比较复杂，为此我们这里的例子采用一小段DNA序列来说明其具本计算过程。实例，两个序列S=ACCTGA和T=CATGTAT，对应的得分矩阵假设为：表2-3四个碱基的得分矩阵ATCG*A2-1-1-1-1T-12-1-1-1C-1-12-1-1G-1-1-12-1*-1-1-1-12为此我们首先假设ba,代表序列S中第a个字符即as与序列T中第b个字符bt之间的相似分数，比如当a=3时，Cs2;b=4时，Gt4，根据得分矩阵，14,2;同样的23,4。这样我们可得到与序列S和T对应的表格σ即图2-7：ij012345CATGT00-1-1-1-1-11A-1-12-1-1-12C-12-1-1-1-13G-1-1-1-12-14C-12-1-1-1-15T-1-1-12-126G-1-1-1-12-1T序列图2-20序列S=ACCTGA和T=CATGTAT之间的各碱基之间对应得分即σ得到对应的σ矩阵。然后我们根据比对的两大组成，首先就可在此基础上应用动态规划法计算各子序列之间最优的比对得分即相应的最佳相似性分数即比对的第一部分。然后应用回溯法给出比对结果。第一步，计算两个序列的最优（大）相似性分数。1，我们假设jiV,是序列nS,,1和mT,,1(0≤i≤n,0≤j≤m)。m,和n分别为这两个序列的长度，在本例子中n=5;m=6。2，初始条件：)22(,0)12(),(0,00jkkikkT，jVSiV3，迭代，相应的迭代公式：对1≤i≤n,1≤j≤m，有CTjiVBSjiVATSjiVjiVjiji32,1,)32(,,132,1,1,这里的迭代公式对生物学工作者而言，可能比较复杂，为此，我们将它表示成相应的图：1,1jiV),(jT),(iS),(jiTS图2-21迭代过程示意图这样整个比对过程就可如下图所示：S序列BAC（0，0）（m,n）图2-22整个动态规划计算示意图4，寻找第m列（即最后一列）中所有元素的最大值:miVmiVmi,max,1*5，寻找第n行（即最后一行）中所有元素的最大值：jnVjnVmj,max),(1*6，寻找最优比对值，即**,,,max,jnVmiVTSV现在我们以图2-20为例为说明上面公式的应用。根据初始条件，图2-20变为图2-23ij012345CATGT00-1-2-3-4-51A-1-12-1-1-12C-22-1-1-1-13G-3-1-1-12-14C-42-1-1-1-15T-5-1-12-126G-6-1-1-12-1图2-23序列S=ACCTGA和T=CATGTAT比对初始值设置T序列S序列图2-23中红色部分即是根据初条件计算得到（其它单元格中没有变）在迭代过程中，根据迭代公式计算V（1，1）（此时i=1,j=1）：12111012111101101100max11，，V，，V，，（V，V据此可以得知1,1V的前一个单元是0,0V。然后计算2,1V，此时i=1,j=2，即：12112113121201212110max21，，V，，V，，（V，V据此可推断出21，V的前一个单元为1,0V。此时图2-24变为（其它单元格中没有变）图2-24ij012345CATGT00-1-2-3-4-51A-1-11-1-1-12C-22-1-1-1-13G-3-1-1-12-14C-42-1-1-1-15T-5-1-12-126G-6-1-1-12-1图2-24图2-23通过两步迭代计算后的结果不断应用上述迭代公式计算，便可得到全部的5,4,3,2,1,06,5,4,3,2,1,0,,jijiV即图2-26ij012345CATGT00-1-2-3-4-5T序列S序列T序列1A-1-110-122C-2100-1-23G-300-1214C-4-1-1-1115T-5-2-21036G-6-3-3032图2-25序列S=ACCTGA和T=CATGTAT比对计算最终结果ij012345CATGT00-1-2-3-4-51A-1-110-122C-2100-1-23G-300-1214C-4-1-1-1115T-5-2-21036G-6-3-3032图2-26回溯图当两个序列每个碱基对的最优比对计算完成后，接下来的工作是在表2-7-3中找出最后一行和最后一列中最大的单元格，并比较这两个最大的单元格，以最终确定其最优比对结果。在这个例子中，最后一行的最优值（即最大值）是3，最后一列中最优值也为3。相应的单位格分别是（6，4）和（5，5）即图2-26中蓝色的两个方框。然后比较这两个方框中的值以确定最终比对结果（即S和T的Alignment）。在本例子中，由于它们相等，因此有两个比对结果，即有两个最优值。以上是全局比对算法的第一步。第二步，回溯，给出两个序列的比对结果根据前面的讨论：当两个序列的最大相似得分数确定后，接下来的工作就是将第一个序T序列S序列S序列列中的各字符与第二个序列中的各字符一一匹配起来。就是通常的回溯过程。由于我们在前面计算每对（第一个序列中的字符与第二个序列中的字符）字符时已记下它们对应的前一段字符，因此这个工作就相对比较容易。图2-26最终的回溯结果可以得到三个比对结果，见图2-27图2-27三个比对结果得到上述三个比对结果，这里就涉及到生物大分子序列分析中的一个非常基本的概念，序列残基数相等（SequenceIdentity）。它有很多方式的定义，但相比之下，我个人认为下面这个定义比较能反映比对的实际情况：它的定义是通过比对，其残基数相同的配对数与全部配对数的百分比。比如在图2-8中，结果共有对残基相匹配即A-A，C-T，G-G，T-T。在这四对中有三对是相等的残基对，因此其序列残基数相等百分比为：ID%=3/4×100%=75%这里应重点强调，序列残基数相等百分比的概念在生物信息学中尤其是生物大分子序列分析中非常有用，因此也非常重要。比如，现在在生物学界普遍认为当两个蛋白质通过比对后，如果序列残基数相等百分比大于20-30%，则就认为这两个蛋白质具有同源性，其三维构构象也比较相似。因而据此也可根据已知功能的蛋白质推断未知功能的新蛋白质。这正是生物信息学的主要宗旨之一：即通过计算即生物信息学方法的处理，向实验工作者提供相应的有意义的结果，这里就是应用序列残基数相等百分比来推断新发现蛋白质的功能。显然有着非常现实的意义。全局比对的计算时间是mnO,(m,n分别为两个待比较序列的长度)级。显然如果两个较长的序列，其比对时间则会很快增加。近似算法FASTA和BLAST就是在尽可能不降低比对精度的情况下尽可能减少计算时间，以期增加比对速度。我们之所以用这么长的篇幅来介绍全局比对，主要原因有：1.全局比对是所有比对法的基础，如果全局比对方法搞清楚了，则其它比对方法就容易理解了。因为它们主要部分与全局比对方法是相同的。2.全局比对法涉及到的基本概念如序列残基数相等（SequenceIdentity），比对得分数等基本概念贯穿于整个生物大分子序列分析。对生物学工作理解应用某种软件分析生物大分子序列所得到的结果是必要的。如果这些基本概念没有搞清楚，则就谈不上应用生物信息学的基本方法来解决所面临的实际问题。第五节局部序列比对（LocalAlignment）顾名思义，局部比对就是要从两个序列中各自找出两个相似性最高的子序列片段。在许多情况下，如果从整体上看，两个序列并不怎么相似或者说它们通过全局比对得到的最大相似性得分数不大，但它们中的一些局部片段是很相似的，这就要求我们只要将这部分局分的片段找出来就达到目的，而不需要考查它们的整体相似性。这在现代生物学中是很有意义的。比如，在蛋白质序列中，有一部分序列片段主要是与它的生物学功能有关，而另一部分片段则对该蛋白质的功能影响较小。因此，对两个类似这样的蛋白质，我们没有必要考虑它们整个蛋白质的比对而确定它们的相似性，我们只需要知道它们部分片段是否相似就可以了。这样就可以更加有针对性地比较两个蛋白质序列或DNA序列。典型的在DNA序列中，它有代码区（外显子exons））和非代码区（内含子introns）.一般地，代码区能最终翻译成蛋白质，代表基因的功能，因此它不易突变，其主要目的是能保证该基因（或蛋白质）功能的稳定性，而非代码区即内含子则比较容易突变，因此如果应用局部比对技术比较两个不同种类的DNA，则找到的序列最相似的那段片段就有可能是基因了。同样的，在蛋白质中，功能区与其它部分相对比较保守，因此应用局部比对技术比较两个不同来源的蛋白质，进而据此推断它们的功能。对局部比对，我们在前面已有一个实例了。这里就不再重复了。局部比对的计算与全局比对相比，其主要不同点是：应用全局比对的计算方法进行计算，当计算到有分数值小于或等于零时，就将此分数值强制设定为零。而当回溯时碰到某个单元可为零时，就停止回溯，显然其比对结果中的子序列不一定要从原比对序列开始，也就是说可以是两个序列中的中间某个片段。这正体现了局部比对的精神。它的基本算法如下：对两个待比对的序列S和T（与全局比对相同）1，初始条件：)52(0,0)42(00,jViV2，迭代，相应的迭代公式：对1≤i≤n,1≤j≤m，有DTjiVCSjiVBTSjiVAjiVjiji62,1,)62(,,162,1,1)62(0,3.从V中寻找最大相似性得分即对应的对元格。72,max,1,1**jiVjiVmjni从以止的计算公式中我们不难看出，局部比对计算与全局比对相比的不同点：1.最初条件不一样，局部比对均为0，而局部比对则为字符与空位得分的累计。2.在比对过程中，如果计算某个单元格小于零，就设置为零。3.回溯过程中遇到零的单元格时就此停止。我们仍以介绍全局比对法所用的例子来说明局部比对，主要是通过这个例子来说明局部比对与全局比对之间有什么不同。根据初始条件2-4和2-5，我们可得到如下的矩阵即图2-28.然后应用迭代公式2-6（A，B，C，D）计算相应的局部序列的得分总数，图2-28.最后通过回溯得到其比对结果即图2-29.由图2-29可知，所得到的比对结果中的两个序列均为原序列中的片段。这也就是前面多次提到的局部比对与全局比对的主要区别，也