Thursday, January 31, 2013

Sequence Alignment problem: Recursive solution without memoization


Thanks to Tim RougGarden's Alogrithms course -II, I worked on the sequence alignment problem. To the uninitiated, the sequence alignment program is to quantify the difference between two given sequences. Also, I have used help from here to post code for the first time(Yay!*2) on my blog
public class sqq {

String X,Y;
int blankfine=10,matchfine = 100;
int fine(char a, char b){
if(a==b)
return 0;
if(a=='-'||b=='-')
return blankfine;
return matchfine;
}

int seqAlign(int i, int j){

if(i==0&&j==0)
return fine(X.charAt(0),Y.charAt(0));
if(i<0&&j>=0)
return j*blankfine;
if(j<0&&i>=0)
return i*blankfine;
int t1 = seqAlign(i-1,j-1)+fine(X.charAt(i),Y.charAt(j));
int t2 = seqAlign(i-1,j)+fine(X.charAt(i),'-');
int t3 = seqAlign(i,j-1)+fine(Y.charAt(j),'-');
int temp = min(t1 , t2 , t3);
System.out.println("i= "+i+" j= "+j+" Ans: " + temp);
System.out.println(t1+" "+t2+" "+t3);
System.out.println("char i: "+X.charAt(i)+" char j: "+Y.charAt(j));

return temp;
}

int min(int a,int b, int c){
if(a<b&& a<c)
return a;
if(b<a&& b<c)
return b;
if(c<b&& c<a)
return c;
if(a<b)
return a;
else
return b;
}
public static void main(String farts[]){
sqq sq = new sqq();
sq.X = "ce";
sq.Y = "cd";
System.out.println(sq.seqAlign(sq.X.length()-1,sq.Y.length()-1));
}
}

No comments: