title: Working with suffix trees in python
body: <p>I'm relatively new to python and am starting to work with suffix trees.  I can build them, but I'm running into a memory issue when the string gets large.  I know that they can be used to work with DNA strings of size 4^10 or 4^12, but whenever I try to implement a method, I end up with a memory issue.  </p>
  
  <p>Here is my code for generating the string and the suffix tree.</p>
  
  <pre><code>import random
  
  def get_string(length):
      string=""
      for i in range(length):
          string += random.choice("ATGC")
      return string
  
  word=get_string(4**4)+"$"
  
  def suffixtree(string):
      for i in xrange(len(string)):
          if tree.has_key(string[i]):
              tree[string[i]].append([string[i+1:]][0])
          else:
              tree[string[i]]=[string[i+1:]]
      return tree
  
  tree={}
  suffixtree(word)
  </code></pre>
  
  <p>When I get up to around 4**8, I run into severe memory problems.  I'm rather new to this so I'm sure I'm missing something with storing these things.  Any advice would be greatly appreciated.  </p>
  
  <p>As a note:  I want to do string searching to look for matching strings in a very large string.  The search string match size is 16.  So, this would look for a string of size 16 within a large string, and then move onto the next string and perform another search.  Since I'll be doing a very large number of searches, a suffix tree was suggested.</p>
  
  <p>Many thanks</p>