我必须编写一个程序,使用仿射间隙惩罚函数在两个序列之间进行全局对齐。动态算法(修改后的 Needleman Wunsch)计算两个给定序列s和t的相似度(表示序列相似程度的最大分数)。它通过构建三个二维数组来考虑间隙,即序列中的连续空间块,这些空间比孤立空间更容易出现。数组不能如此正式地描述为:
数组 C:保持以序列s的字符与序列t的字符对齐的字符结尾的块的最大分数;数组 BS:为以序列t
的字符结尾的块保持最大分数,与序列s中的空格对齐
数组 BT:为以序列s的字符结尾的块保持最大分数,并与序列t中的空格对齐;
该算法具有以下递推关系:
C[i,j] = v(s[i],t[j]) + max{C[i-1][j-1], BS[i-1][j-1], BT[i- 1][j-1]}
BS[i,j] = max{C[i][j-1]-(h+g), BS[i][j-1]-g, BT[i][ j-1]-(h+g)}
BT[i,j] = max{C[i-1][j]-(h+g), BS[i-1][j]-(h+g ), BT[i-1][j]-g}
** v(s[i],t[i]) = 匹配值(当两个字符相同时)或不匹配(当字符不相同时)相似度是每个数组的最后一个值中的最大值。问题是当我运行程序时,它有一个奇怪的行为:
对于给定的序列对,如果我更改哪个是 t 或 s,我的程序会为同一对序列给出不同的值。那么,您能帮我找出程序为什么会有这样的行为吗?你知道我做错了什么吗?关于代码,这里是:
int main (void){
int mat, mis, h, g,
sim, i, j, m, n;
/* mat = match, mis = mismatch, h = open gap penalty, g = extend gap penalty */
string s, t;
s = malloc(1500);
t = malloc(1500);
scanf("%d %d %d %d", &mat, &mis, &h, &g);
scanf("%s", s);
scanf("%s", t);
m = strlen(s);
n = strlen(t);
int C[m][n], BS[m][n], BT[m][n];
C[0][0] = 0;
for(j = 1; j<= n; j++)
C[0][j] = -32000;
for(i = 1; i<= m; i++)
C[i][0] = -32000;
for(j = 1; j <= n; j++)
BS[0][j] = -(h + g*j);
for(i = 0; i <= m; i++)
BS[i][0] = -32000;
for(j = 0; j <= n; j++)
BT[0][j] = -32000;
for(i = 1; i <= m; i++)
BT[i][0] = -(h + g*i);
for(i = 1; i <= m; i++){
for(j = 1; j <= n; j++){
C[i][j] = align(s[i-1],t[j-1],mat,mis) + max(C[i-1][j-1],BS[i-1][j-1],BT[i-1][j-1]);
BS[i][j] = max((C[i][j-1]-(h+g)),(BS[i][j-1]-g),(BT[i][j-1])-(h+g));
BT[i][j] = max((C[i-1][j]-(h+g)),(BS[i-1][j]-(h+g)),(BT[i-1][j]-g));
}
}
printf("\n");
printf("c[m][n]: %d bs[m][n]:%d bt[m][n]: %d\n", C[m][n], BS[m][n], BT[m][n]);
sim = max(C[m][n], BS[m][n], BT[m][n]);
printf("sim: %d\n", sim);
return 0;
}