Read the discussion on k-nucleotide benchmark in debian shootout (http://groups.google.com/group/comp.lang.lisp/msg/d50c86053c9000b7) and decided to play with it a little: to use as hash-table keys numbers in base 4 instead of gene strings. That gave a speed gain of around 30%: http://shootout.alioth.debian.org/u32q/benchmark.php?test=knucleotide&lang=sbcl&id=3.
But still 12 times slower, than the C++ variant. Perhaps native strings (instead of full unicode) would have given 2-2.5 times additional speedup. But what else can be improved?