Как построить оценочную матрицу для глобального выравнивания последовательностей?

Я попытался получить глобальное выравнивание последовательности между двумя строками. Но это дает мне неправильный ответ. Мой способ генерации оценочной матрицы приведен ниже.

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++;
        }
    }

}

Кто-нибудь, пожалуйста, помогите мне...!

Источник

2 ответа

Решение

Попробуйте этот код...

public void makeMatrix(String v,String w)
{
    int[][] maxDist=new int[v.length()+1][w.length()+1];
    for(int i=0;i<=v.length();i++)
    {
        for(int j=0;j<=w.length();j++)
        {
            if(i==0)
                maxDist[i][j]=-j;
            else if(j==0)
                maxDist[i][j]=-i;
            else
                maxDist[i][j]=0;
        }
    }
    fillMatrix(maxDist, v, w);
}

public int weight(String v,String w,int i,int j)
{
    if(v.charAt(i-1)==w.charAt(j-1))
        return 1;
    else
        return -1;
}

public void fillMatrix(int[][] ar,String v,String w)
{
    for(int i=1;i<=v.length();i++)
    {
        for(int j=1;j<=w.length();j++)
        {
            int scoreDiagonal=ar[i-1][j-1]+weight(v, w, i, j);
            int scoreLeft=ar[i][j-1]-1;
            int scoreUp=ar[i-1][j]-1;

            ar[i][j]=Math.max(scoreDiagonal, Math.max(scoreLeft, scoreUp));
        }
    }
}

Надеюсь, это код, который вы ищете...

Источник

Ваша матрица оценок неверна. Если вы напечатаете матрицу, вы увидите, что она выглядит так:

    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 или прочитать одну из книг по алгоритмам; Анализ биологической последовательности Дурбина и др. - это классическая (но очень трудная для понимания) книга, в которой рассматриваются парные выравнивания.

Источник
Другие вопросы по тегам