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;
}
}
