0

众所周知，全局序列比对问题可以使用 Needleman-Wunsch 算法解决。解决问题分为三个步骤

1. Initializing the matrix
2. Matrix filling step
3. Trace back the residues for appropriate alignment.

说清楚。

let S1={s1,s2,s3,....sm} and
    S2={x1,x2,x3,.....xn}  are the two sequences

并让评分函数为

 match=0, 
 mismatch=1 and 
 gap=2

  1. 对于初始化步骤

    1.1。创建一个 m+1 乘 n+1 的二维矩阵，即 M[m+1][n+1]

    1.2. 将第一行和第一列初始化为
    M[0][j]=M[0][j-1]+ gap 和

    M[i][0]=M[i-1][0]+间隙

2.对于矩阵填充步骤，只有当M[i-1][j-1]、M[i-1][j]和M[i][j]时，才能开始计算M[i][j] -1] 获得它们的值，并且可以使用以下方法计算这些值：

M[i][j]=Max(Diagonal,left , Up)  where 

Diagonal = M[i - 1][j - 1] + similar(S1, S2)
Left = M[i][j - 1] + gap
Up = M[i - 1][j] + gap*  and
similar(S1, S2)=0 where S1(i)=S2(j) else similar(S1, S2)=1

要使用串行方法实现，我们可以使用以下代码填充矩阵以进行第二步

fillMatrix() { 
        for (int i = 1; i <= m; i++) {
          for (int j = 1; j <= n; j++) {
            int Diagonal = M[i - 1][j - 1] + similar(S1, S2);
            int Left = M[i][j - 1] + gap; 
            int Up = M[i - 1][j] + gap; 
            M[i][j] = Max(Diagonal, Left), Up);
         }
      }
   }

并行实现（使用 OpenMP 或 Pthreads）。

对于并行实现，由于数据依赖性，垂直或水平数据分解是不可行的。在计算该矩阵元素之前，需要计算所有北、西和西北邻域。因此，可以按照反对角线的顺序依次进行分数矩阵的计算，如附图反对角矩阵所示。我的问题是，如何提取无方阵的反对角元素，不包括第一列和第一行的值，如图所示反对角元素任何可以帮助我的人？

4

0 回答 0