This wasn't a bio problem, but... could someone that knows bioperl/DNA sequencing comment on the possibility of this methodology?

1. Chop up the long binary string into substrings
2. Encode the bytes as DNA base pairs
3. Use existing alignment implementations for DNA sequences

You'd probably want to do that with different size substrings, of course. (And yeah, this would be using a screwdriver as a saw, or something.)