0

EDIT 2: I managed to find the solution with suffix trees Tree::Suffix perl package. Thanks to MarcoS for the trie idea. I figured out from that, that suffix trees could be used as well. The Tree::Trie perl package is implemented as hash of hashes and I guess that's the reason it slow. I tried it and then went back to Tree::Suffix. Thanks to all others for their links to different algorithms. I am already trying to write code for every algorithm mentioned here myself as a learning process

EDIT 1: I changed the title from perl string-match problem to string-match problem.

Suppose that I have two strings, say,
S1 = ACGAGGATAGTATGCCACACAATGAGTACCCGTAC
S2 = CAGTATTGCACGTTGTAAAGTTACCCAGGTACGATGACAGTGCGTGAGCATACGAGGATAGTATGCCA

I initially wanted to check for the occurrence of string S1 (with no or 1 mismatch) in S2. And I have already written the perl code for that.

Now, I would like to develop on it to

1) Search for k-mismatches of S1 in S2.
2) Search for the occurrence of a prefix (yes, prefix, not suffix), of S1 in S2. If you look at the example, the string: ACGAGGATAGTATGCCA occurs at the end of S2 which is the beginning of S1.
3) If possible, search for the prefix with k-mismatches.

The catch is that I have about 100 million such S2 strings. S1 however remains the same and is of a defined constant length for a given problem. Is there an efficient algorithm in the literature that I could use for this problem of mine?

S1 varies between 50 and 80 characters. Also, I am mostly interested in solving problem 2 at first.

Thank you very much.

Arun
  • 116,683
  • 26
  • 284
  • 387
  • I can't believe it would be efficient to write that in perl unless you can find a native module to implement the k-mismatch algorithm. – Alnitak Sep 26 '11 at 13:34
  • 2
    Could a [Trie](http://en.wikipedia.org/wiki/Trie) be helpful for your purposes? – MarcoS Sep 26 '11 at 13:45
  • 1
    Perhaps see: http://stackoverflow.com/questions/1672782/fastest-way-to-find-mismatch-positions-between-two-strings-of-the-same-length – Joel Berger Sep 26 '11 at 15:24

2 Answers2

1

You may be able to modify the Aho-Corasick algorithm for your purposes.

Matt K
  • 13,370
  • 2
  • 32
  • 51
1

For approximate matching, have a look at http://en.wikipedia.org/wiki/Bitap_algorithm as used in agrep.

mcdowella
  • 19,301
  • 2
  • 19
  • 25