Needleman Wusch算法是经典的全局比对算法，用于比对两条DNA序列或者蛋白质序列的同源性或者说相似性，不过这两者的概念有所不同。本例使用Java对该算法进行实现，并且返回一个最优结果。作为对该算法的学习以及理解有所帮助。工具/原料moreJavaNetbean方法/步骤1/3分步阅读

首先了解一下这个算法，这是动态规划中的一个经典例子，对于递归的概念的深刻理解，将一个大问题变成小问题，并逐步求解。由第一个字符，我们假设为缺失开始，每一加一个字符，都有三种情况，mismatch，match，deletion/insert,对应的进行打分。高分值的为最优解，逐步延伸至最后一个字符。如有不懂，可以对这个模型在进行深刻理解。

2/3

该代码对回溯步骤进行简化，仅返回一个最优解，但是该方法简单，适合初级编程者，自学所用。

源代码：

/*Needleman Wunsch是一个全局比对算法，可用于DNA和蛋白质序列的全局比对*/

public class Needleman_Wunsch {

/*全局变量用于回溯是的指针*/

static int l=0;

public static void main(String args) {

/*比对的两列字符串*/

String t=GCGCAATG;

String p =GCCCTAGCG;

/*创建H矩阵用于打分，成为打分矩阵，创建D矩阵用于回溯，成为指针矩阵或者方向矩阵*/

int tlen=t.length();

int plen=p.length();

int h=new int;

int d=new int;

/*初始化矩阵，第一列或行为deletion后者insert,扣分2*/

for(int i=0;i1;i++){

for(int j=0;jplen+1;j++){

h=-2*j;

d=3;

}

}

for(int j=0;j1;j++){

for(int i=0;itlen+1;i++){

h=-2*i;

d=1;

}

}

/*动态规划用于打分*/

for(int i=1;itlen+1;i++){

for(int j=1;jplen+1;j++){

/*分值：mismatch（失配）-1，deletion(缺失)/inserting（插入）-2，match（匹配）1，*/

int s1=-2,s2=0,s3=-2;

if(t.charAt(i-1)==p.charAt(j-1)){

s2=1;

}else{

s2=-1;

}

h=maximum(h+s1,h+s2,h+s3);

d=l;

}

}

/*输出打分矩阵*/

System.out.println(score matrix:);

for(int i=0;itlen+1;i++){

for(int j=0;jplen+1;j++){

System.out.printf(%4d,h);

if(j!=0j%plen==0){

System.out.println();

}

}

}

/*输出索引矩阵*/

System.out.println(index matrix:);

for(int i=0;itlen+1;i++){

for(int j=0;jplen+1;j++){

System.out.print(d+ );

if(j!=0j%plen==0){

System.out.println();

}

}

}

/*输出结果*/

System.out.print(Target sequence:);

String result =get_back(t,p,d);

for (int i=0;iresult.length();i++){

System.out.print(result.charAt(i)+ );

}

System.out.println();

System.out.print(Source sequence:);

for (int i=0;ip.length();i++){

System.out.print(p.charAt(i)+ );

}

}

/*求最大值的方法*/

public static int maximum(int a,int b,int c){

int max =a;

l=1;

if(ab){

max=b;

l=2;

if(bc){

max=c;

l=3;

}

}else if(ac){

max=c;

l=3;

}

if(max==amax==b){

l=4;

}else if(max==amax==c){

l=5;

}else if(max==bmax==c){

l=6;

}

if(max==amax==bmax==c){

l=7;

}

return max;

}

/*回溯方法*/

public static String get_back(String t,String p,int d){

int i=t.length();

int j=p.length();

StringBuffer sb = new StringBuffer();

while(i=0j0){

int start = d;

switch(start){

case 1:sb.insert(0, t.charAt(i-1));i=i-1;break;

case 2:sb.insert(0, t.charAt(i-1));i=i-1;j=j-1;break;

case 3:sb.insert(0, -);j=j-1;break;

case 4:sb.insert(0, t.charAt(i-1));i=i-1;j=j-1;break;

case 5:sb.insert(0, t.charAt(i-1));i=i-1;break;

case 6:sb.insert(0, t.charAt(i-1));i=i-1;j=j-1;break;

case 7:sb.insert(0, t.charAt(i-1));i=i-1;j=j-1;break;

}

}

String result =sb.toString();

return result;

}

}

3/3

结果分析：

Target sequence:G C G C - A A T G

Source sequence:G C C C T A G C G

此结果为最优解之一。

注意事项

需要对该理论有深刻理解推荐阅读《生物信息学导论》

对Java基础编程扎实