Dot_Matrix点阵是序列比对的最基础算法

1、代码如下：public class Dot_Matrix_Java { public static void main(String[] args) { //输入两序列 String s1="AACAAAAAACACAGTCGATCGATCGATCGATGCATGCAGCATGCTGATCAGCTACGATGC";//long String s2="AACAAAAAACACAGTCGATCGATCGATCGATGCATGCAGCATGCTGATCAG";//short //创建数组 int[][] h=new int[s1.length()][s2.length()]; //返回并输出点阵 System.out.println("Result:"); System.out.print(" "); for(int i=0;i<s2.length();i++){ System.out.print(" "+s2.charAt(i)+" "); } System.out.println(); for(int i=0;i<s1.length();i++){ System.out.print(s1.charAt(i)); for(int j=0;j<s2.length();j++){ if(s1.charAt(i)==s2.charAt(j)){ System.out.print(" * "); h[i][j]=1; }else{ System.out.print(" "); h[i][j]=0; } if(j!=0&&j%(s2.length()-1)==0){ System.out.println(); } } } //返回并输出打分矩阵 System.out.println("Score_Matrix:"); for(int i=0;i<h.length;i++){ for(int j=0;j<h[0].length;j++){ System.out.print(h[i][j]+" "); if(j!=0&&j%(s2.length()-1)==0){ System.out.println(); } } } //回溯并输出结果 String result=get_back(h,s1,s2); boolean count=false; StringBuffer sb=new StringBuffer(); for(int i=0;i<result.length();i++){ if(result.charAt(i)==' '){ count=true; }else{ if(count){ count=false; sb.append(','); } sb.append(result.charAt(i)); } } System.out.println(); System.out.println(sb.toString()); } //回溯方法 public static String get_back(int [][] h,String s1,String s2){ int num = 1; StringBuffer sb = new StringBuffer(); for(int i=h[0].length-1;i>=0;i--){ int j=h.length-1; for(int temp=i;temp>=0;temp--,j--){ if(h[j][temp]==1){ sb.insert(0, s1.charAt(j)); }else{ sb.insert(0, ' '); } } sb.insert(0, ' '); } for(int i=h.length-2;i>=0;i--){ int j=h[0].length-1; if(i>j){ for(int temp=i;j>=0;temp--,j--){ if(h[temp][j]==1){ sb.insert(0, s1.charAt(temp)); }else{ sb.insert(0, ' '); } } }else{ for(int temp=i;temp>=0;temp--,j--){ if(h[temp][j]==1){ sb.insert(0, s1.charAt(temp)); }else{ sb.insert(0, ' '); } } } sb.insert(0, ' '); } return sb.toString(); } }

2、由以上代码得到的结果噪音多，背景复杂故对其进行优化，采用shift_frame方法

3、由shift_frame得到的结果清晰，直观代码如下：public class Dot_Matirx_shift_熠硒勘唏frame { public static void main(String[] args) { String s1="AACAAAAAACACAGTCGATCGATCGATCGATGCATGCAGCATGCTGATCAGCTACGATGC"; String s2="AACAAAAAACACAGTCGATCGATCGATCGATGCATGCAGCATGCTGATCAG"; int T=10; for(int i=0;i<s1.length()-T;i++){ String sub_1=s1.substring(i,i+T); for(int j=0;j<s2.length()-T;j++){ String sub_2=s2.substring(j,j+T); if(score(sub_1,sub_2)>=10){ System.out.print(" * "); }else{ System.out.print(" "); } } System.out.println(); } } public static int score(String sub_1,String sub_2){ int mark=0; for(int i=0;i<sub_1.length();i++){ if(sub_1.charAt(i)==sub_2.charAt(i)){ mark+=1; } } return mark; } }