Fast kernels for inexact string matching

Christina Leslie, Rui Kuang

Research output: Contribution to journalConference articlepeer-review

32 Scopus citations


We introduce several new families of string kernels designed in particular for use with support vector machines (SVMs) for classification of protein sequence data. These kernels - restricted gappy kernels, substitution kernels, and wildcard kernels - are based on feature spaces indexed by k-length subsequences from the string alphabet σ (or the alphabet augmented by a wildcard character), and hence they are related to the recently presented (k, m)-mismatch kernel and string kernels used in text classification. However, for all kernels we define here, the kernel value K(x, y) can be computed in O(CκK(|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 mismatch kernel. We compute the kernels efficiently using a recursive function based on a trie data structure and relate our new kernels to the recently described transducer formalism. Finally, we report protein classification experiments on a benchmark SCOP dataset, where 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.

Original languageEnglish (US)
Pages (from-to)114-128
Number of pages15
JournalLecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science)
StatePublished - 2003
Event16th Annual Conference on Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003 - Washington, DC, United States
Duration: Aug 24 2003Aug 27 2003


  • Computational biology
  • Kernel methods
  • String kernels


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

Cite this