2-最长公共子序列问题(无答案)

最长公共子序列问题（LCS）（生物信息学中常用算法）

子序列的概念：

设X=< x1, x2,┅, xm>，若有1≤i1< i2< ┅ Z=< z1, z2,┅, zk> = < xi1, xi2,┅, xik>，则称Z是X的子序列，

记为Ze.g. X=, Z=, 则有Z公共子序列的概念：

设X，Y是两个序列，且有Z则称Z是X和Y 的公共子序列。

最长公共子序列的概念：

若Z则称Z是X和Y 的最长公共子序列，记为ZLCS(X , Y)。

最长公共子序列往往不止一个。

e.g. X=, Y=, 则

Z=, Z’=, Z’’=

均属于LCS(X , Y) ，即X,Y有3个LCS。

如何找出X和Y的一个最长公共子序列？

Brute-force法：列出X的所有长度不超过n（即Y）的子序列，

从长到短逐一进行检查，看其是否为Y的子序列，

直到找到第一个最长公共子序列。

由于X共有2m个子序列，故此方法对较大的m没有实用价值。

是否能使用动态规划法？如何用？

分析：

记Xi=﹤x1，…，xi﹥即X序列的前i个字符 (1≤i≤m)（前缀）

Yj=﹤y1，…，yj﹥即Y序列的前j个字符 (1≤j≤n)（前缀）

假定Z=﹤z1，…，zk﹥∈LCS(X , Y)。

若xm=yn（最后一个字符相同），则不难用反证法证明：

该字符必是X与Y的任一最长公共子序列Z（设长度为k）的

最后一个字符，即有zk = xm = yn 且显然有Zk-1∈LCS(Xm-1 , Yn-1)

即Z的前缀Zk-1是Xm-1与Yn-1的最长公共子序列。

若xm≠yn，则亦不难用反证法证明：

要么Z∈LCS(Xm-1, Y)，要么Z∈LCS(X , Yn-1)。

由于zk≠xm与zk≠yn其中至少有一个必成立，因此：

若zk≠xm则有Z∈LCS(Xm-1 , Y)，

若zk≠yn 则有Z∈LCS(X , Yn-1)。

∴若xm=yn，则问题化归成求Xm-1与Yn-1的LCS

（LCS(X , Y)的长度等于LCS(Xm-1 , Yn-1)的长度加1）

若xm≠yn 则问题化归成求Xm-1与Y的LCS及X与Yn-1的LCS

LCS(X , Y)的长度为：

max{LCS(Xm-1 , Y)的长度, LCS(X , Yn-1)的长度}

求LCS(Xm-1 , Y)的长度与LCS(X , Yn-1)的长度

这两个问题不是相互的：

∵两者都需要求LCS(Xm-1，Yn-1)的长度,

因而具有重叠性。

另外两个序列的LCS中包含了两个序列的前缀的LCS，

故问题具有最优子结构性质

考虑用动态规划法。

引进一个二维数组C，用C[i,j]记录Xi与Yj的LCS的长度

如果我们是自底向上进行递推计算，那么在计算C[i,j]之前，

C[i-1,j-1], C[i-1,j]与C[i,j-1]均已计算出来。此时我们

根据X[i]=Y[j]还是X[i]Y[j]，就可以计算出C[i,j]：

若X[i]=Y[j]，则执行C[i,j]←C[i-1,j-1]+1；若X[i]Y[j]，则根据：

若C[i-1,j]≥C[i,j-1]则C[i,j]取C[i-1,j]；否则C[i,j]取C[i,j-1]。即有

0若i0或j0C[i1,j1]1若i,j0且xiyjmax{C[i1,j],C[i,j1]}若i,j0且xiC[i,j]=e.g. 如下图：

yj

0 1 2 3 4 5 6

yj B D C A B A

0 xi 0 0 0 0 0 0 0

↑ ↑ ↑↖ ↖

1 A 0 ←0 ←0←0 1←1 1

↖ ↑↖

