Approximate String Matching Interview Question

Question

I was working on the challenge Save Humanity from Interviewstreet for a while then gave up, solved a few other challenges, and have come back to it again.

The code below generates the correct answers but the time complexity O(text * pattern) is not sufficient for the auto-grader. Could anyone perhaps give me a hint or a pointer on how to improve my algorithm?

final BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
final StringBuilder builder = new StringBuilder();
final int number_trials = Integer.valueOf(input.readLine());

for(int trial = 0; trial < number_trials; trial++)
{    
    final int allowed_mismatches = 1;
    final char[] text = input.readLine().toCharArray();
    final char[] pattern = input.readLine().toCharArray();        
    input.readLine();

    for(int text_index = 0; text_index < text.length - pattern.length + 1; text_index++)
    {
        int pattern_index = 0;
        int missed = 0;

        while(pattern_index < pattern.length && missed <= allowed_mismatches)
        {
            if(text[text_index + pattern_index] != pattern[pattern_index])
            {
                missed++;
            }

            pattern_index++;
        }

        if(missed <= allowed_mismatches)
        {
            builder.append(text_index);
            builder.append(" ");
        }
    }

    if(builder.length() > 0 && builder.charAt(builder.length() - 1) == ' ')
    {
        builder.deleteCharAt(builder.length() - 1);
    }           

    if(trial + 1 < number_trials)
    {
        builder.append("\n");
    }       
}

System.out.println(builder.toString());

Answer 1

This is a common problem in bioinformatics. There are in general three different approaches to the problem

1. Inexact string search via dynamic programming
2. Inexact string search via text search
3. Filtering

The filtering isn’t strictly speaking solving the problem – rather, it’s eliminating most of those regions in the string which are irrelevant. Still, it’s the most promising area: In modern-day sequencing projects, this is the go-to method, but it only makes sense if you search for lots of small strings, since you first need to create an index for the large string (the “reference”).

Still, a brief overview.

All the methods described in the following are implemented in the SeqAn library for C++. Unfortunately, the code uses some very special idioms to to implement highly efficient algorithms in a generic fashion but it’s still the best reference implementation that I know of.

The first method uses a dynamic programming local alignment algorithm (think Smith-Waterman), with one modification: for each column that we calculate, we stop once we find the second error (in your case; in general, we allow k errors and stop after we find k + 1).

Even though dynamic programming has a prohibitive O(n * m) complexity, this trick (called the “Ukkonen trick”) pushes runtime down to O(n * k) which, in your case, is linear. Combined with an efficient implementation of the dynamic programming table (Myers bit vector algorithm), this was fast enough to assemble reads at Celera during the Human Genome Project. There are some lecture notes which can serve as a basis for the implementation.

Caveat: this is pretty tricky, especially if you want to understand the correctness proof of the bit vector algorithm.

But actually, since you only allow mismatches instead of gaps this is overkill – it’s effectively the same as your method, albeit with a more efficient implementation.

The second approach uses modified exact string search, see cat_baxter’s answer for two excellent implementations. In particular, a modification of the suffix tree version (using a trie with backlinks due to Aho and Corasick) was used in some versions of the sequence search tool BLAST.

The third approach can be split again; I’m going to focus on two variants:

• pigeonhole-based search. In your case, that’s incredibly easy: since you only allow one error, you can just split each potential hit location into two; now you know that one of those must match exactly – otherwise there’d be at least two errors in the match.

  So you can just move a sliding window over the string and use an exact search algorithm to compare regions of the size m/2 against both halves of your pattern (of length m). This can be done very efficiently if you have an index for the reference string.

• Alternatively, you can harness the q-gram lemma which tells you that (in your case), the pattern has t common q-grams with each equal-length match in the reference, where t = m - 2 q + 1. If you choose your q appropriately, you can build a collision-free hash table for all q-grams in the reference, and look up all matching positions in O(1).

Answer 2

1.I would use something like "APPROXIMATE BOYER-MOORE STRING MATCHING" described here:

http://www.cs.hut.fi/~tarhio/papers/abm.pdf

2.The second option is the Suffix Tree Solution:

http://homepage.usask.ca/~ctl271/810/approximate_matching.shtml

The Suffix Tree approach to the k-mismatch problem is essentially the same as the approach taken when matching with wild-cards; though in this case k is the number of allowable mismatches rather than the number of wildcards. The algorithm proceeds by executing up to k constant-time lce queries for each position i in the text. If the the lce queries span the end of P, then P occurs starting at position i of the text.

for i = 1; i < m-n+1; i++
  1. j = 1, i′ = i, count = 0
  2. l = lce (P[j], T[i′])
  3. if j+l = n+1, P occurs in T at i with only count mismatches; continue next i;
  4. if count ≤ k, count++, j = j+l+1, i′=i′+l+1, go to 2
  5. if count = k+1, then a k mismatch of P does not occur at i; continue next i;

An alternate approach, when both k and the alphabet size are relatively small is to generate all permutations of P with up to k changes and then search for each of these permutations in the tree. This would run in time O(P′ + m), where P′ is the combined length of the permissible permutations of P.

Answer 3

Just litteral enhancements :

final int allowed_mismatches = 1; // outside the for

// evaluate at the beginning
for(int text_index = 0, n = text.length - pattern.length + 1; text_index < n ; text_index++)

final int patternLength = pattern.length ; // as soon as possible, and replace it as needed 

if(builder.length() > 0) ;// ' ' ends obviously builder.charAt(builder.length() - 1) == ' ')