1、7、比对的统计学显著性对于任何序列比对，我们可以计算其相似性得分，但重要的是需要判定这个分值是否足够高，是否具有显著意义（Karlin and Altschul，1990； Alexandrov and Solovyev，1998），是否能够提供进化同源性的证据。由于随机因素的影响，非同源的序列也可能具有较高的相似性得分。不幸的是，没有一种数学理论方法描述全局序列比对的期望得分的分布，无法直接分析统计显著性，需进行间接分析。下面介绍几种显著性检验的方法（王槐春，1994）。序列相似的显著性检验的典型方法是将两条待比较的序列分别随机打乱，再使用相同的程序与打分函数（或打分矩阵）进行比对，计算这些
2、随机序列的相似性得分。重复这一过程（通常为 50100 次），得到随机序列比对得分的正态分布曲线，用和分别表示其平均值与标准差。设原来两条序列的比对得分为 x，利用下式计算大于或等于 x 的比对得分概率：z = (x - )/ (3-32)z 值的单位为 SD。根据正态分布，当 z 值为 3.1、4.3 和 5.2 时，相似性得分为 x 的随机出现概率分别为 10-3、10 -5 和 10-7。可以根据 z 值判断两个序列相似得分的显著性。一般假定当 z 值大于 5 时，两条被比较的序列在进化上是相关的；当 z 值在 35 之间时，如果两者有其他方面相似的证据（如功能相似），则两条序列也是同源
3、的；如果 z 值小于 3，则表示两条序列不同源。许多序列比较软件都带有计算 z 值的程序，可直接用于评价序列比对的显著性。判断两条序列比对显著性的另一个常用方法是分析其中的一条序列（称为靶序列）对数据库检索的相似性得分的分布情况，即所检测出的其他类似序列的个数与得分大小，并根据结构域或功能的有无设立阳性对照和阴性对照。如果靶序列所检出序列的分布状态与阳性对照序列的检测结果相近，而阴性对照序列不能或仅检出很少有关的序列，则可以断定要比较的那两条序列的比对结果是有统计意义的。这种方法称为相似性得分分布分析方法，常用于数据库相似性检索的显著性评价，可以确定一些微弱的序列相似性的显著性。karlin
4、和 Altschul(Karlin and Altschul, 1990)提出一种基于概率论的显著性分析方法，他们推导出一个精确的公式，计算两条序列比对得分大于两条随机序列比对得分的概率。根据这一公式，比对得分是将第一条序列的任意一个片段与第二条序列的任意一个片段进行比对的最高得分（比较过程中不引入空位），称为最大片段得分，比对的片段称为高得分片段对（HSP）。HSP 通常用改进得 Smith-waterman 算法或简单地使用大的空位罚分方法获得。Karlin-Altschul 的计算公式如下： P(Sx) = 1- exp(-Ke-x) (3-33)其中 P(Sx)是最大片段得分大于 x
5、的概率，K 和是两个参数，它们的值取决于打分函数和序列中各种字符出现的频率。该方法只限于不引入空位的序列比较得分的显著性计算。把一个已知得比对分值 S同预期的分布相关联可以计算出 P 值，从而给出这个分值的比对显著性。通常，P 值越趋近于零，分值越有意义。把比对局限于没有空位的基础之上，使问题大大简化，但是却脱离分子生物学的实际情况。要建立一个插入和缺失的精确模型需要引入空位，但如果空位相对较少，在这些空位之间仍然可以获得高分值区域，有代表性的是可能会获得紧密相邻的 HSP。在这种情况下，从总体上去评估它的显著性是较为合理的，也许，每个片段并不显得很重要，但是几个片段同时出现就不太像是偶然事件
6、了。Karlin-Altschul 加和统计学可以计算 N 个 HSP 的统计值，这个方法的实质是把 N 个最佳片段的分值进行加总，从而计算事件偶然发生的可能性，其它一些论据也被用来确认这些分值只是在片段与比对一致的情况下进行加总。虽然加总的分值分布与 HSP 分值最大值有差异，仍然可以得到解析解。上述几种方法需要经过计算才能进行显著性的判断，有经验的专家往往能够直接进行显著性判断。Doolitter（Doolittle, 1987）提出如下的经验法则： 如果两个序列的长度都大于 100，在适当地加入空位之后，它们配对的相同率达到 25%以上，则两个序列相关； 如果配对的相同率小于 15%，则
7、不管两个序列的长度如何，它们都不可能相关； 如果两个序列的相同率在 15%25%之间，它们可能是相关的。第三节 序列多重比对与序列两两比对不一样，序列多重比对（Multiple Alignment）的目标是发现多条序列的共性。如果说序列两两比较主要用于建立两条序列的同源关系和推测它们的结构、功能，那么同时比较一组序列对于研究分子结构、功能及进化更为有用。例如，某些在生物学上有重要意义的相似性只能通过将多个序列对比排列起来才能识别。同样，只有在多序列比较之后才能发现与结构域或功能相关的保守序列片段。对于一系列同源蛋白质，人们希望研究隐含在蛋白质序列中的系统发育的关系，以便更好地理解这些蛋白质的进
8、化。在实际研究中，生物学家并不是仅仅分析单个蛋白质，而是更着重于研究蛋白质之间的关系，研究一个家族中的相关蛋白质，研究相关蛋白质序列中的保守区域，进而分析蛋白质的结构和功能。序列两两比对往往不能满足这样的需要，难以发现多个序列的共性，必须同时比对多个同源序列。图 3.13 是从多个免疫球蛋白序列中提取的 8 个片段的多重比对。这 8 个片段的多重比对揭示了保守的残基（一个是来自于二硫桥的半胱氨酸，另一个是色氨酸）、保守区域（特别是前 4 个片段末端的 Q.PG）和其它更复杂的模式，如 1 位和 3 位的疏水残基。另一个疏水模式则是每个片段起始端的折叠。实际上，多重序列比对在蛋白质结构的预测中非
9、常有用。多重比对也能用来推测各个序列的进化历史。可以看出前 4 条序列与后 4 条序列是从两个不同祖先演化而来，而这两个祖先又是由一个最原始的祖先演化得到。实际上其中的 4 个片段是从免疫球蛋白的可变区域取出的，而另 4 个片段则从免疫球蛋白的恒定区域取出。当然，如果要详细研究进化关系，还必须取更长的序列进行比对分析。对于多重序列比对的定义实际上是两个序列的推广。设有 k 个序列 s1, s2, . ,sk，每个序列由同一个VTISCTGSSSNIGAGNHVKWYQQLPGVTISCTGTSSNIGSITVNWYQQLPGLRLSCSSSGFIFSSYAMYWVRQAPGLSLTCTVSGT
10、SFDDYYSTWVRQPPGPEVTCVVVDVSHEDPQVKFNWYVDGATLVCLISDFYPGAVTVAWKADSAALGCLVKDYFPEPVTVSWNSGVSLTCLVKGFYPSDIAVEWESNG图 3.13 多重序列比对(Fuellen, 1997)字母表中的字符组成，k 大于 2，通过插入操作，使得各序列 s1, s2, . ,sk 的长度一样，从而形成这些序列的多重比对。如果将各序列在垂直方向排列起来，则可以根据每一列观察各序列中字符的对应关系，如图 3-13。通过序列的多重比对，可以得到一个序列家族的序列特征。当给定一个新序列时，根据序列特征，判断这个序列是否属于该
11、家族。对于多序列比对，现有的大多数算法都基于渐进的比对的思想，在序列两两比对的基础上逐步优化多序列比对的结果。进行多序列比对后可以对比对结果进行进一步处理，例如构建序列模式的 profile，将序列聚类构建分子进化树等等。1、SP（Sum-of-Pairs）模型在多重比对中，首先要对所得到的比对进行评价，以确定其优劣。例如，对图 3-13 中的 8 个序列进行比对，可以得到另外两种结果，如图 3.14 所示。那么，这样的三个多重比对，哪一个更好呢？这就需要有一种方法来评价一个多重比对。评价一个多重序列比对比评价序列两两比对结果更复杂。这里，我们假设得分（代价）函数具有加和性，即多重比对的得分是
12、各列得分总和。因此，我们首先考虑如何给比对的每一列打分，然后将各列的和加起来，成为一个总得分。在处理每一列时，自然的处理方式是寻找一个具有 k 个变量的打分函数（k 是参与多重比对的序列的个数），而每一个变量或者是一个来自特定字母表中的字符，或者是一个空白。我们很难得到这样一种具有 k 个变量的表达式函数。另一方面，这种隐式函数不具有统一的形式，随着 k 的变化，函数的表现形式也发生变化，不利于计算机处理。可以考虑使用显式函数，在实现时，用一个 k 维数组来表示该显式函数（类似于打分矩阵），指定对应于 k 个变量各种组合的函数值。这带来一个问题，即所需的数组空间很大，而且随着 k 的变化，数据
13、结构也要随之动态变化。我们所期望的函数在形式上应该简单，具有统一的形式，不随序列的个数而发生形式变化。根据得分函数的意义，函数值应独立于各参数的顺序，即与待比较的序列先后次序无关。另外，对相同的VTISCTGSSSNIG-AGNHVKWYQQLPG VTISCTGSSSNIGAGNHVKWYQQLPGVTISCTGTSSNIG-SITVNWYQQLPG VTISCTGTSSNIGSITVNWYQQLPGLRLSCSSSGFIFS-SYAMYWVRQAPG LRLSCS-SSGFIFSSYAMYWVRQAPGLSLTCTVSGTSFD-DYYSTWVRQPPG LSLTCTVSGTSFDDYYS
14、TWVRQPPGPEVTCVVVDVSHEDPQVKFNW-YVDG PEVTCVVVDVSHEDPQVKFNWYVDGATLVCLISDFYPG-AVTVAW-KADS ATLVCLISDFYPGAVTVAWKADSAALGCLVKDYFPE-PVTVSW-NS-G AALGCLVKDYFPEPVTVSWNSGVSLTCLVKGFYPS-DIAVEW-ESNG VSLTCLVKGFYPSDIAVEWESNG（a） （b）图 3.14 多重序列比对结果比较(Fuellen, 1997)或相似字符的比对，奖励的得分值高，而对于不相关的字符比对或空白，则进行惩罚（得分为负值）。满足上述条件的一个函
15、数就是常用的逐对加和 SP（sum-of-pairs）函数。SP 函数定义为一列中所有字符对得分之和：(3-34)其中，c 1,c2,ck是一列中的 k 个字符，p 是关于一对字符相似性的打分函数，对于 p 可采用不同的定义。例如：总得分根据字符两两比较得分计算演化而来，即逐对计算 p(1,2)，p (1,3) ，.，p (1,8)，p (2,3) ，p(2,4)，.，p (2,8)，.，p (7,8) 的所有得分，再加和得到结果。在上述计算中，假定：如果两个对比的字符相同，则得分为 0，否则得分为-1。所以上述一列的得分为：（-7-6-5-4-3-2-1 ）+2=-26。将一个多重比对所有列
16、的得分全部加起来，其和即为该多重序列比对的得分。注意，在进行多重序列比对时，可能会出现两个空缺字符的比对，因此需要扩充函数 p 的定义域，即增加 p(-，-)的定义。通常的定义是p(- , -) = 0 （3-35）这似乎有点意外，因为一般只要是遇到空缺字符，其得分就应该是负的，所以两个空缺字符的比对应得到更多的负分。但是这样处理是有道理的。在序列多重比对中，我们往往在得到整体的比对的基础上进一步分析两个序列的对应关系。例如，根据图 3-13 的比对结果，取出最后两个比对的序列，见图3.15（a）。这里存在空缺字符对比列，相当于这两条序列都进行了插入操作。但是由于插入位置相同（如图 3.15（
17、a）箭头所指位置），这两条序列本身在此位置上是完全相同的，所以此位置上的编辑代价为零，或者得分为 0。因而在分析这两个序列时，可以去掉这些空缺字符对比的列，得到由多重序列比对结果推演的两两比对，如图 3.15（b）所示。其结果又称为多重序列比对在两个特定序列上的投影（projection）。121 ),(),.(kiijjicpcscoreSP26GSPALscore若先处理每一个序列对，在处理序列对时，逐个计算字符对，最后加和，则 SP 得分模型的计算公式如下：(3-36)这里， 是一个多重比对， ij是由推演出来的序列 s i 和 s j 的两两比对。具体计算 SP 时，我们可以先对多重序
18、列比对的每一列进行计算，然后将每一列的得分值相加；也可以先计算每一对推演出来的两两序列比对的得分，然后再加和。但是注意，上述两种计算过程仅在 p(- , -)=0 条件成立下才等价。2、多重比对的动态规划算法多重序列比对的最终目标是通过处理得到一个得分最高（或代价最小）的序列对比排列，从而分析各序列之间的相似性和差异。如同处理序列两两比对一样，依然可以用动态规划方法。回想前一节中穿越距离矩阵的路径。距离矩阵相当于二维平面，对于三条序列，每一种可能的比对可类似地用三维晶格中的一条路径表示，而每一维对应于一个序列，如图 3.16 所示。路径的起点为晶格的左下角，路径的终点为晶格的右上后角。图 3.
19、16 中的路径记为 (0,0,0)，(1,0,0) ，(2,1,0)，(3,2,0) ，(3,3,1)，(4,3,2)。如果存在多个序列，则形成的空间是超晶格（Hyperlattice ）。假设在晶格的顶端、前面、后面各有一平行光源，这些光源将代表多重序列比对的路径投影到相对的侧面，即投影到一对序列所在的平面。图 3.16 仅画出了右边的光源。将多重比对投影到两个序列所在的平面在加速优化计算中将起着重要的作用。一个投影的结果可能比原来要短，例如，下面的多重序列比对G-SNSGN-SGNAVSNSAALGCLVKDYFPEPVTVSWNSGVSLTCLVKGFYPSDIAVEWESNG （a ）
20、AALGCLVKDYFPEPVTVSWNSGVSLTCLVKGFYPSDIAVEWESNG（b）图 3.15 多重比对的投影jiiscoreSP)(如果在前两个序列方向进行投影，则投影结果为：G-SNSGN-S如果路径的某一段沿投影方向进行，那么该段路径就不可能产生投影。图 3.16 中的第一段沿着第一条序列向前进，推进方向垂直于其它两条序列，则平行光源对这一段不产生直线投影，而仅仅产生一个投影点。序列两两比对的动态规划方法经改进后可直接用于序列的多重比对。就二重序列而言，将动态规划方法计算过程看成在二维平面按一定顺序访问每一个节点，访问节点的顺序取决于节点之间的关系，如图 3.7 所示。二维
21、平面（或二维晶格）与前面所介绍的超晶格相似，上一节距离矩阵中的位置与每一个晶格节点相对应。在计算过程中，对每个节点计算其代价。每个节点的代价代表两个子序列最优比对的代价，而晶格最后一个节点（右下角节点）的代价即为两条完整序列的比对代价。在超晶格中，序列的放置与上一节有所不同，计算是从左下角进行的，而不是距离矩阵中的左上角。如图 3.17 所示，计算过程从超晶格的坐标点（0,0,0）开始，按节点之间的依赖关系向右上后方推进，直到计算完最后一个节点。实际计算时，可以采用类似二维的计算方式，即先高维后低维（对应于先行后列）。在图 3.17 中，当前点的代价计算取决于和它相邻的 7 条边，分别对应于匹
22、配/替换或引入空缺等三种编辑操作。计算各操作的代价（包括前继节点的代价），选择一个代价最小的操作，并将代价和存放于该节点。在三维或超晶格中，计算公式与上一节相似，但计算一个节点依赖于更多终点 SA光源A投影 平行投影NSV S N S VSN-S起点 路径 -NSA-. -AS图 3.16 三条序列所对应的三维晶格的前趋节点。在三维情况下要考虑 7 个前趋节点，在 k 维情况下要考虑 2k-1 个前趋节点。假设以 k 维数组 A 存放超晶格，则计算过程如下：（1）a 0, 0, ,0 = 0（2）a i = max a i - b + SP-score(Column(s, i, b)这里 i
23、是一个向量，代表当前点， b 是具有 k 个元素的非零二进向量，代表 i 与前一个点的相对位置差（例如，在二维的情况下，b =（1，1）、（1，0）或（0，1），s 代表待比对的序列集合，而(3-37)if bj = 1if bj = 0 (3-38)SP-score(Column(s, i, b)代表 SP 模型的得分值。计算过程是一个递推的过程，在计算每个晶格节点得分的时候，将其各前趋节点的值分别加上从前趋节点到当前点的 SP 得分，然后取最大值作为当前节点的值。随着待比对的序列数目增加，计算量和所要求的计算空间猛增。 对于 k 个序列的比对，动态规划算法需要处理 k 维空间里的每一个节点
24、，计算量自然与晶格中的节点数成正比，而节点数等于各序列长度的乘积。另外，计算每个节点依赖于其前趋节点的个数。在二维情况下，前趋节点个数等于 3，三维等于 7，四维等于 15。对于 k 维超晶格，前趋节点的个数等于 2k - 1。因此用动态规划方法计算多重比对的时间复杂度为 O(2ki=1,.,k si)。这个计算量是巨大的，而动态规划算法对计算空间的要求也是很大的。称一个问题在多项式时间内可解，当且仅当存在一个时间复杂度为 O(nc)的求解算法，其中 c 是常数，n 是问题的输入规模（如序列的长度、序列的个数）。例如前面介绍的序列两两比较动态规划算法的时间复杂度为 O(n2)。假设有 k 个长
25、度 n 的序列，则利用 SP 模型寻找最优多重序列比对算法的时间复杂度为 O(2knk)，这里 k 和 n 都是问题的规模。当前计算点图 3.17 三维晶格节点计算依赖关系)(,(jj kisccColumn可以证明，利用 SP 模型寻找最优多重序列比对是一个 NP-完全问题（Wang and Jiang , 1994）。1971 年，Cook 给出 NP-完全问题的定义（Cook，1971）。P 类问题为多项式界的问题；NP 类问题是这样一类问题，如果有一个复杂度为多项式的算法解决其中的某个问题，则所有这些问题都在 P 类中；而 NP-完全问题是这样一类问题，如果其中的某个问题存在多项式界的
26、算法，则 NP 类中的每一个问题都存在一个多项式界算法（巴斯，1985）。但是，几乎所有专家都认为不可能在多项式时间内准确求解 NP-完全问题。简单地说，所谓 NP-完全问题是这样一类问题，我们可以在多项式的时间内验证问题的一个解是否是正确的。例如，假设你不必计算最优的多重序列比对，只要验证一个给定多重比对的SP 得分小于某个特定值，这时，可以编写一个具有多项式时间复杂度的算法进行验证。对于生物信息学的问题，有许多是 NP-完全问题。在实际应用中，有一些变通的方法可以用来求解NP-完全问题。概括如下：（1）只求解规模比较小的问题；（2）利用动态规划、分支约束等技术减小搜索空间，提高求解问题的效
27、率；（3）针对具体问题的特点，根据实际输入情况，设计实用求解算法，这样的算法虽然在最坏的情况下其时间复杂度是非多项式的，但是算法执行的平均效率和复杂度与多项式的算法相当；（4）采用近似算法或者启发式方法，如局部搜索、模拟退火、遗传算法等。对基于 SP 模型寻找最优多重序列比对这样一个问题，可以用近似的方法求解，其算法的时间复杂度可用多项式表示（Gusfield 1993; Bafna V, et al. 1994）。下面分别介绍几种实用的多重序列比对算法。3、 优化计算方法如果待比对的序列很多，多重序列比对所形成的超晶格空间将非常大，算法不可能访问所有的节点，而且也没有必要这样做。正如序列两两
28、比对一样，可以想象代表最优的路径处于主对角线附近，至少不会在超晶格中的某个平面上。假设已知一个试探性的路径与最优的路径靠近，并且两条路径最多相距 r 个单位，则应当将动态规划算法所要计算的节点限制在以试探性路径为中心、半径为 r 的区域内，这样做无疑可以提高算法的效率。我们不能盲目地搜索整个空间，应该利用人工智能空间搜索策略的剪枝技术，根据问题本身的特殊性将搜索空间限定在一个较小的区域范围内。若问题是搜索一条得分最高（或代价最小）的路径，则在搜索时如果当前路径的得分低于某个下限（或累积代价已经超过某个上限），则对当前路径进行剪枝，即不再搜索当前路径的后续空间。在双重序列比对中, Fickett
29、 和 Ukkonen 设计了一种定界约束过程 (bounding procedure)的方法来减少计算量，其中距离矩阵的上界和下界可以预先确定或动态变化。为了在多维空间上使用动态规划算法，Carrillo 和 Lipman（Carrillo and Lipman，1988）将这种思想引入到多重序列比对，即先进行初步的序列双重比对，以限制进一步作多重序列全面比对所需要的多维空间的大小和计算量，从而克服了多序列的维数、空间和运算量之间的矛盾。这里介绍 Carrilo-Lipman 的优化计算方法，该算法是基于下述关系的，即多重序列比对与向两个序列投影之间的关系，也就是通过公式（3-34）将 SP
30、得分与序列两两比对的得分联系起来。设 k 个序列 s1, s2, . ,sk 的长度分别为 n1, n2, . , nk，按照 SP 得分模型计算这些序列的最优比对。依然采用动态规划方法，但并不计算超晶格空间中所有的节点，而是仅处理“相关”的节点。但是，那些节点是相关的呢？这需要观察节点在两个序列上的投影。假设是关于 k 条序列 s1, s2, . ,sk 的最优多重比对。注意这并不意味着向某两条序列的投影是这两条序列的最优比对。我们可以按下述方法测试超晶格空间中的一个节点是否是相关节点：从某个节点向任何两个序列所在的平面投影，如果该投影是这两个序列两两最优比对的一部分（前面一部分），则该节点
31、是相关节点。在说明具体的优化计算方法之前，先介绍一种计算两条序列经过特定断点的最优比对算法。设有两条序列 s、t，已知它们的两个断点分别是 i、j，则 s、t 对于经过特定断点（i、j ）的最优比对可分为两个部分，一是对应于两条序列前缀 0:s:i 与 o:t:j 的最优比对，另一个是对应于两条序列后缀 i:s:m 与 j:t:n的最优比对, m、n 分别为两条序列的长度。实际上，经过特定断点的最优比对是两个比对。为了得到特定断点的最优比对，用两个矩阵 A 和 B，其值为：ai, j = sim(0:s:i , o:t:j)bi, j = sim(i:s:m , j:t:n)对于矩阵 A 的计
32、算和标准算法一样，而对于矩阵 B 的计算则是反方向的，即先对 B 的最后一行和最后一列进行初始化，然后反向推进到（0，0）。这样，矩阵 A 与 B 的和 C=A+B 包含了在特定断点（i、j）的最优比对得分。称 C 矩阵为总得分矩阵，而 A、B 分别是前缀和后缀的得分矩阵。根据矩阵 C，我们可以迅速求出两个序列的最优比对，而不需要像上一节用反向跟踪的方法求出最优比对所对应的路径。图 3.18 列出了根据某个打分模型计算得到的矩阵 A 和 C。可以看出，根据 C的最大值，可非常容易地找出最优比对所对应的路径。G A T T C0 -2 -4 -6 -8 -10A -2 -1 -1 -3 -5 -
33、7T -4 -3 -2 0 -2 -4T -6 -5 -4 -1 1 -1C -8 -7 -6 -3 -1 2G -10 -7 -8 -5 -3 0G -12 -9 -8 -7 -5 -2G A T T C-2 -2 -7 -12 -17 -22A -7 -4 -2 -7 -12 -17T -10 -7 -5 -2 -7 -12T -13 -10 -7 -5 -2 -7C -14 -13 -10 -5 -4 -2G -17 -13 -13 -8 -4 -2G -22 -17 -14 -11 -7 -2（a） （b）-ATTCGGGATTC-（c）图 3.18 （a ）前缀矩阵；（b）总得分矩阵
34、；（c）最优比对虽然最优多重比对的投影不一定是两两最优比对，但是我们可以为投影的得分设立一个下限。定理 3-1：设是关于 s1, s2, . ,sk 的最优比对，如果 SP-score() L，则score(ij) Lij (3-39)其中Lij = L - ( sim(sx, sy) )xy,(x,y)(i,j)证明：SP-score() L score( xy ) Lxy score(xy ) L - score(ij)xy,(x,y)(i,j) sim(sx,sy ) L - score(ij)xy,(x,y)(i,j)由此定理得到证明。这里，L 实际上是最优多重比对的一个下限，而 Li
35、j 是序列 si 和序列 sj 比对得分的一个下限。现在需要判断超晶格中的一个节点 i = (i1, i2, , ik )是否在 L 的限制下与最优比对相关。简单地说， 如果一个节点满足定理的条件，则该节点是相关的。若条件不满足，即 score(ij)小，则不可能是相关的，因此 i 肯定不会处于最优路径上。当然，上述条件只是一个必要条件，但不是充分条件。满足条件只是说明 i 可能处于最优路径，但不一定处于最优路径。条件的作用是限制搜索空间，提高算法实现效率。将上述条件进一步具体化，则如果对于所有的 1 x y k，i 满足cxyix, iy Lxy则 i 是相关的。这里 cxy 是序列 sx
36、和 sy 的总得分矩阵。这个具体的条件是根据前面的叙述推演出来的，因为如果 cxyix, iyLxy，则说明经过 ix, iy断点的 sx 和 sy 的最优得分小于 Lxy，而 score(xy )小于最优得分，所以 score(xy ) Lxy，所以定理 3-1 的条件不满足，因而超晶格点 i 是非相关的。为了得到一个合理的下限 L，我们可以任选一个包含所有序列的多重比对，计算其得分，以此作为 L。若选取的 L 接近于最优值，算法速度将大大提高。注意，L 的值不能超过最优值，否则算法出错。在实现上述优化计算方法时必须非常仔细。不可能对超晶格中的每一个节点都进行上述判断，否则计算时间不会有多大
37、的减少。我们需要一种剪枝方法，它一次能够将许多不相关节点删除。从超晶格的零点 0 = (0, 0, , 0) 出发，此节点总是相关的。逐步扩展节点，直到终点 (n1, , nk)，在扩展过程中，仅分析相关节点。称一个节点 i 影响另一个节点 j，如果在计算 aj时用到 i。这又称为j 依赖于 i。i 和 j 关系的另一特征是：b=j - i 是一个非零的二进向量，每一个节点依赖于其它 2 k-1 个节点。为了便于处理，设置一个缓冲区，该缓冲区内仅存放相关节点的后续节点。首先将 0 放入其中。当一个节点 i 进入缓冲区时，其对应的值 ai被初始化，然后 ai的值在随后的阶段中被更新。当该节点离开缓冲区时，其值即为该点真正的值，并用于其它节点（依赖于此节点）的计算。当然，其后续节点是否要计算，还取决于 i 是否为相关节点，若不是，则不再计算其后续的其它节点。具体的过程如下：设 j 是一个依赖于 i 的相关节点，如果 j 不在缓冲区内，则将其放入缓冲，并计算
