Come up with your own compression system that maps a couple consecutive DNA letters to one character. If your system uses URL-friendly characters only, there will be no need for base32. If there are only a few chars outside the legal URL range, then use URL escaping on just those, rather than puffing up the entire string.

You could use a Huffman table encoding system with fixed tables that you design based on feeding it some typical data. I think a context-aware scheme would be able to compress better, though.

How about posting the actual grammar? Maybe you'll get some concrete suggestions.

—John