首页 > 编程知识 正文

最长公共子串 DNA序列,最长公共子序列最优解

时间:2023-05-05 04:24:00 阅读:136035 作者:4174

一、概念1 .指定的字符串str='ABCDADNENXY '

http://www.Sina.com/:从str中任选移除若干个(包括0个)字符,且其馀为用于此str的子序列,例如ABC、ABXY、DADXY等,其中无需在中间连续。

子序列:与子序列不同,子序列必须是连续的。 例如,ABCD、ENXY、CDADNE都是子串,但AXY不是。 因为中途断了,所以是连续的。

子串必须是子串,子串不一定是子串。

2 .最长公共子序列(Longest Common Sequence ) )。

给定字符串str1和str2,如果一个字符串s是相同的str1和str2的子序列,则s称为两者的公共子序列,如果s最长,则s称为最长公共子序列,即LCS。

例如,如果str1='ABCBDCA '、str2='DABDA ',那么两者的一个公共子序列为AA,而最长的公共子序列为ABDA。

此外,如str1=bacd ABC、str2=ax BDC,由于两者的LCS有多个,例如BDC、ABC、ADC均为LCS,因此需要明确LCS可能不是唯一的。

第二,LCS的长度LCS问题可以分解为求LCS的长度,求出LCS具体是哪个字符串,求LCS的长度看起来比较简单。

子串: A和b分别是长度为x和y的两个字符串,要求A=a1、a2、ax、B=b1、b2、by,以及a和b的LCS。

观察问题描述和b的最后一个字符,如果相等,则该字符必须属于LCS的一部分,否则该字符可能属于LCS的一部分。 据此建立动态规划的状态转移方程。

思路:如果已经给出了a和b,则可以用LCS(x,y )表示a和b的具体解法:。 试着求出递归关系式吧。

LCS长度

1.

2.如果A和B尾部字符相同

3.如果不相同

4.递推公式的边界

————————————————————————————————————————————————

最终求出的是LCS(x,y )的值,在明确了递归关系式的情况下,能够通过递归或“循环式”方式用代码求出LCS(x,y )的值。

代码如下所示。

# include iostream # include string.husingnamespacestd; //请注意,递归方法//a和b分别在输入的字符串前附加“”空字符。 是为了解决边界问题。 intLCS(stringa,string B,int x,int y ) if(x==0||y==0) /边界returrer else//非边界位置(if(a[x]==b[y] ) ) /最后ELSEreturnmax(LCS(a,b,x,y-1 ),LCS ) a,b,x-1,y ); }}int main () {string A='BCBACABBACDX '; string B='BCXYDADJL '; //A和b的LCS是BCAD int x=A.length (; int y=B.length (; A=' ' A; B=' ' B; intresult=LCS(a,b,x,y ); cout result endl; 返回0; } # include iostream # include string.husingnamespacestd; //LCS [ x ] [ y ] int main ((stringa=' bcbacabbacdx '; string B='BCXYDADJL '; //A和b的LCS是BCAD int x=A.length (; int y=B.length (; A=' ' A; B=' ' B; int i,j; int ** LCS=new int*[x 1]; for(I=0; i=x; I ) {LCS[i]=new int[y 1]; for(j=0; j=y; j ) LCS[i][j]=0; //LCS[i][j]表示}for(I=0; i=x; I ) for ) j=0; j=y; j ) if(I==0||j==0) LCS[i][j]=0; ELSE{if(a[I]==b[j] ) LCS[i][j]

= LCS[i-1][j-1] + 1; elseLCS[i][j] = max(LCS[i-1][j], LCS[i][j-1]);}int result = LCS[x][y];cout << result << endl;return 0; }三、如何求出具体的LCS

LCS长度问题已经通过递推关系式求解出来了,现在来思考如何求出具体的序列有哪些字符组成. 由于LCS的非唯一, 为了简化问题,我们先求出其中一个,如果有多个LCS不要求都求出来,求出一个即可.

