# GaKCo: a Fast GApped k-mer string Kernel using COunting

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Apr 2017.

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

- [Reads2Vec: Efficient Embedding of Raw High-Throughput Sequencing Reads Data](https://mlsanity.com/paper/2211.08267/) (2022)
- [T Cell Receptor Protein Sequences and Sparse Coding: A Novel Approach to Cancer Classification](https://mlsanity.com/paper/2304.13145/) (2023)
- [Anderson Acceleration For Bioinformatics-Based Machine Learning](https://mlsanity.com/paper/2302.00347/) (2023)
- [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)
- [Position Specific Scoring Is All You Need? Revisiting Protein Sequence Classification Tasks](https://mlsanity.com/paper/2410.12655/) (2024)
- [MIK: Modified Isolation Kernel for Biological Sequence Visualization, Classification, and Clustering](https://mlsanity.com/paper/2410.15688/) (2024)
- [Beyond Accuracy: Measuring Representation Capacity of Embeddings to Preserve Structural and Contextual Information](https://mlsanity.com/paper/2309.11294/) (2023)
- [Sequence-to-Image Transformation for Sequence Classification Using Rips Complex Construction and Chaos Game Representation](https://mlsanity.com/paper/2512.10141/) (2025)
- [When do cheap embeddings beat protein language models? A theoretically-grounded hashing sketch for biological sequence classification](https://mlsanity.com/paper/2512.10147/) (2025)

## Abstract (arXiv)

String Kernel (SK) techniques, especially those using gapped k-mers as features (gk), have obtained great success in classifying sequences like DNA, protein, and text. However, the state-of-the-art gk-SK runs extremely slow when we increase the dictionary size (Sigma) or allow more mismatches (M). This is because current gk-SK uses a trie-based algorithm to calculate co-occurrence of mismatched substrings resulting in a time cost proportional to O(SigmaM). We propose a fast algorithm for calculating underlineGapped k-mer underlineKernel using underlineCounting (GaKCo). GaKCo uses associative arrays to calculate the co-occurrence of substrings using cumulative counting. This algorithm is fast, scalable to larger Sigma and M, and naturally parallelizable. We provide a rigorous asymptotic analysis that compares GaKCo with the state-of-the-art gk-SK. Theoretically, the time cost of GaKCo is independent of the SigmaM term that slows down the trie-based approach. Experimentally, we observe that GaKCo achieves the same accuracy as the state-of-the-art and outperforms its speed by factors of 2, 100, and 4, on classifying sequences of DNA (5 datasets), protein (12 datasets), and character-based English text (2 datasets), respectively. GaKCo is shared as an open source tool at urlhttps://github.com/QData/GaKCo-SVM