5
\$\begingroup\$

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][0] = opt[i - 1][0] + gap;
        }
        for (int j = 1; j <= test.length; j++) {
            opt[0][j] = opt[0][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]

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – 永劫回帰 Apr 12 '17 at 18:03
  • \$\begingroup\$ Just need the previous line to computer the next? @永劫回帰 \$\endgroup\$ – user3667111 Apr 12 '17 at 18:16
  • \$\begingroup\$ 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. \$\endgroup\$ – 永劫回帰 Apr 12 '17 at 18:31
3
\$\begingroup\$

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\$).

Another way to optimize the pairwise alignment is to take advantage of an extended instruction set of modern CPUs (SIMD extension). Up to now there are several such implementations of the Smith-Waterman algorithm (1 or 2).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.