# Efficient Approximation Algorithms for String Kernel Based Sequence Classification

arXiv: https://arxiv.org/abs/1712.04264 · HTML: https://mlsanity.com/paper/1712.04264/

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Dec 2017.

## Built on by (most cited first, 20 of 20)

- [Spike2Vec: An Efficient and Scalable Embedding Approach for COVID-19 Spike Sequences](https://mlsanity.com/paper/2109.05019/) (2021)
- [A k-mer Based Approach for SARS-CoV-2 Variant Identification](https://mlsanity.com/paper/2108.03465/) (2021)
- [Determinantal Beam Search](https://mlsanity.com/paper/2106.07400/) (2021)
- [Efficient Approximate Kernel Based Spike Sequence Classification](https://mlsanity.com/paper/2209.04952/) (2022)
- [Effective and scalable clustering of SARS-CoV-2 sequences](https://mlsanity.com/paper/2108.08143/) (2021)
- [Robust Representation and Efficient Feature Selection Allows for Effective Clustering of SARS-CoV-2 Variants](https://mlsanity.com/paper/2110.09622/) (2021)
- [Benchmarking Machine Learning Robustness in Covid-19 Genome Sequence Classification](https://mlsanity.com/paper/2207.08898/) (2022)
- [Computing Graph Descriptors on Edge Streams](https://mlsanity.com/paper/2109.01494/) (2021)
- [Efficient Classification of SARS-CoV-2 Spike Sequences Using Federated Learning](https://mlsanity.com/paper/2302.08688/) (2023)
- [T Cell Receptor Protein Sequences and Sparse Coding: A Novel Approach to Cancer Classification](https://mlsanity.com/paper/2304.13145/) (2023)
- [Characterizing SARS-CoV-2 Spike Sequences Based on Geographical Location](https://mlsanity.com/paper/2110.00809/) (2021)
- [DANCE: Deep Learning-Assisted Analysis of Protein Sequences Using Chaos Enhanced Kaleidoscopic Images](https://mlsanity.com/paper/2409.06694/) (2024)
- [Information We Can Extract About a User From 'One Minute Mobile Application Usage'](https://mlsanity.com/paper/2207.13222/) (2022)
- [BioSequence2Vec: Efficient Embedding Generation For Biological Sequences](https://mlsanity.com/paper/2304.00291/) (2023)
- [PCD2Vec: A Poisson Correction Distance-Based Approach for Viral Host Classification](https://mlsanity.com/paper/2304.06731/) (2023)
- [Virus2Vec: Viral Sequence Classification Using Machine Learning](https://mlsanity.com/paper/2304.12328/) (2023)
- [Sequence Analysis Using the Bezier Curve](https://mlsanity.com/paper/2503.14574/) (2025)
- [Sequence-Based Nanobody-Antigen Binding Prediction](https://mlsanity.com/paper/2308.01920/) (2023)
- [Beyond Accuracy: Measuring Representation Capacity of Embeddings to Preserve Structural and Contextual Information](https://mlsanity.com/paper/2309.11294/) (2023)
- [Single-Layer MeMo as a Randomized Hamming-Kernel Classifier](https://mlsanity.com/paper/2609.34562/) (2026)

## Abstract (arXiv)

Sequence classification algorithms, such as SVM, require a definition of distance (similarity) measure between two sequences. A commonly used notion of similarity is the number of matches between k-mers (k-length subsequences) in the two sequences. Extending this definition, by considering two k-mers to match if their distance is at most m, yields better classification performance. This, however, makes the problem computationally much more complex. Known algorithms to compute this similarity have computational complexity that render them applicable only for small values of k and m. In this work, we develop novel techniques to efficiently and accurately estimate the pairwise similarity score, which enables us to use much larger values of k and m, and get higher predictive accuracy. This opens up a broad avenue of applying this classification approach to audio, images, and text sequences. Our algorithm achieves excellent approximation performance with theoretical guarantees. In the process we solve an open combinatorial problem, which was posed as a major hindrance to the scalability of existing solutions. We give analytical bounds on quality and runtime of our algorithm and report its empirical performance on real world biological and music sequences datasets.