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

Source: [GaKCo: a Fast GApped k-mer string Kernel using COunting](<https://www.sota2.com/research/paper/68fa63a61e209131cea00135>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T20:46:17.527Z

Authors: Ritambhara Singh, Arshdeep Sekhon, Kamran Kowsari, Jack Lanchantin, Beilun Wang, Yanjun Qi

Published: 2017-04-24T21:43:21.000Z

## Abstract

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(\\Sigma^{M})$. We propose a \\textbf{fast} algorithm for calculating \\underline{Ga}pped $k$-mer \\underline{K}ernel using \\underline{Co}unting (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 $\\Sigma^{M}$ 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 \\url{https://github.com/QData/GaKCo-SVM}

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [Sequence Classification on Breast Cancer dataset](<https://www.sota2.com/research/sota/sequence-classification-on-breast-cancer-dataset.md>): Sequence Classification; Breast Cancer dataset; Accuracy: 27.6.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/1704.07468>)

[PDF](<https://arxiv.org/pdf/1704.07468.pdf>)