This is not my field, but ...

                                    \ | /
   <<<    <<<    <<<    <<<    <<< -- O --
                                    / | \
  """""\ 
 """===(° 
"(O)"    \
 \u     =¯
  |  \__)
[download]

That was your whole second paragraph going right over my head. T'ain't mine ivver! :)

However, you're right that the bio guys do this sort of fuzzy comparison a lot--a lot a lot. And they frequently exhaustively cross compare huge volumes of very large strings. I was involved in a whole other thread here aimed at finding the fastest way to do exactly that in Perl.

So, encoding 4 RAs per char and saving 75% memory and 75% of comparison time would be a huge saver--if you can get the encoding data/decoding results costs down.

Maybe using C, but vec is just too slow, as you have to access every 2-(3-,4-)bit offset individually at the perl level. Maybe a XS/C/asm module that takes a list of numbers and a bit size and returns a fully encoded string.

However, there is still another problem that I hadn't thought about before. This works ok for two equal length strings, but more often than not, the task is to compare relatively short fragments against huge sequences to try and locate (likely) positions at which the fragment matches. In that scenario, the shorter fragment has to be tried at all offsets against the longer. That means you would need to encode each fragment 4 times, and use them cyclically against the sequence in order to test all positions.