A recent technical report introduces a class of kernels for sequences. The kernels are based on pair hidden Markov models, and can potentially enable linear statistical techniques to be naturally applied to biological sequences.
Interested people should also read a recent technical report "Convolutions on Discrete Structures" by David Haussler, which is independent of my work, and which contains a very extensive discussion of kernels for discrete objects.