对于两个字符串  A = "ABCBDAB"  和   B = "BDCABA", 由上面的代码已经求出LCS长度为4, 可以看出来LCS可以是BDAB或BCAB或BCBA等,我们的目标是求出其中任意一个.

我们回忆求LCS长度的过程,是打表求出LCS[i][j](0<=i<=x,   0<=j<=y)这个二维数组. 下面手动计算这个过程.

1.二维数组或称为表格LCS[x][y]初始化


2.逐行按照递推关系式运算,结果依次如下:



                    ......

3.最终的表格状态为:


表格右下角的值为LCS[x][y] = 4, 我们需要考虑的是4是怎么计算出来的,反推数字4的来历,记录这个路径,就可以找规律求出其中一个LCS了.

例如,最右下角的4,由于B!=A,因此是取左边4和上面4的最大值,两个4一样大,这个也从侧门反映了这个球LCS的问题的LCS不唯一.

那么我们的代码是怎么计算的呢,看一下代码

if(A[i] == B[j])LCS[i][j] = LCS[i-1][j-1] + 1; elseLCS[i][j] = max(LCS[i-1][j], LCS[i][j-1]);

对于(i, j)位置,

如果A[i]==B[j],那么左上方向的数据+1,填到(i, j)位置

否则左边和上边两个方向的最大值,填到(i, j)位置

对于(i, j) = (7, 6),即最右下角,A[7]!=B[6],所以看LCS[6][6]和LCS[7][5],这两个值都是4,怎么办?我们的代码是取

max(LCS[i-1][j], LCS[i][j-1])

那我们怎么记录(7, 6)位置的4是从左边还是从上面来的呢,随便取一个就可以。比如,在遇到max里面两个都相等的时候,取上面的那个,

那么这个4的得到的过程如下图所示:


反推得到的路径为  结束,如果我们遍历一下这个路径(i,j),打印出满足A[i]=B[j]的字符,得到的是:BCBA,这刚好是要求的LCS之一,求出一个即可.

所以,在“循环打表”的代码基础上记录路径就可以得到诸多LCS其中的一个了.

代码如下:

#include<iostream> #include<string.h>using namespace std;//循环打表 的方式求LCS[x][y] int main(){//string A = "ABCBDAB";//string B = "BDCABA";string A = "ABCBDABXBXZWUNBV";string B = "BDCABAXWBVQUADABA";int x = A.length();int y = B.length();A = ' ' + A;B = ' ' + B;int i, j;int ** LCS = new int*[x+1];int ** dir = new int*[x+1];//dir用于记录方向 ,规定该数组元素取值只有0 1 2三种,分别表示左上,左,上 //dir[i][j]表示LCS[i][j]是从哪个方向得到的 for(i=0;i<=x;i++){LCS[i] = new int[y+1];dir[i] = new int[y+1];for (j=0;j<=y;j++)LCS[i][j] = 0;//}for(i=0;i<=x;i++)for(j=0;j<=y;j++)if(i==0 || j==0)LCS[i][j] = 0;else{if(A[i] == B[j]){LCS[i][j] = LCS[i-1][j-1] + 1; dir[i][j] = 0;//左上 }else{LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1]);if(LCS[i-1][j]>=LCS[i][j-1])//如果>=改为>,得到的LCS不一样 dir[i][j] = 1;//i变化 上 elsedir[i][j] = 2;//j变化 左 } }int result = LCS[x][y];cout << result << endl;//根据dir求出路径,即一系列(i,j), 同时判断 A[i]==B[j]i = x, j = y;string lcs = "";while(!(i==0 || j==0)){cout << i << " " << j << endl;if(A[i]==B[j]){lcs = A[i] + lcs;cout << A[i] << endl; } if(dir[i][j]==0)i--, j--;else if(dir[i][j]==1)i--;elsej--;}cout << lcs << endl;return 0; }这样可以求出一个LCS,至于如何求出所有的LCS问题,后续再讨论.


版权声明:该文观点仅代表作者本人。处理文章:请发送邮件至 三1五14八八95#扣扣.com 举报,一经查实,本站将立刻删除。