SimoneSmith Waterman算法经典局部比对算法（一）
的有关信息介绍如下：
Smith Waterman算法是经典的局部比对算法，本文将对其进行模拟运算，使用Java语言，进行运算，将比对两条DNA序列，得出最佳比对模型，与前一算法相似，将采用最优解之一，与全局比对算法的区别是局部最优解和全局最优解的区别。
首先对Smith Waterman算法原理需要有深刻的理解，可以查看网上资料或书籍，简单介绍一下，递归思想，采用动态规划编程，其与全局比对的区别是，可以开始与任何位置并结束于任何位置。
采用规则如下：
0
match=+1
mismatch=-1
delete/insert=-2
得分score=max(0,match,mismatch,delete/insert)
我们采用Java实现，得到得分矩阵h，指针矩阵d，从而回溯结果输出结果。
代码如下：
import java.util.Arrays;
public class Smith_Waterman {
static int l;
public static void main(String[] args) {
String s="CGATGCTGCTAGCTGCTAGCTAGCTACGATGCTAC";
String t="GCTAGCTGC";
int [][] h =new int [t.length()+1][s.length()+1];
int [][] d =new int [t.length()+1][s.length()+1];
for(int i=0;i h[i]=0; if(i==0){ for(int j=0;j h[i][j]=0; } } } for(int i=1;i for(int j=1;j int score =0; if(t.charAt(i-1)==s.charAt(j-1)){ score =1; }else{ score=-1; } h[i][j]=maximum(h[i-1][j]-2,h[i-1][j-1]+score,h[i][j-1]-2); d[i][j]=l; } } System.out.println("score matrix:"); for(int i=0;i for(int j=0;j System.out.printf("%4d",h[i][j]); if(j!=0&&j%s.length()==0){ System.out.println(); } } } System.out.println(); System.out.println("index matrix:"); for(int i=0;i for(int j=0;j System.out.printf("%4d",d[i][j]); if(j!=0&&j%s.length()==0){ System.out.println(); } } } System.out.println("*********************************"); String[] result=get_back(t,s,h,d).split(","); int in =s.indexOf(result); int on =t.indexOf(result); System.out.println(s); for(int i=0;i System.out.print(" "); } System.out.print(t); } public static int maximum(int a,int b,int c){ int max = 0; int [] m =new int; m=0;m=a;m=b;m=c; Arrays.sort(m); max=m; if(max==a){ l=1; if(a==b){ l=3; }else if(a==c){ l=5; } }else if(max==b){ l=2; if(b==a){ l=3; }else if(b==c){ l=6; } }else if(max==c){ l=3; if(c==b){ l=6; }else if(c==a){ l=5; } }else if(max==0&&a!=0&&b!=0&&c!=0){ l=0; } return max; } public static String get_back(String t,String p,int[][] h,int [][] d){ StringBuffer sb1 = new StringBuffer(); StringBuffer sb2 = new StringBuffer(); int start_row=0; int start_column=0; int max =h[start_row][start_column]; for(int i=0;i for(int j=0;j if(h[i][j]>max){ max=h[i][j]; start_row=i; start_column=j; } } } sb1.insert(0, t.charAt(start_row-1)); sb2.insert(0, p.charAt(start_column-1)); do{ int start = d[start_row][start_column]; switch(start){ case 1:sb1.insert(0, t.charAt(start_row-2));sb2.insert(0, p.charAt(start_column-2));start_row=start_row-1;break; case 2:sb1.insert(0, t.charAt(start_row-2));sb2.insert(0, p.charAt(start_column-2));start_row=start_row-1;start_column=start_column-1;break; case 3:sb1.insert(0, '-');start_column=start_column-1;break; case 4:sb1.insert(0, t.charAt(start_row-2));sb2.insert(0, p.charAt(start_column-2));start_row=start_row-1;start_column=start_column-1;break; case 5:sb1.insert(0, t.charAt(start_row-2));sb2.insert(0, p.charAt(start_column-2));start_row=start_row-1;break; case 6:sb1.insert(0, t.charAt(start_row-2));sb2.insert(0, p.charAt(start_column-2));start_row=start_row-1;start_column=start_column-1;break; } }while(h[start_row-1][start_column-1]>0); if(d[start_row-1][start_column-1]!=0){ do{ int start = d[start_row][start_column]; switch(start){ case 1:sb1.insert(0, t.charAt(start_row-2));sb2.insert(0, p.charAt(start_column-1));start_row=start_row-1;break; case 2:sb1.insert(0, t.charAt(start_row-2));sb2.insert(0, p.charAt(start_column-1));start_row=start_row-1;start_column=start_column-1;break; case 3:sb1.insert(0, '-');start_column=start_column-1;break; } }while(h[start_row-1][start_column-1]>0); } String result=sb1.toString()+","+sb2.toString(); return result; } } 结果如下： CGATGCTGCTAGCTGCTAGCTAGCTACGATGCTAC GCTAGCTGC 得出其在序列上的最佳比对位置。 在引物设计、基因识别中可以应用。
