美妙的夜晚(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分)

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

回溯思想：

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的结果为：（这张图是这几天见到过的最漂亮的东西了，哈哈哈）