Needleman Wusch算法全局比对（Java）
1、首先了解一下这个算法，这是动态规划中的一个经典例子，对于递归的概念的深刻理解，将一个大问题变成小问题，并逐步求解。由第一个字符，我们假设为缺失开始，每一加一个字符，都有三种情况，mismatch，match，deletion/insert,对应的进行打分。高分值的为最优解，逐步延伸至最后一个字符。如有不懂，可以对这个模型在进行深刻理解。
2、该代码对回溯步骤进行简化，仅返回一个最优解，但是该方法简单，适合初级编程者，自学所用。
源代码：
/*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[tlen+1][plen+1];
int [][] d=new int[tlen+1][plen+1];
/*初始化矩阵，第一列或行为deletion后者insert,扣分2*/
for(int i=0;i<1;i++){
for(int j=0;j<plen+1;j++){
h[i][j]=-2*j;
d[i][j]=3;
}
}
for(int j=0;j<1;j++){
for(int i=0;i<tlen+1;i++){
h[i][j]=-2*i;
d[i][j]=1;
}
}
/*动态规划用于打分*/
for(int i=1;i<tlen+1;i++){
for(int j=1;j<plen+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[i][j]=maximum(h[i-1][j]+s1,h[i-1][j-1]+s2,h[i][j-1]+s3);
d[i][j]=l;
}
}
/*输出打分矩阵*/
System.out.println("score matrix:");
for(int i=0;i<tlen+1;i++){
for(int j=0;j<plen+1;j++){
System.out.printf("%4d",h[i][j]);
if(j!=0&&j%plen==0){
System.out.println();
}
}
}
/*输出索引矩阵*/
System.out.println("index matrix:");
for(int i=0;i<tlen+1;i++){
for(int j=0;j<plen+1;j++){
System.out.print(d[i][j]+" ");
if(j!=0&&j%plen==0){
System.out.println();
}
}
}
/*输出结果*/
System.out.print("Target sequence:");
String result =get_back(t,p,d);
for (int i=0;i<result.length();i++){
System.out.print(result.charAt(i)+" ");
}
System.out.println();
System.out.print("Source sequence:");
for (int i=0;i<p.length();i++){
System.out.print(p.charAt(i)+" ");
}
}
/*求最大值的方法*/
public static int maximum(int a,int b,int c){
int max =a;
l=1;
if(a<b){
max=b;
l=2;
if(b<c){
max=c;
l=3;
}
}else if(a<c){
max=c;
l=3;
}
if(max==a&&max==b){
l=4;
}else if(max==a&&max==c){
l=5;
}else if(max==b&&max==c){
l=6;
}
if(max==a&&max==b&&max==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>=0&&j>0){
int start = d[i][j];
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、结果分析：
Target sequence:G C G C - A A T G
Source sequence:G C C C T A G C G
此结果为最优解之一。
