2025年Neddle-Wunch算法的C++实现

科技前沿 • 2025-04-01 10:47 • 阅读 57

大家好，我是讯享网，很高兴认识大家。

生物信息课要求每人准备一个ppt，介绍生物信息学领域的相关内容。所以我脑海中瞬间浮现了NW算法与遗传算法。正好一个是计算机技术解决生物问题，一个是生物学思想指导的算法。接下来大部分时间用来NW算法的代码了，发现写着还是有点难度的，毕竟这么久没有写代码了。NW算法的核心就是动态规划，结合设定的罚分矩阵，思路挺容易的，就是实现的时候，要记得走过的最优路径，并且最后显示出来。

课上的讲解，效果其实并不好。因为动态规划这个思想在十分钟内能说清已经不错了，要想懂，还得自己琢磨。

并且教授这门课的老师，并不是偏向于算法设计方向的，讲了半天没人回应额.........

讯享网

下面是我写的代码，基本能实现要求：

#include<iostream> #include<string> using namespace std; struct Pair{ int w; int v;//v是该位置的累计积分。 };//w的允许有三个值，0代表向下的箭头，1代表斜向下的箭头，2代表向右的箭头。 int tran(char a){ int c; if (a=='A'){ c=0; } if (a=='G'){ c=1; }if (a=='C'){ c=2; }if (a=='T'){ c=3; } return c; }//将输入的字符序列变为数字序列。 int main(){ string s1; string s2; cin >> s1 >> s2;//限制输入 的字符串的长度小于100 int m,n; m=s1.size(); n=s2.size(); //将输入的字符串AGCT转化为0，1，2，3 int s[5][5]; int gap=-5; s[0][0]=10;s[1][0]=-1;s[2][0]=-3;s[2][1]=-5; s[1][1]=7;s[3][0]=-4;s[3][1]=-3;s[3][2]=0; s[2][2]=9; s[3][3]=8; for(int i=0;i<4;i++){ for(int j=0;j<4;j++){ if(s[i][j]!=0){ s[j][i]=s[i][j]; } } } Pair dp[100][100]; dp[0][0].v=0; dp[0][0].w=0; for(int i=0;i<=m;i++){ for(int j=0;j<=n;j++){ if(i==0&&j!=0){ dp[i][j].v=dp[i][j-1].v+gap; dp[i][j].w=2; } if(j==0&&i!=0){ dp[i][j].v=dp[i-1][j].v+gap; dp[i][j].w=0; }//以上是计算基准情况 } } for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ int x=tran(s1[i-1]); int y=tran(s2[j-1]); if(dp[i-1][j].v+gap>dp[i-1][j-1].v+s[x][y]){ dp[i][j].v=dp[i-1][j].v+gap; dp[i][j].w=0; } else{ dp[i][j].v=dp[i-1][j-1].v+s[x][y]; dp[i][j].w=1; } if(dp[i][j].v<dp[i][j-1].v+gap){ dp[i][j].w=2; dp[i][j].v=dp[i][j-1].v+gap; } } } cout << "最终得分矩阵为" << endl; for(int i=0;i<=m;i++){ for(int j=0;j<=n;j++){ cout << dp[i][j].v << " "; if(j==n){ cout << endl; } } } string s3,s4;//存放排队的方案 int a,b; a=m;b=n; int xx=0; while(a>=0&&b>=0){ if(dp[a][b].w==0){ s3[xx]=s1[a-1]; s4[xx]=' '; a-=1; } else{ if(dp[a][b].w==1){ s3[xx]=s1[a-1]; s4[xx]=s2[b-1]; a-=1; b-=1; } else{ if(dp[a][b].w==2){ s3[xx]=' '; s4[xx]=s2[b-1]; b-=1; } } } xx=xx+1; } cout << "输出标记的路径：" << endl; for(int i=0;i<=m;i++){ for(int j=0;j<=n;j++){ cout << dp[i][j].w<< " "; if(j==n){ cout << endl; } } } cout << "输出最相似的配对方案" << endl; for(int i=xx-2;i>=0;i--){ cout << s3[i]; } cout << endl; for(int i=xx-2;i>=0;i--){ cout << s4[i]; } cout << endl; return 0; }

讯享网

2025年Neddle-Wunch算法的C++实现

相关推荐