javadynamic-programmingbioinformaticsbiometrics

How to build the scoring matrix for global sequence alignment?


I have tried to get the global sequence alignment between two strings. But it gives me the wrong answer. My way of generating the scoring matrix as below.

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

}

Someone please help me...!


Solution

  • Try this code...

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

    Hope this is the code you are looking for...