# Sequence Alignment of two Strings

I have some code which aligns the sequence of two strings, I am doing numbers just for my implementation.

I was wondering whether there are any performance enhancements I could make as the code itself is $O(n^2)$ which isn't ideal in terms of scalability, here's the code:

        int[] goal = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,15, 0};
int[] test = {1, 5, 9, 11, 2, 10, 0, 6, 8, 14, 15, 12, 7, 4, 3, 13};
int gap = 1;
// The penalties to apply
int substitution = 1, match = 0;

int[][] opt = new int[goal.length + 1][goal.length + 1];

// First of all, compute insertions and deletions at 1st row/column
for (int i = 1; i <= goal.length; i++) {
opt[i] = opt[i - 1] + gap;
}
for (int j = 1; j <= test.length; j++) {
opt[j] = opt[j - 1] + gap;
}

for (int i = 1; i <= goal.length; i++) {
for (int j = 1; j <= test.length; j++) {
int scoreDiag = opt[i - 1][j - 1] + (goal[i - 1] == test[j - 1] ? match : 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 <= goal.length; i++) {
for (int j = 0; j <= test.length; j++) {
System.out.print(opt[i][j] + "\t");
}
System.out.println();
}


The value that I actually need from the code is opt[goal.length][test.length]

• That looks like a variant of the Levenshtein algorithm. If so you can't reduce the n^2 time complexity but you can reduce your memory usage because you just need the previous line to compute the next. – 永劫回帰 Apr 12 '17 at 18:03
• Just need the previous line to computer the next? @永劫回帰 – user3667111 Apr 12 '17 at 18:16
• In fact, you need both the previous and the current line as can be seen here opt[i][j - 1] + gap, opt[i - 1][j] + gap, opt[i - 1][j - 1] + (goal[i - 1] == test[j - 1] ? match : substitution). You never need to go more than 1 line backward. – 永劫回帰 Apr 12 '17 at 18:31

One general way to speed up dynamic algorithms is the "Method of Four Russians" - $O(\frac{n^2}{\log n})$. But to implement this method you should use limited alphabet (not like numbers in your implementation).
Although theoretically this method looks awesome, practically the size of a lookup table is growing fast ($O(3^{2t} \cdot \left|A \right| \cdot t)$, where $\left|A \right|$ is the size of an alphabet, and $t$ is a block size). For example, in the case of DNA (4 letters alphabet) it can fit to the modern cash memory just in the case of $t$ equals to 3 ($\sim0.1MB$) or 4 ($\sim10MB$).