4 T 1 5 5 5 5 — —

表3-2 TY的后继表

i CH(i) 0 1 2 3 4 5 6 7

1 A 1 6 6 6 6 — — —

2 C 3 3 3 — — — — —

3 G 5 5 5 5 5 — — —

4 T 2 2 4 4 7 7 7 —

(i,j)和(k,l)是字符序列X与Y的两个匹配点，如果i<k, j<l,称(i,j)是()（k,l）的前继匹配点或者(k,l)是(i,j)的后继匹配点，用(i,j)<(k,l)表示这种关系。

是匹配点(i,j)的后继匹配点集合，k如果，并且没有一个点满足称(k,l)是(i,j)的直接后继匹配点，并将这种关系表示为(i,j)>(k,l)。

如果匹配点且不存在满足，称(i,j)为初始匹配点。对于一个匹配点，它的层次被定义为：

从上述的定义中，可以推导一下定理：

定理1：字符序列X与Y的LCS的长度为|LCS(X,Y)|，。

证明：假设X与Y的最长公共子序列的匹配点是。是初始匹配点，, ()的层次是k。可以推导出r是最高层，。假设r不是最高层，必然存在，。则，这与相矛盾。

产生后继匹配点的过程:在的算法中，首先通过后继表并发产生初始匹配点的所有后继匹配点。这些后继匹配点的直接后继匹配点也用上述的方法产生。重复上述的操作直至没有后继匹配点可以产生。因此，生成所有匹配点的直接后继匹配点是算法中基础操作。

对于一个匹配点，产生它的所有的直接后继匹配点方法如下：

从(3-3)中，可知上述的操作就是将TX的第i列的元素和TY的第j列的元素结合起来。

比如在例子1中的匹配点(2,5)的直接后继匹配点可由TX的第2列元素和TY的第5列元素组成。他们分别是(4,6)，(3,-)，(-,-)和(5,7)。在这里，(3,-)和(-,-)并不能代表匹配点，他们只能说明他们达到了搜索后继点的终点。丢弃了(3,-)和(-,-)之后,(2,5)的后继点为(4,6)和(5,7)。

定理2:根据(3-3)中的方法，可以找出所有匹配点的直接后继匹配点。 适合大数据分析MLCS算法的设计与实现(5):http://www.youerw.com/jisuanji/lunwen_123957.html