2 B 0 1 ←1←1 ←1 2 ←2

↑ ↑↖ ↑ ↑

3 C 0 1 ←1 2 ←2←2 ←2

↖ ↑ ↑ ↑↖

4 B 0 1 ←1 2 ←2 3 ←3

↑↖ ↑ ↑ ↑ ↑

5 D 0 1 2←2 ←2 3 ←3

↑ ↑ ↑↖ ↑↖

6 A 0 1 2←2 3←3 4

↖ ↑ ↑ ↑↖ ↑

7 B 0 1 2←2 3 4 ←4

为了构造出LCS，使用一个mn的二维数组b，

b[i,j]记录C[i,j]是通过哪一个子问题的值求得的,

以决定搜索的方向：

若C[i-1,j]≥C[i,j-1]，则b[i,j]中记入“↑”；

若C[i-1,j] < C[i,j-1]，则b[i,j]中记入“←”；

算法 LCS_L(X,Y,m,n,C)

for i=0 to m do C[i,0]←0

for j=1 to n do C[0,j]←0

for i=1 to m do {

for j=1 to n do{

if x[i]=y[j] then {C[i,j]←C[i-1,j-1]+1；

b[i,j]←“↖” ；}

}else if C[i-1,j]≥C[i,j-1] then {C[i,j]←C[i-1,j]；

b[i,j]←“↑” ；}

}else{C[i,j]←C[i,j-1]；

b[i,j]←“←” ；}

算法的时间复杂度显然是(m×n)的。

输出一个LCS(X,Y)的递归算法：

LCS_Output(b,X,i,j)

If i=0 or j=0 then return;

If b[i,j]=“↖”then /*X[i]=Y[j]*/

{LCS_Output(b,X,i-1,j-1)；

输出X[i]；}

else if b[i,j]=“↑”then /*C[i-1,j]≥C[i,j-1]*/

LCS_Output(b,X,i-1,j)

else if b[i,j]=“←” then /*C[i-1,j]LCS_Output(b,X,i,j-1)

e.g. 对上述例子调用LCS_Output(b,X,7,6)。

算法分析：

由于每次调用至少向上或向左（或向上向左同时）移动一步，

故最多调用（m+n）次就会遇到i=0或j=0的情况，

此时开始返回。返回时与递归调用时方向相反，步数相同，

故算法时间复杂度为(m＋n)。

注意：仅用“↑” ，“←” ，“↖”是搜索不到所有的LCS的；

主要是由于在上述LCS_L算法里，

对于语句if C[i-1] ≥ C[i,j-1] then ….，

没有区分C[i-1,j]＞C[i,j-1] 和C[i-1,j]＝C[i,j-1]

这两种不同的情况。因此，要找出所有的LCS，

当满足X[i]Y[j]且C[i-1,j]＝C[i,j-1]时，要执行b[i,j]←“←↑”，

即记录两个搜索方向，才能够据此找出所有的LCS。

为节省空间，数组b亦可不用，直接

根据X[i]=Y[j]还是X[i]Y[j]以及C[i,j-1]，C[i-1,j]来找出搜索方向：

X[i]=Y[j]等价于b[i,j]=“↖”，

X[i]Y[j]且C[i,j-1] > C[i-1,j] 等价于b[i,j]=“←”，

X[i]Y[j]且C[i,j-1] < C[i-1,j] 等价于b[i,j]=“↑”，

X[i]Y[j]且C[i,j-1] = C[i-1,j] 等价于b[i,j]=“←↑”，

不用b数组可节省(m×n)的空间，但算法写起来稍烦一些。

执行时间的量级两者相同。

如果只需计算LCS的长度而无需求出具体的LCS，

则二维数组C也可以不用，

只用一个长为min{m,n}的数组即可。

作业：设计一个算法求出全部的LCS，分析最坏情况。

用”会计方法”证明,利用b[i,j]来求所有LCS的算法

在最坏情况下时间复杂度为O(

mCmn)。