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

最长公共子序列问题（LCS）（生物信息学中常用算法） 子序列的概念： 设X= x1, x2,┅, xm，若有1≤i1 i2 ┅ ik≤m，使得 Z= z1, z2,┅, zk = xi1, xi2,┅, xik，则称Z是X的子序列， 记为ZX。 e.g. X=A,B,C,B,D,A,B, Z=B,C,B,A, 则有ZX。 公共子序列的概念： 设X，Y是两个序列，且有ZX和ZY， 则称Z是X和Y 的公共子序列。 最长公共子序列的概念： 若ZX，ZY，且不存在比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的所有长度不超过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]。即有 C[i,j]= e.g. 如下图： 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]是