Fast string kernels using inexact matching for protein sequences

Christina Leslie, Rui Kuang

Research output: Contribution to journalArticlepeer-review

127 Scopus citations


We describe several families of k-mer based string kernels related to the recently presented mismatch kernel and designed for use with support vector machines (SVMs) for classification of protein sequence data. These new kernels - restricted gappy kernels, substitution kernels, and wildcard kernels - are based on feature spaces indexed by k-length subsequences ("k-mers") from the string alphabet Σ. However, for all kernels we define here, the kernel value K(x,y) can be computed in O(cK(|x| + |y|)) time, where the constant cK depends on the parameters of the kernel but is independent of the size |Σ| of the alphabet. Thus the computation of these kernels is linear in the length of the sequences, like the mismatch kernel, but we improve upon the parameter-dependent constant cK = km+1|Σ|m of the (k,m)-mismatch kernel. We compute the kernels efficiently using a trie data structure and relate our new kernels to the recently described transducer formalism. In protein classification experiments on two benchmark SCOP data sets, we show that our new faster kernels achieve SVM classification performance comparable to the mismatch kernel and the Fisher kernel derived from profile hidden Markov models, and we investigate the dependence of the kernels on parameter choice.

Original languageEnglish (US)
Pages (from-to)1435-1455
Number of pages21
JournalJournal of Machine Learning Research
StatePublished - Nov 1 2004

Bibliographical note

Publisher Copyright:
© 2004 Christina Leslie and Rui Kuang.


  • Computational biology
  • Kernel methods
  • String kernels


Dive into the research topics of 'Fast string kernels using inexact matching for protein sequences'. Together they form a unique fingerprint.

Cite this