美妙的夜晚(Smith Waterman)

习惯了凌晨来敲那些复杂的代码

因为安静

因为此时的心里才被代码完全的占据，没有一丝的杂念

搞了两天多的递归，终于出结果了，

终于没把自己仍死循环里，否则还不知道谁来break out me呢！

----------------------------------------------------以下问题描述及解决方案---------------------------------------------

Q = catgt

S= acgctg

由Query和Subject所得的得分矩阵为：

         1、

初始化得分矩阵的条件：

Matrix(0,0) = 0; ( 矩阵(0,0)这个点，初始化为0 )

Matrix(0,j) = match(-,y)+ Matrix(0,j-1) (j>=1)

Matrix(i,0) = match(x,-)+ Matrix(i-1,0) (i>=1)

                                     Matrix(i-1,j-1) + match(Q[i], S[j]);

Matrix(i,j) = max     Matrix(i-1,j) + match(Q[i], -);

                                     Matrix(i,j-1) + match(-, S[j]);

2、

match(x,x) = 2   (两个字符相匹配得2分)

match(x,y) = match(x,-) = match(-,y) = -1 (两个字符不匹配或与空格匹配得-1分)

由以上条件，得到的得分矩阵为：

	-	c	a	t	g	t
-	0	-1	-2	-3	-4	-5
a	-1	-1	1	0	-1	-2
c	-2	1	0	0	-1	-2
g	-3	0	0	-1	2	1
c	-4	-1	-1	-1	1	1
t	-5	-2	-2	1	0	3
g	6	-3	-3	0	3	2

 

回溯思想：

backTrace():

for( i=Q.length, j=S.length; i>0&&j>0; ) {

         if ( Matrix(i,j) == Matrix(i-1,j-1) + match(Q[i], S[j]) ){

         i--; j--;

}

else if ( Matrix(i,j) == Matrix(i-1,j) + match(Q[i], -) ){

         i--;

         //在Q序列中的j位置插入一个空格 ‘-’

}

else if( Matrix(i,j) == Matrix(i,j-1) + match(-, S[j]) ){

         j--;

//在S序列中的i位置插入一个空格 ‘-’

}

}

问题：需要把标红色箭头的三条路径都选出来。

如下图所示：

 

所得结果为：

q = catg-t-                           q = -c-atgt                  q = -ca-tgt

s = -acgctg                          s = acgctg-                 s = acgctg-

 

debug的结果为：（这张图是这几天见到过的最漂亮的东西了，哈哈哈）