java - 如何构建全局序列比对的评分矩阵？

Question

我试图获取两个字符串之间的全局序列对齐。但它给了我错误的答案。我生成评分矩阵的方法如下。

public void makeScoringMatrix(String v,String w)
{
    int ar[][]=new int[v.length()+1][w.length()+1];
    for(int i=v.length()-1;i>=0;i--)
    {
        for(int j=w.length()-1;j>=0;j--)
        {
            if(v.charAt(i)==w.charAt(j))
                ar[i][j]=ar[i+1][j+1]+1;
            else if(v.charAt(i)!=w.charAt(j))
                ar[i][j]=ar[i+1][j+1]+0;
            else
                ar[i][j]=Math.max(ar[i][j+1],Math.max(ar[i+1][j],ar[i+1][j+1]));
        }
    }
    //printArray(ar);
    getGlobalAlignment(ar,v,w);
}

public void getGlobalAlignment(int ar[][],String v,String w)
{
    int i=0,j=0,index=0;
    while(i<v.length() && j<w.length())
    {
        if(v.charAt(i)==w.charAt(j))
        {
            System.out.print(v.charAt(i));
            i++;
            j++;
            index++;

        }
        else if(ar[i+1][j]>ar[i][j+1])
        {
            i++;
        }
        else
        {
            j++;
        }
    }

}

有人请帮助我......!

Answer 1

您的评分矩阵不正确。如果打印矩阵，您将看到它如下所示:

    A  T  C  A
A [3, 0, 0, 1, 0]
G [3, 0, 0, 1, 0]
C [3, 0, 0, 1, 0]
A [3, 0, 0, 1, 0]
  [3, 0, 0, 1, 0]

问题是您将 v[i] 与每个 w[j] 进行比较，而它只应与最多 2 个相邻位置(i 和 i+1)进行比较。

您还会注意到，最后一列全是 0，而它应该是第一行，并且第一列被认为是终端值(这就是矩阵长度+1 的原因)。

最后，我相信在全局对齐的回溯过程中，您应该从矩阵中的最终位置开始向后走(因此称为术语“跟踪-后退”)。当您向前走过对齐时您比较序列中的序列相似性，而不是矩阵中的分数，我认为这是不正确的。

您应该查看有关 Needleman-Wunsch 的维基百科文章 http://en.wikipedia.org/wiki/Needleman-Wunsch_algorithm或者阅读一本算法书籍； Durbin 等人的生物序列分析是一本涵盖成对比对的经典(但很难理解)书籍。