There are several things that you need to modify:
- Note that in the image you give us the alignment goes from the bottom-right corner to the top-left corner. So in that image they are not really aligning
AACAGTTACC
andTAAGGTCA
, butCCATTGACAA
andACTGGAAT
. - You say that you want a global alignment, but you actually compute a local alignment. The main difference is in penalties at the beginning of the sequences. In a global alignment you have to compute insertions and deletions at the first row and columns.
- Third, you are not applying correctly the penalties you mention. Instead, you always penalize with -1 and reward with +1.
- In the example image they are not taking the maximum value at each position, but the minimum (this is because your penalties are positive and the rewards is 0, not the other way around, so you want to minimize the values).
The full solution is:
// Note that these sequences are reversed!
String sequenceA ="CCATTGACAA";
String sequenceB = "ACTGGAAT";
// The penalties to apply
int gap = 2, substitution = 1, match = 0;
int[][] opt = new int[sequenceA.length() + 1][sequenceB.length() + 1];
// First of all, compute insertions and deletions at 1st row/column
for (int i = 1; i <= sequenceA.length(); i++)
opt[i][0] = opt[i - 1][0] + gap;
for (int j = 1; j <= sequenceB.length(); j++)
opt[0][j] = opt[0][j - 1] + gap;
for (int i = 1; i <= sequenceA.length(); i++) {
for (int j = 1; j <= sequenceB.length(); j++) {
int scoreDiag = opt[i - 1][j - 1] +
(sequenceA.charAt(i-1) == sequenceB.charAt(j-1) ?
match : // same symbol
substitution); // different symbol
int scoreLeft = opt[i][j - 1] + gap; // insertion
int scoreUp = opt[i - 1][j] + gap; // deletion
// we take the minimum
opt[i][j] = Math.min(Math.min(scoreDiag, scoreLeft), scoreUp);
}
}
for (int i = 0; i <= sequenceA.length(); i++) {
for (int j = 0; j <= sequenceB.length(); j++)
System.out.print(opt[i][j] + "\t");
System.out.println();
}
The result is just as in the example you gave us (but reversed, remember!):
0 2 4 6 8 10 12 14 16
2 1 2 4 6 8 10 12 14
4 3 1 3 5 7 9 11 13
6 4 3 2 4 6 7 9 11
8 6 5 3 3 5 7 8 9
10 8 7 5 4 4 6 8 8
12 10 9 7 5 4 5 7 9
14 12 11 9 7 6 4 5 7
16 14 12 11 9 8 6 5 6
18 16 14 13 11 10 8 6 6
20 18 16 15 13 12 10 8 7
So the final alignment score is found at opt[sequenceA.length()][sequenceB.length()]
(7). If you really need to show the reversed matrix as in the image, do this:
for (int i = sequenceA.length(); i >=0; i--) {
for (int j = sequenceB.length(); j >= 0 ; j--)
System.out.print(opt[i][j] + "\t");
System.out.println();
}