CODEWITHSUNDEEP
recursionbioinformatics
user2918984
user2918984

Reputation: 121

A recursive code approach to the sequence alignment

I am looking for a recursive code for the sequence alignment problem. After a search I found the Needleman Wunsch algorithm, but the building of the matrix table was implemented with two for loops, other than that I could not find any recursive code that does the trick in a normal time. Any ideas for a recursive code implementation? Thanks!

Upvotes: 1

Views: 3931

Answers (2)

jtgi
jtgi

Reputation: 138

Recursive implementation with caching

Indexing gets a little messy as I use length of strings in 0-based arrays and as bound. But it is nice how closely this resembles the recurrence. Allocating stack frames in a quadratic alg is prob not a good idea however with a VM that doesn't support tail calls and a implementation that isn't tail recurse.

Running Time: O(n*m)

public static int solveWithCache(String n, String m) {
  String paddedN = " " + n; //makes some indexing easier if we pad.
  String paddedM = " " + m;

  int[][] cache = new int[paddedN.length()][paddedM.length()];

  for(int[] row : cache)
    Arrays.fill(row, Integer.MIN_VALUE);

  return solveWithCacheCompute(paddedN, paddedM, paddedN.length()-1, paddedM.length()-1, cache);
}

private static int solveWithCacheCompute(String n, String m, int i, int j, int[][] cache) {
  if(i == 0 && j == 0) return 0;
  if(cache[i][j] != Integer.MIN_VALUE) return cache[i][j];
  if(i == 0) return (j) * gapPenalty;
  if(j == 0) return (i) * gapPenalty;

  int matchScore = (n.charAt(i) == m.charAt(j)) ? matchBenefit : mismatchPenalty;

  int leaveIt = solveWithCacheHelper(n, m, i-1, j-1, cache) + matchScore;
  int addGapN = solveWithCacheHelper(n, m, i-1, j, cache) + gapPenalty;
  int addGapM = solveWithCacheHelper(n, m, i, j-1, cache) + gapPenalty;

  return Math.max(leaveIt, Math.max(addGapN, addGapM));
}

Iterative Implementation

(To easily compare) Typical DP style. Watch those indexes though; they be tricky.

public static int solve(String n, String m) {
  int nlen = n.length();
  int mlen = m.length();
  int[][] maxAlign = new int[nlen + 1][mlen + 1];

  for(int q = 0; q <= nlen; q++) 
    maxAlign[q][0] = q * gapPenalty;

  for(int r = 0; r <= mlen; r++) 
    maxAlign[0][r] = r * gapPenalty;

  for(int i = 1; i <= nlen; i++) {
    for(int j = 1; j <= mlen; j++) {
        int matchScore = (n.charAt(i-1) == m.charAt(j-1)) ? matchBenefit : mismatchPenalty;

        int leaveIt = maxAlign[i-1][j-1] + matchScore;
        int addGapN = maxAlign[i-1][j] + gapPenalty;
        int addGapM = maxAlign[i][j-1] + gapPenalty;

        maxAlign[i][j] = Math.max(leaveIt, Math.max(addGapN, addGapM));
    }
  }

  return maxAlign[nlen][mlen];
}

Upvotes: 4

mattnedrich
mattnedrich

Reputation: 8022

Why do you want a recursive algorithm?

It looks like the sequence alignment problem can be solved via dynamic programming - this is what the Needleman Wunsch algorithm is doing. From the Wikipedia page (http://en.wikipedia.org/wiki/Needleman-Wunsch_algorithm) there is a recurrence given for solving the problem. This is one recursive solution. However, this recursive solution performs the same sub-problem calculation over and over. The dynamic programming solution subverts by solving the problem bottom-up and storing computations for future look-up (memoization) via the two for loops.

Upvotes: 2

Related Questions