global sequence alignment dynamic programming finding the minimum in a matrix

Viewed 9273

I have 2 sequences, AACAGTTACC and TAAGGTCA, and I'm trying to find a global sequence alignment. I managed to create a 2D array and create the matrix, and I even filled it with semi-dynamic approach.

Here is my code to fill the matrix:

void process() {
    for (int i = 1; i <= sequenceA.length; i++) {
        for (int j = 1; j <= sequenceB.length; j++) {
            int scoreDiag = opt[i-1][j-1] + equal(i, j);
            int scoreLeft = opt[i][j-1] - 1;
            int scoreUp = opt[i-1][j] - 1;
            opt[i][j] = Math.max(Math.max(scoreDiag, scoreLeft), scoreUp);
        }
    }
}

private int equal(int i, int j) {
    if (sequenceA[i - 1] == sequenceB[j - 1]) {
        return 1;
    } else {
        return -1;
    }
}

My main problem is that this code generates this output:

 0   -1   -2   -3   -4   -5   -6   -7   -8     
-1   -1    0   -1   -2   -3   -4   -5   -6      
-2   -2    0    1    0   -1   -2   -3   -4     
 -3   -3   -1    0    0   -1   -2   -1   -2      
 -4   -4   -2    0   -1   -1   -2   -2    0      
 -5   -5   -3   -1    1    0   -1   -2   -1       
-6   -4   -4   -2    0    0    1    0   -1      
-7   -5   -5   -3   -1   -1    1    0   -1       
-8   -6   -4   -4   -2   -2    0    0    1      
 -9   -7   -5   -5   -3   -3   -1    1    0      
-10   -8   -6   -6   -4   -4   -2    0    0 

But I want it to look like this (all i care are numbers in the pictures):

enter image description here

I got to apply penaltys: per mismatch 1 and per gap 2, if its match 0.

2 Answers
Related