<p>I have a large number of short patterns (5-10 &quot;letters&quot; or amino acids in this context). I want to search for these in a large database of &quot;texts&quot; (proteins). Are there any existing packages which provide efficient algorithms for this? Ideally they would be</p>

<ul>
	<li>Handle 140k patterns and 280k texts</li>
	<li>Able to handle ambiguous residues such as &#39;J&#39; for [IL] (this can be faked by duplicating some patterns)</li>
	<li>python is preferred (I&#39;m already using BioPython, but it is missing this afaik)</li>
</ul>

<p>I&#39;m currently using a naive O(n^2) search, but it&#39;s taking too long. I think this problem is generally solved using keyword trees (Aho-Corasick algorithm), but I&#39;d rather not implement that myself unless I have to.</p>

<p><em>Update</em></p>

<p>I should have specified that for output I need both the text and the pattern which matched it. This prevents some of the otherwise great implementations (eg fgrep, ahocorasick) from solving my problem.</p>

I ended up using the <a href="http://code.google.com/p/esmre/">esmre</a> library, as suggested by <a href="https://www.biostars.org/u/6141/">dariober</a> in the comments. It dropped my run time from hours (with a brute force search) to seconds.

Full code is on <a href="https://github.com/sbliven/proteinsearch">github</a>, but the important parts are quite simple:

    import esmre
    
    vocab = esmre.Index()
    for word in patterns:
      vocab.enter(word,word)
    for text in texts:
      matches = vocab.query(text)
      for match in matches:
        print "Match for %s in %s" % (match, text)