The Spectrum Kernel: A String Kernel for SVM Protein Classification

By Christina S. Leslie, Eleazar Eskin, William Stafford Noble. 2001

1,176 citations recorded by the source corpus.

We introduce a new sequence-similarity kernel, the spectrum kernel, for use with support vector machines (SVMs) in a discriminative approach to the protein classification problem. Our kernel is conceptually simple and efficient to compute and, in experiments on the SCOP database, performs well in comparison with state-of-the-art methods for homology detection. Moreover, our method produces an SVM classifier that allows linear time classification of test sequences. Our experiments provide evidence that string-based kernels, in conjunction with SVMs, could offer a viable and computationally efficient alternative to other methods of protein classification and homology detection.

Subfields: Molecular Biology, Statistical Learning Theory, Computational Biology & Bioinformatics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Molecular Biology

In Statistical Learning Theory

In Computational Biology & Bioinformatics

Citations in the corpus

Discriminative Embeddings of Latent Variable Models for Structured Data (2016, neutral): “We compare our algorithm on string benchmark datasets with the kernel method with existing sequence kernels, i.e., the spectrum string kernel (Leslie et al., 2002a), mismatch string kernel (Leslie et al., 2002b) and fisher kernel with HMM generative models (Jaakkola & Haussler, 1999).”
Security analysis of online centroid anomaly detection (2010, methodology): “As byte sequences are not directly suitable for application of machine learning algorithms, we deploy a k-gram spectrum kernel (Leslie et al., 2002; Shawe-Taylor and Cristianini, 2004) for the computation of the inner products.”
MRFalign: Protein Homology Detection through Alignment of Markov Random Fields (2014, methodology): “Improvement in these alignment-free methods results from the application of discriminative learning approaches such as SVM– Fisher [26], SVM-pairwise [27], SVM with the spectrum kernel [28] and SVM with the mismatch kernel [29].”
Continuous Distributed Representation of Biological Sequences for Deep Proteomics and Genomics (2015, neutral): “Protein family classification based on the primary structures (sequences) has been performed using classifiers such as support vector machine (SVM) [16, 17, 18].”
Biological Sequence Modeling with Convolutional Kernel Networks (2017, neutral): “String kernels, see, e.g., Leslie et al. [2002, 2004], Saigo et al. [2004], Rangwala and Karypis [2005], have shown state-of-the-art prediction performance but are computationally expensive, which restricts their use to small-scale datasets.”
Predicting linear B-cell epitopes using string kernels (2008, positive): “…1999; Lodhi et al ., 2002; Leslie et al ., 2002, 2004; Saigo et al ., 2004) are a class of kernel methods that have been successfully used in many sequence classification tasks (Leslie et al ., 2002, 2004; Saigo et al ., 2004; Zaki et al ., 2005; Rangwala et al ., 2006; Wu et al ., 2006).”
A comprehensive review and comparison of different computational methods for protein remote homology detection (2018, background): “Spectrum kernel [70] is a string kernel, whose”
Kernel-Based Learning of Hierarchical Multilabel Classification Models (2006, methodology): “|)) time, to compute substring spectrum kernels are based on suffix trees (Leslie et al., 2002; Vishwanathan and Smola, 2002), although dynamic programming and approaches based on thetrie data structure also can be used ShaweTaylor and Cristianini (2004).”
Detecting Unknown Network Attacks Using Language Models (2006, methodology): “Recent approaches to text categorization advocate the use of kernel functions as similarity measures, which allows one to incorporate contextual information (45; 46; 39).”
Kernels for small molecules and the prediction of mutagenicity, toxicity and anti-cancer activity (2005, methodology): “However, using a suffix tree data structure (Ukkonen, 1995; Weiner, 1973; as also proposed in Leslie et al., 2002; Vishwanathan and Smola, 2003) allows us to compute each of the proposed kernels in time O(d(n1m1+n2m2)), where d is the depth of the search and ni (resp.”
SeqGL Identifies Context-Dependent Binding Signals in Genome-Wide Regulatory Element Maps (2015, methodology): “The first k-mer based string kernels were introduced shortly afterwards [37, 38] for the problem of SVM classification of protein domains and used the same retrieval tree Fig 7.”
APCluster: an R package for affinity propagation clustering (2011, methodology): “In order to compute a similarity matrix for this data set, we choose (without further justification, just for demonstration purposes) the simple spectrum kernel [8] with a sub-sequence length of k = 6.”
Classification of small molecules by two- and three-dimensional decomposition kernels (2007, background): “Common examples of 'all-substructures kernels' are the spectrum kernel for strings (Leslie et al., 2002), the kernel defined by Collins and Duffy (2002) for trees and the cyclic pattern kernel for molecules (Horva´th et al., 2004).”
A brief survey on sequence classification (2010, methodology): “Leslie et al. [35] propose a k - spectrum kernel for protein classiﬁcation.”