2-最长公共子序列问题

最长公共子序列问题（LCS）（生物信息学中常用算法）子序列的概念：设X = <x1, x2,┅, x m>，若有1≤i1<i2< ┅ <i k≤m，使得Z=< z1, z2,┅, z k> = <x i1, x i2,┅, x ik>，则称Z是X的子序列，记为Z<X。

e.g. X=<A,B,C,B,D,A,B>, Z=<B,C,B,A>, 则有Z<X。

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

最长公共子序列的概念：若Z<X，Z<Y，且不存在比Z更长的X和Y 的公共子序列，则称Z是X和Y 的最长公共子序列，记为Z LCS(X , Y)。

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

e.g. X=<A,B,C,B,D,A,B>, Y=<B,D,C,A,B,A>, 则Z=<B,C,B,A>, Z’=<B,C,A,B>, Z’’=<B,D,A,B>均属于LCS(X , Y) ，即X,Y有3个LCS。

如何找出X和Y的一个最长公共子序列？Brute-force法：（设X的长度大于Y，即有m>n）列出X的所有长度不超过n（即∣Y∣）的子序列，从长到短逐一进行检查，看其是否为Y的子序列，直到找到第一个最长公共子序列。

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

是否能使用动态规划法？如何用？分析：记X i=﹤x1，…，x i﹥即X序列的前i个字符(1≤i≤m)（前缀）Y j=﹤y1，…，y j﹥即Y序列的前j个字符(1≤j≤n)（前缀）假定Z=﹤z1，…，z k﹥∈LCS(X , Y)。

若x m=y n（最后一个字符相同），则不难用反证法证明：该字符必是X与Y的任一最长公共子序列Z（设长度为k）的最后一个字符，即有z k = x m = y n。

且显然有Z k-1∈LCS(X m-1 , Y n-1)即Z的前缀Z k-1是X m-1与Y n-1的最长公共子序列。

若x m≠y n，则亦不难用反证法证明：要么Z∈LCS(X m-1, Y)，要么Z∈LCS(X , Y n-1)。

由于z k≠x m与z k≠y n其中至少有一个必成立，因此：若z k≠x m则有Z∈LCS(X m-1 , Y)，若z k≠y n 则有Z∈LCS(X , Y n-1)。

∴若x m=y n，则问题化归成求X m-1与Y n-1的LCS（LCS(X , Y)的长度等于LCS(X m-1 , Y n-1)的长度加1）若x m≠y n，则问题化归成求X m-1与Y的LCS及X与Y n-1的LCS LCS(X , Y)的长度为：Max {LCS(X m-1 , Y)的长度, LCS(X , Y n-1)的长度}求LCS(X m-1 , Y)的长度与LCS(X , Y n-1)的长度这两个问题不是相互独立的：∵两者都需要求LCS(X m-1，Y n-1)的长度,因而具有重叠性。

此外，两个序列的LCS中包含了两个序列的前缀的LCS，故问题具有最优子结构性质⇒考虑用动态规划法。

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

如果我们是按行、列的序号从小到大地进行递推计算，（从第1行开始计算：C[1,1]、C[1,2]、。

C[1,n]，再算C[2,1]、C[2,2]、。

C[2,n]，。

最后计算C[m,1]、C[m,2]、。

C[m,n]，最后算出的C[m,n]即为LCS(X , Y)的长度。

）那么在计算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]。

即有C[i,j]=⎪⎪⎩⎪⎪⎨⎧⎪⎪⎭⎪⎪⎬⎫≠>--=>+--==y x y x j i j i j i j i C j i C j i j i C j i 且若且若或若0,]}1,[],,1[max{0,1]1,1[000 为了构造出LCS ，使用一个m ⨯n 的二维数组b ，b[i,j]记录C[i,j]是通过哪一个子问题的值求得的,以决定搜索的方向：若X[i]=Y[j]，则b[i,j]中记入“↖”（亦可不记）；若X[i]≠Y[j]且C[i-1,j] ≥ C[i,j-1]，则b[i,j]中记入“↑”；若X[i]≠Y[j]且C[i-1,j] < C[i,j-1]，则b[i,j]中记入“←”；e.g. 对于X=<A,B,C,B,D,A,B>，Y=<B,D,C,A,B,A>，求出的各个C[i,j]与b[i,j]如下图：0 1 2 3 4 5 6y j B D C A B A0 x i 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_L(X,Y,m,n,C,b)（求出各个C[i,j]与b[i,j]）for i=0 to m do C[i,0]←0for j=1 to n do C[0,j]←0for 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 /*X[i]≠Y[j]且C[i-1,j]≥C[i,j-1]*/ LCS_Output(b,X,i-1,j)else if b[i,j]=“←” then /*X[i]≠Y[j]且C[i-1,j]<C[i,j-1]*/ 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。

故本例应为0 1 2 3 4 5 6y j B D C A B A0 x i0 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为节省空间，数组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}的数组即可。

（作为思考题）作业：利用b[i,j]，设计一个算法求出全部的LCS，利用”会计方法”，分析你所编算法的时间复杂度的最坏情况。

（在最坏情况下，所编算法的时间复杂度有可能为O(m n m C+)）该作业要完成一份报告，并提交。

附：实验报告的要求1、算法设计、流程图绘制、报告撰写各环节必须独立完成。

2、实验报告要满足下述各个方面的要求：首先要对问题进行分析，找出解决问题的关键环节，注意内容与课件相同者只需写“该部分思路同课件”即可。

其次要对算法进行设计构思，并在报告中写出自己的思路，这部分内容要求不仅自己能读懂，他人读后也能完全理解。

算法设计完成后，用流程图（中文）形式把算法表达出来，流程图要画详细（包括算法中的所有if-then-else判断），特别是当字符相同时的详细处理办法(算法思路中也要写), 不能只画未能完全反映所给算法具体思路的简单粗框图。

程序运行通过后，要对多种实例(至少3组以上)进行测试，给出各实例运行后的截屏，并对运行结果进行分析，分析的内容要尽可能全面、客观、深入。

在报告的最后附上自己所编制的程序。

3、未按上述要求撰写报告者，将根据具体情况酌情扣分。