3

アフィン ギャップ ペナルティ関数を使用して 2 つのシーケンス間のグローバル アラインメントを行うプログラムを作成する必要があります。動的アルゴリズム (変更された Needleman Wunsch) は、指定された 2 つのシーケンスsとtの類似度 (シーケンスがどの程度類似しているかを表す最大スコア) を計算します。また、3 つの 2 次元配列を構築することにより、ギャップ、つまり連続するスペースのブロックが考慮されます。これは、孤立したスペースよりも発生する可能性が高くなります。配列は次のように形式的には記述できません。

配列 C:シーケンスtの文字と整列されたシーケンスs の文字で終わるブロックの最大スコアを保持します。配列 BS:シーケンスs内のスペースと整列されたシーケンスtの文字で終わるブロックの最大スコアを保持します

配列 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;
}
4

1 に答える 1

2

わかりました、デバッガの使い方がわからないので、多くのprintfsを試した後、ようやく問題を見つけました。
最初の手がかりは、ファイルから (比較的長い) シーケンスを読み込もうとしたときに gcc が教えてくれたセグメンテーション違反でした。確かにセグメンテーション違反にはいくつかの原因が考えられますが、プログラムでこのエラーが発生するほとんどの場合、実際には配列に存在しない位置にアクセスしようとしていたために発生していました。
その後、多くの printfs が初期化ステップでいくつかの値を示しました。これは、各配列の最初の行と最初の列が持つべき値とは異なります。セグメンテーション違反を初期化ステップからの奇妙な値に関連付け、配列の宣言ステップとすべてのループ条件をチェックすることにしました。ありました！配列の非常に基本的な機能を単純に忘れていました。配列のサイズがnの場合、ゼロからn-1までアクセスできます。
私の非常に初心者のエラーを解決するために、各配列の行と列に 1 つの位置を追加して (位置 (0,0) は整列された文字のペアに関連付けられていないため)、各配列のサイズが[m][n]になるようにしました。ここで、mはシーケンスs の(長さ + 1) です。、nはシーケンスtの (長さ + 1) です。さらに、 [m-1][n-1] の位置までアクセスするようにループ条件をすべて変更しました。これで、プログラムは正常に動作します。

于 2013-05-09T22:28:27.560 に答える