文章编号:1672-2477(2008)04-0052-05利用矩阵搜索求所有最长公共子序列的算法宫洁卿(东南大学软件学院,江苏南京211189)摘要:利用动态规划法求出二维数组的情况下,使用矩阵搜索的方法求出所有分支,从而求出所有最长公共子序列的算法.该算法将通常认为的指数量级的时间复杂度降低到了max{O(cmn),O(ck)}.随后对此算法的正确性以及效率做了证明.关键词:最长公共子序列(LCS);矩阵搜索;算法中图分类号:TP301.6文献标识码:A前言最长公共子序列(LongestCommonSubsequence)算法是一种非常基础的算法.其主要目的是找出两个序列中最长的公共子序列.目前LCS算法在生物工程上有着广泛的应用.在生物工程中,基因序列是保存生物基本信息的地方,包含了海量的生物数据,基因由4种不同的碱基通过不同的组合来表现,人类基因有将近30亿个DNA碱基对,呈双螺旋结构.随着基因序列长度的增长,其组合的数量也是以指数级增长,通过人工对DNA的差异进行比较分析是难以实现的.因此,分子生物学家越来越依靠高效的计算机字符串比较算法,即将基因序列的问题转换为由4种基本字符组合出来的字符串,并以此为基础进行处理.在基因工程中,经常需要比较位于相同位置的两条不同的基因序列,根据找出的公共自序列来对样本进行分析.在常见的基因分析中,一般需要找到所有的最长公共子序列,此时LCS算法成为首选.然而,目前对LCS算法的研究一般针对的是对某一个最长公共子序列的算法进行优化和分析,对求出所有的最长公共子序列的研究,目前尚无针对此问题的优秀算法[2～5].传统的算法都是基于路径依赖的关系求所有公共自序列.本文利用动态规划法,在计算出二维数组的情况下,提出一种称为矩阵搜索的方法求出所有分支,从而求出所有最长公共子序列的算法,该算法将通常认为的指数量级的时间复杂度降低到了max{O(cmn),O(ck)}.1背景知识定义1子序列的概念:设X=(x1,x2,,xm),若有1≤i1<i2<<ik≤m,使得Z=(z1,z2,,xik),则称Z是X的子序列,记为Z<X.,zk)=(xi1,xi2,=(A,B,C,B,D,A,B),Z=(B,C,B,A),则有Z<X.公共子序列的概念:设X,Y是两个序列,且有Z<X和Z<Y,则称Z是X和Y的公共子e.g.X定义2序列.定义3最长公共子序列的概念:若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,D,A,B)均属于LCS(X,Y),即X,Y有3个LCS.1.2传统解法Z=(B,C,B,A),Z′=(B,C,A,B),传统的LCS解法是采用动态规划算法(DynamicPrograming)来解决.其解法可以用一个递归函数来表示:收稿日期:2008-08-10作者简介:宫洁卿(1984—),男,安徽芜湖人,硕士研究生0若i=0或j=0C[i,j]=C[i-1,j-1]+1若i,j>0且xi=yjmax{C[i-1,j],C[i,j-1]}若i,j>0且xi≠yi引进一个二维数组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].每一个C[I,j]还负责纪录自己是通过哪个子问题的值求得的.一共有5种可能:从左边,从上边,从左上,从左边和上边,无.2基于矩阵搜索的算法2.1二维数组C的分析本算法是基于通过动态规划算法给出的二维数组C为基础进行计算的.根据图1的矩阵可以看到,每一个从3→2,2→1,1→0的路线就是需要的结果.如果是使用穷举的方法走所有的路线,那么获得的结果很多都是重复的,并且比较是否是不同的结果也会非常的麻烦.通过观察图1可以发现,如果可以从某个(n+1)→n出发,能够用某种手段得到所有的n→(n-1),那么其中n→n的路线并不需要去关心,只要证明从(n+1)→n到n→(n-1)是连通的就可以.2.2传统解法以及缺点以图1为例,传统的解法是从二维矩阵的右下角考虑搜索所有的路线.这种方法最大的缺点就是要搜索所有的路径.在最坏的情况下,搜索了O(C2n)数量级的路线,只得到1个结果.目前现有的优化方法是避免走重复的路线.算法将所走过的路径压入栈中,在走不同的路径时与栈中的元素比较,如果是曾经走过的路径且没有新的分支,则直接抛弃掉.图1二维矩阵一传统解法的最大缺点是在于:算法还是基于自顶向下的分支搜索,必须要走遍所有的分支,且在避免走重复路径的时...