# Hyper-k-mers: efficient streaming k-mers representation

Igor Martayan, Lucas Robidou, Yoshihiro Shibuya, Antoine Limasset

► To cite this version:

Igor Martayan, Lucas Robidou, Yoshihiro Shibuya, Antoine Limasset. Hyper-k-mers: efficient streaming k-mers representation. RECOMB 2025, Apr 2025, Seoul, South Korea. 10.1101/2024.11.06.620789. hal-05396266

HAL Id: hal-05396266

https://hal.science/hal-05396266v1

Submitted on 3 Dec 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Hyper-k-mers: efficient streaming k-mers representation

Igor Martayan¹,*, [0009-0008-3007-6168], Lucas Robidou²,*, [0009-0003-8525-8157],
Yoshihiro Shibuya³[0000-0002-3137-1504], and Antoine Limasset¹[0000-0002-0669-4141]

¹ Univ. Lille, CNRS, Centrale Lille, UMR 9189 CRISTAL, F-59000 Lille, France
igor.martayan@univ-lille.fr
antoine.limasset@univ-lille.fr

² Genome Informatics, Faculty of Technology and Center for Biotechnology, Bielefeld University, Germany
lucas.robidou@uni-bielefeld.de

³ Institut Pasteur, Paris, France
yoshihiro.shibuya@pasteur.fr

* co-first authors

**Abstract.** K-mers have become ubiquitous in modern bioinformatics pipelines. A key factor in their success is the ability to filter out erroneous k-mers by removing those with low abundances. However, large numbers of distinct k-mers make counting a memory-intensive step. Early tools addressed this issue by storing k-mers on disk. More recent solutions, mitigate the excessive redundancy of overlapping k-mers by partially reassembling them into super-k-mers. Nevertheless, consecutive super-k-mers still overlap by $k - 1$ bases, leading to some degree of inefficiency.

Here we present *hyper-k-mers* as an alternative, less redundant, representation of super-*k*-mers. Our contributions are three-fold. First, we propose hyper-*k*-mers, a new *k*-mer representation that asymptotically decreases duplication compared to super-*k*-mers. Second, we present a theoretical analysis comparing the space efficiency of super-*k*-mers, syncmers, and hyper-*k*-mers. Our approach offers significant advantages compared to super-*k*-mers, by reducing the asymptotic lower bound from 6 to 4 bits per nucleotide. Third, we present KFC, a *k*-mer counting algorithm leveraging hyper-*k*-mers. KFC offers significant practical advantages, including an order of magnitude improvement in memory usage compared to state-of-the-art tools. Notably, our experiments show that KFC is the only tool whose memory usage scales sub-linearly with *k*-mer size *k*, and is the fastest option when *k* is large.

**Availability:** KFC is available at https://github.com/lrobidou/KFC with tests available at https://github.com/imartayan/KFC_experiments

**Keywords:** hyper-*k*-mer · super-*k*-mer · *k*-mer · *k*-mer counting.
# 1 Introduction

Representing DNA sequences as sets of *k*-mers, fixed-length sub-strings of length *k*, is a simple yet highly efficient approach in sequence bioinformatics by enabling accurate estimation of sequence similarity in linear time, circumventing the need for computationally intensive alignment steps. Moreover, it naturally handles redundancy, as each unique *k*-mer is stored only once, regardless of its frequency in the DNA sequence. This property is particularly beneficial when dealing with sequencing datasets that are inherently redundant due to high coverage depths (in the order of 1000x in large sequencing datasets). Over the years, the use of *k*-mers has been extended to various applications such as genotyping [17], phylogeny reconstruction [43], and read error correction [21]. However, naive storage of *k*-mers leads to significant space overheads, potentially up to a factor of *k*, since each position in the DNA sequence can generate a *k*-mer. Additionally, sequencing errors introduce erroneous non-biologically-relevant *k*-mers. As observed by Velvet [46], for sufficiently large *k*'s, spurious *k*-mers only repeat a few times, since it is unlikely for two independent errors to produce the same *k*-mer. However, due to high coverage depths, the total number of erroneous *k*-mers can easily outnumber the true genomic *k*-mers by orders of magnitude. Therefore, filtering out infrequent *k*-mers, while retaining the highly frequent ones, has proven to be an extremely effective strategy for distinguishing true *k*-mers from errors. This observation led to one of the simplest, yet most fundamental tasks in computational biology, known as *k*-mer counting, which aims to associate *k*-mers to their occurrence counts in a dataset for filtering purposes. Despite its apparent simplicity, *k*-mer counting is quite resource-intensive, as storing large numbers of *k*-mers along with their counts is expensive in terms of both memory and time. Given their critical role in various applications, *k*-mer counting tools have historically focused on speed while limiting memory usage to practical levels. A significant milestone was achieved with Jellyfish [26], which implements a mutex-free hash table for high-throughput parallelism, achieving counting speeds akin to simple file reading. Alternative approaches have utilized more efficient data structures for counting, such as counting quotient filters [30,29], Burst tries [22], and cuckoo hashing [45]. However, these methods still face the challenge of storing entire *k*-mers in main memory. Some tools trade results accuracy for reduced memory usage by using probabilistic data structures like Bloom filters [27,37] or quotient filters [30] to remove low abundance *k*-mers before counting. Another approach to reduce memory is to partition *k*-mers into buckets. Buckets can be safely stored on disk and independently processed thus limiting the number of *k*-mers in main memory [7,34]. Finally, some methods have attempted to accelerate *k*-mer counting by leveraging GPUs [44,13].

A significant advancement in reducing the memory footprint of *k*-mer storage was the introduction of super-*k*-mers [20,9]. Super-*k*-mers encode *N* successive *k*-mers sharing the same minimizer – the smallest sub-string of length *m* within a *k*-mer, for a given ordering [38,35,3] – into *k* + *N* − 1 nucleotides. Minimizers exhibit locality-sensitive hashing properties, functioning as a special case of MinHash with a single fingerprint, and have been widely used in *k*-mer partitioning [5,25]. With the behavior of minimizers now well understood [36], we can accurately estimate the representation cost of super-*k*-mers, leading to significant improvements in efficiency. The adoption of super-*k*-mers has mitigated the memory issues of *k*-mer counting, and super-*k*-mer-based tools such as KMC3 [18] and FASTK [28] are among the best tools of this competitive field. Recently, a new standardized format, KFF, based on super-*k*-mers, has been proposed for representing *k*-mer sets [11].

Even in the absence of errors, efficient *k*-mer representations are still required to minimize memory footprint. However, super-*k*-mers are still far from the optimal space efficiency, due to overlaps at their extremities, leading to unwanted redundancies. Over the years, multiple efficient encodings of *k*-mer sets have been proposed [4,39,40], and allowed lightweight *k*-mer based tools [6,31,14]. The common underlying principle is that redundancy can be decreased by merging overlapping *k*-mers. One of the most well-known instances of this idea is the concept of *unitigs*, which are sequences formed by non-branching paths in de Bruijn graphs [4]. Unitigs are one of the most well-known de Bruijn graph representations, with duplications only occurring near branching paths. Subsequent representation proposed to allow more merging even if they may be unsure biologically to be more succinct. Such representations are essentially static, as they are constructed once from a complete set of *k*-mers. In contrast, super-*k*-mers can be constructed on-the-fly during sequence parsing, making them a more versatile representation. Moreover, this representation is inherently partitioned, since each super-*k*-mer (and thus each *k*-mer) is associated with its minimizer, which naturally facilitates indexing [23,24,32]. A fundamental question is whether we can improve this convenient light-weight and partitioned representation to be as memory-efficient as static ones, thereby
obtaining the best of both worlds. Static representations achieve space close to the lower bound of 2 bits per nucleotide (over the four letters DNA alphabet), whereas super-k-mer representations are several times larger for commonly-used k-mer sizes ($k \approx 31$). However, for $k \to +\infty$, super-k-mer tend to 6 bits per k-mer [36]. Up until now, k-mer sizes have been quite small, due to the limited read lengths of next-generation sequencing (NGS) datasets. However, larger k-mer sizes are becoming more practical thanks to continuous improvements in the accuracy of long-read sequencing technologies, such as Oxford Nanopore Technologies (ONT), whose reads are approaching 1% error rates [41], and PacBio HiFi sequencing with error rates as small as 0.1% [1]. These advancements enable the use of very large k-mer sizes in applications like genome assembly, k-mer analysis, and pangenomics. Conversely, very large k-mer sizes degrade the performance of traditional efficient encoding methods (unitigs simplitigs, eulertigs, ...), as overlap sizes increase linearly with k. To address this challenge, we introduce the concept of hyper-k-mers as an alternative to super-k-mers, aiming to bridge the gap between dynamic and static representations. Compared to super-k-mers, hyper-k-mers-based representations are 33% lighter while displaying similar properties. We demonstrate the practical interest of our approach by implementing and testing a new k-mer counting tool called KFC based on hyper-k-mers. KFC is both the fastest and the more memory-efficient tool for large k's, being the only one being more efficient as k rises.

The rest of the paper is organized as follows. In section 2, we formally define the concepts of k-mers, minimizers, super-k-mers, hyper-k-mers, and the main goal of our work. Section 3 presents the theoretical analysis of hyper-k-mers and details the algorithm and ideas behind our tool KFC. Section 4 reports experimental results to assess KFC's performance compared to other k-mer counting tools. We conclude with discussions on possible future directions and general considerations.

## 2 Definitions and problem statement

In this section, we introduce the concepts at the basis of our exposition about hyper-k-mers in section 3. For the most part, we re-use the notation from [16] and [31], which we report here for convenience. We considered strings defined over the alphabet $\Sigma = \{A, C, G, T\}$ of size $\sigma = 4$, and we use the terms *character*, *base* and *nucleotide* interchangeably. Let $S \in \Sigma^*$ be a (genomic) string. We refer to $S[i..j]$ as the substring of length $j-i$, starting at position $i$ (included) and ending at position $j$ (excluded).

**Definition 1 (k-mer).** *k-mers are substrings* $S[i..i + k)$ *of fixed length k*.

**Definition 2 (Order).** An order $O_m$ on m-mers is a function $O_m : \sigma^m \to \mathbb{R}$, such that $x \le_{O_m} y$ if and only if $O_m(x) \le_{O_m} O_m(y)$

In practice, (pseudo-)random hash functions $h: \Sigma^m \to U$ are used to define an order [33], where $U$ is a sufficiently large universe of possible values, like $U = 2^{64}$ if using 64-bit hash functions.

**Definition 3 ((Random) minimizer).** A minimizer of a k-mer $K$ is its minimal substring of length $m < k$ for a given (random) order $O_m$.

Minimizers have been widely studied in the literature [38, 35, 16] and multiple selection methods, called *minimizer schemes*, have been proposed. The efficiency of a minimizer scheme is usually measured by its *density*.

**Definition 4 (Density of a minimizer scheme).** The density of a minimizer scheme is the expected proportion of selected minimizers over the number of m-mers in a random string.

In particular, the density of random minimizers is equal to $d = 2/(w+1)$ [38], where $w = k - m + 1$ is the window size (the number of m-mers in a k-mer). Thus, two neighboring k-mers overlapping by $k-1$ bases often share the same minimizer.

**Definition 5 (Super-k-mer).** A maximal sequence of consecutive k-mers having the same minimizer [19].

**Definition 6 (Overlap of consecutive super-k-mers).** Given two consecutive super-k-mers $u$ and $v$, we define the overlap of $u$ and $v$, denoted $\text{ov}(u, v)$, as the $k-1$ bases shared by the rightmost k-mer of $u$ and the leftmost k-mer of $v$.
A straightforward method to reduce k-mer memory consumption is to store super-k-mers instead of k-mers. Let $S$ be the set of k-mers of string $S$. Each character (base) in $S$ can be encoded using 2 bits since $\sigma = 4$. Thus, naively storing set $S$ requires $2k$ bits per nucleotide (each character in $S$ is covered by $k$ k-mers, except the extremities), whereas a super-k-mer representation only requires 6 bits per nucleotide [36]. While undoubtedly an improvement, super-k-mers space usage is still far away from the optimal achievable space of 2 bits per nucleotide of a completely (theoretical) linear representation of $S$. The remaining overhead comes from the $k-1$ bases overlaps between neighboring super-k-mers.

Our main goal is to find a representation of $S$ whose space is < 6 bits per nucleotide.

# 3 Methods

We start this section by introducing out theoretical analysis of super-k-mers and their space requirements. Next, we do the same for closed syncmers [12]. Syncmers have been shown to "pave" sequences better than other sampling techniques [12,42], with a tendency to cover more bases than, e.g. minimizer-based sampling. Despite not being suitable for representing k-mer sets, we think our theoretical results on closed syncmers are useful to put hyper-k-mer into perspective.

## 3.1 Super-k-mers

**Lemma 1 (Average number of super-k-mers).** Given a random string $S$, the expected number of super-k-mers is $(|S| - m + 1) \times d$.

*Proof.* By definition of the density $d$, the expected number of minimizers is $(|S| - m + 1) \times d$. Since each minimizer corresponds to one super-k-mer, the expected number of super-k-mers is the same.

**Lemma 2 (Average length of super-k-mers).** Given a random string $S$, the average length of a super-k-mer is $\frac{|S|-k+1}{(|S|-m+1)\times d} + k - 1$. In particular, it approaches $\frac{1}{d} + k - 1$ as $|S| \to +\infty$.

*Proof.* By Lemma 1, there are $(|S| - m + 1) \times d$ super-k-mers on average. Since there are $|S| - k + 1$ k-mers in $S$, each super-k-mer contains $\frac{|S|-k+1}{(|S|-m+1)\times d}$ k-mers on average, i.e. $\frac{|S|-k+1}{(|S|-m+1)\times d} + k - 1$ bases.

**Theorem 1 (Super-k-mer space usage).** Given a random string $S$, the expected total number of bases in the super-k-mers of $S$ is asymptotically equivalent to $|S| \cdot (1 + (k - 1) \cdot d)$ as $|S| \to +\infty$.

*Proof.* Let $S_{sk}$ denote the set of super-k-mers of $S$, $|S_{sk}|$ the number of super-k-mers in $S$ and $S_{sk}[i]$ denotes the $i$-th super-k-mer of $S$. The total number of characters in $S_{sk}$ is:

$$ 
\begin{aligned}
\sum_{i=0}^{|S_{sk}|} |S_{sk}[i]| &= |S_{sk}| \times \sum_{i=0}^{|S_{sk}|} \frac{|S_{sk}[i]|}{|S_{sk}|} \\
&= (|S| - m + 1) \times d \times \sum_{i=0}^{|S_{sk}|} \frac{|S_{sk}[i]|}{|S_{sk}|} && (\text{See Lemma 1}) \\
&= (|S| - m + 1) \times d \times \left( \frac{|S| - k + 1}{(|S| - m + 1) \times d} + k - 1 \right) && (\text{See Lemma 2}) \\
&\stackrel{|S| \to +\infty}{\sim} |S| \times d \times \left( \frac{1}{d} + k - 1 \right) \\
&= |S| \cdot (1 + (k - 1) \cdot d)
\end{aligned}
$$

In particular, for random minimizers which have a density $d = 2/(w + 1) = 2/(k - m + 2)$, the space usage of super-k-mers is asymptotically equivalent to $|S| \cdot (1 + \frac{2(k-1)}{k-m+2}) \sim 3 \cdot |S|$ for $k \gg m$.
## 3.2 Closed-syncmers

**Definition 7 (Closed syncmer).** A *k*-mer with a minimizer located at its start or its end.

**Theorem 2 (Closed syncmer space usage).** Given a random string $S$, the expected total number of bases in the closed syncmers of $S$ is asymptotically equivalent to $|S| \cdot k \cdot d$ as $|S| \to +\infty$.

*Proof.* Each *k*-mer consists of $w = k - m + 1$ *m*-mers. Let us consider the last $w + 1$ *m*-mers of a string after adding a base spawning a new minimizer. The smallest *m*-mer among these $w + 1$ is either the first (if the minimizer changed because the previous one is out of scope) or the last (if the new minimizer is smaller than the previous one). If the smallest *m*-mer is the first one, then the previous *k*-mer is a closed syncmer. Otherwise, the smallest *m*-mer is at the end of the last *k*-mer, which is thus a closed syncmer. Thus, apart from the first minimizer, each minimizer creates a closed syncmer, so there are $(|S| - m + 1) \times d$ closed syncmers, on average, in $S$. Since each closed syncmer has length *k*, the expected total number of bases is $((|S| - m + 1) \times d \times k)$, which is asymptotically equivalent to $|S| \cdot k \cdot d$ as $|S| \to +\infty$.

In particular, for random minimizers, the space usage of closed syncmers is asymptotically equivalent to $|S| \cdot \frac{2 \cdot k}{k-m+2} \sim 2 \cdot |S|$ for $k \gg m$.

## 3.3 Hyper-*k*-mers

<figure><img src="image_2.png" /><figcaption>Fig. 1: Example of minimizers, super-*k*-mers and hyper-*k*-mers for $m = 3$ and $k = 11$ using lexicographic order. In this example, the original sequence contains 40 bases and super-*k*-mers use 70 bases while hyper-*k*-mers use 50 bases.</figcaption></figure>

**Definition 8 (Hyper-*k*-mer).** Given three consecutive super-*k*-mers *u*, *v* and *w*, let $m_v$ be the minimizer of *v*. We define the hyper-*k*-mer associated to $m_v$ as $(\text{ov}(u, v), \text{ov}(v, w))$, and refer to $\text{ov}(u, v)$ as its left part and $\text{ov}(v, w)$ as its right part. By convention, if *v* has no predecessor in the sequence, we define its left part as the first $k-1$ bases and if it has no successor, we define its right part as the last $k-1$ bases.

We can already make a few observations based on this definition: every hyper-*k*-mer contains exactly $2(k-1)$ bases and given two consecutive hyper-*k*-mers *u* and *v*, the right part of *u* and the left part of *v* are identical. This means that we can effectively save $k-1$ bases for each pair of consecutive hyper-*k*-mers. Figure 1 gives an example of hyper-*k*-mers and shows that their overlapping parts can be shared.

**Theorem 3 (Hyper-*k*-mer space usage).** Given a random string $S$, the expected total number of bases in the hyper-*k*-mers of $S$ is asymptotically equivalent to $|S| \cdot (k-1) \cdot d$ as $|S| \to +\infty$.

*Proof.* Each minimizer of $S$ is associated with one hyper-*k*-mer, so there are $((|S| - m + 1) \times d)$ hyper-*k*-mers on average. What's more, each pair of consecutive hyper-*k*-mers shares $k-1$ bases which can be written only once. Thus, except for the first hyper-*k*-mer (which uses $2(k-1)$ bases), each hyper-*k*-mer uses $k-1$ bases. Therefore, the expected total number of bases is $((|S| - m + 1) \times d + 1) \times (k-1)$, which is asymptotically equivalent to $|S| \cdot (k-1) \cdot d$ as $|S| \to +\infty$.
In particular, for random minimizers, the space usage of hyper-k-mers is asymptotically equivalent to $|S| \cdot \frac{2 \cdot (k-1)}{k-m+2} \sim 2 \cdot |S|$ for $k \gg m$. Figure 2 gives an overview of the evolution of the space usage as $k$ increases, and compares it to the evolution of super-k-mer's space usage.

These results, summarized in Table 1, show that representing a set of k-mers using hyper-k-mers is more space-efficient than super-k-mers and slightly more space-efficient than closed syncmers, regardless of the chosen minimizer scheme. In particular, hyper-k-mers require $2/3$ of the space used by super-k-mers for random minimizers, and this ratio gets even lower for minimizer schemes with a lower density.

<table><caption>Table 1: Comparison of the space usage of super-k-mers, closed syncmers and hyper-k-mers.</caption><thead><tr><th rowspan="2">Representation</th><th colspan="2">Expected number of bases / k-mer</th></tr><tr><th>Asymptotic formula</th><th>For random minimizers with $k \gg m$</th></tr></thead><tbody><tr><td>Super-k-mers (1)</td><td>$1 + (k-1) \cdot d$</td><td>3</td></tr><tr><td>Closed syncmers (2)</td><td>$k \cdot d$</td><td>2</td></tr><tr><td>Hyper-k-mers (3)</td><td>$(k-1) \cdot d$</td><td>2</td></tr></tbody></table>

<figure><img src="image_3.png" /><figcaption>Fig. 2: Space usage of super-k-mers and hyper-k-mers for $k \in [31, 200]$, with random minimizers of size 21.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Fig. 3: High-level view of the KFC data structure, using the example introduced in Figure 1. Two data structures are maintained. **Bottom**: a vector of hyper-k-mers parts stores the left and right parts of the hyper-k-mers computed from the original set of sequences. The bold parts correspond to the (possibly truncated) minimizers of the sequence. **Top**: a hash table associates each minimizer to a list of entries. Each entry represents a hyper-k-mer and its count. Each hyper-k-mer is represented using pointers (represented as dots) to its left and right parts in the vector of hyper-k-mers parts. To retrieve the parts, each pointer consists of the part's position in the vector, a start and end position in that part, and an orientation flag to handle reverse complements.</figcaption></figure>
## 3.4 Counting *k*-mers using hyper-*k*-mers

This section proposes *k*-mer counting as an application of hyper-*k*-mers to a real-life use-case. Hyper-*k*-mers are used as a proxy for storing *k*-mer counts. A simplified overview of the resulting index is presented in Figure 3.

Our *k*-mer counter implements a two-pass algorithm. In the first stage, we iterate over super-*k*-mers in the input sequences. We identify which super-*k*-mers are solid, i.e. are present more than two times in the input. If a super-*k*-mer is solid, the hyper-*k*-mer, along with its minimizer, is computed using its left and right super-*k*-mer neighbors (see Definition 8). If a computed hyper-*k*-mer was already present in the index, we increase its count in the hash table, otherwise, we insert a new entry in the table and insert the corresponding hyper-*k*-mers in the vector (encoded using two bits per base). However, doing so prevents us from counting the first and last super-*k*-mers of a read, as they are likely truncated and, by extension, unique and below our threshold. It also prevents us from counting the non-solid super-*k*-mers sharing their minimizer with a solid super-*k*-mer (indicating a possible sequencing error in the non-solid super-*k*-mer, whose *k*-mers shared with the solid super-*k*-mers should not be discarded).

As such, the second stage consists of correcting these issues by re-reading the input. Non-solid super-*k*-mers sharing their minimizer with solid super-*k*-mers which are substrings of hyper-*k*-mers already in the index, are added to the internal hash table. This also allows for the addition of the first and last super-*k*-mers of each read. After these two stages, the only *k*-mers that will be wrongly discarded are the ones that **A**/ are present more than two times in the input but **B**/ belong to a non-solid super-*k*-mer that does not share its minimizer with any of the solid super-*k*-mers. This super-*k*-mer-level threshold is slightly more aggressive than a *k*-mer-level threshold to filter unique *k*-mers. The effects of this heuristic are discussed in section 4.2.

As our algorithm works in a streaming fashion, at any time, only the index has to be maintained in memory whereas reads are only loaded on-demand. This allows our implementation to have a light memory footprint (see subsection 4.2), and to be parallelized (see Figure 10).

KFC's algorithm is given in Supplementary Materials (KFC's algorithm). For clarity, we omit some details, such as how KFC handles subsequences in hyper-*k*-mers parts.

# 4 Experiments

In this section, we benchmark our proposed *k*-mer counter, KFC, based on hyper-*k*-mers and compare it against other counters: Jellyfish [26], KMC [8,9,18], FASTK [28], Kaarme [10] and Gerbil [13]. Our implementation is written in Rust and publicly available at https://github.com/lrobidou/KFC with accompanying test scripts at https://github.com/imartayan/KFC_experiments.

## 4.1 Experimental setup

We report the datasets used in this study and their characteristics in the Supplementary Materials (Table 2). Experiments were performed on a common laptop computer (Dell Inc. Precision 7780 with 13th Gen Intel® Core™ i9-13950HX × 32 and 64GB RAM).

## 4.2 Results

**Long reads whole genome sequencing datasets** In our initial set of experiments, we evaluate all tools using coverage around 100X of the *E. coli* genome with three distinct long-read methods: ONT duplex, ONT simplex, and HiFi. We tested a wide range of *k*-mer sizes, up to 1021, and present the results in Figure 4. Despite the varying error distributions among the methods, the tools exhibit similar overall behaviors. Kaarme maintains an almost constant memory usage but is significantly slower than the other tools. Due to timeouts, it is not tested across all *k*-mer sizes. Jellyfish shows a steadily increasing memory usage with *k*, outperforming FastK and KMC at larger *k*-mer sizes, although it is nearly always the second slowest in terms of runtime. KMC3 and FastK demonstrate very similar behaviors, with memory usage quickly approaching the available RAM. FastK uses less memory than KMC in low-error experiments, but has comparable memory consumption on the noisier simplex dataset. In terms of runtime, both tools behave similarly, with execution time increasing rapidly with *k*. Gerbil outperforms both FastK and KMC3 by using less memory and achieving
<figure><img src="image_5.png" /><figcaption>(a) *k*-mer counting benchmark on ONT Duplex *E. coli* datasets (SRX23975767 and SRX23975758) at approximately 100X depth, with unique *k*-mer filtering</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>(b) *k*-mer counting benchmark on HiFi *E. coli* dataset (SRR11434954) downsampled at 100X depth, with unique *k*-mer filtering.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>(c) *k*-mer counting benchmark on ONT Simplex *E. coli* dataset (SRR28370668) downsampled at 100X coverage, with unique *k*-mer filtering.</figcaption></figure>

<caption>Fig. 4: Comparison of *k*-mer benchmarks on different *E.coli* datasets. Each subfigure shows the memory usage and timing plots for different sequencing technologies.</caption>

faster runtimes but cannot handle *k*-mers larger than 512. KFC is unique in that it is the only tool to display both decreasing runtime and memory usage with increasing *k*. Consequently, for *k*-mer sizes above 200, KFC exhibits the lowest runtime and memory usage among all the tested tools. Experiments for different coverages are reported in the Supplementary material, without significant change in the tools’ respective behaviors. We ran the same benchmark on two larger-scale metagenomic HiFi experiments, in order to assess the tools’ behavior on larger, and more complex datasets. As a medium-scale experiment, we chose a HiFi Zymo Biomics community sequencing that comprises at least one order magnitude more distinct
<figure><img src="image_8.png" /><figcaption>Fig. 5: *k*-mer counting benchmark on HiFi Zymo community dataset (SRR13128014) downsampled at 5 gigabases, with unique *k*-mer filtering.</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Fig. 6: *k*-mer counting benchmark on HiFi human gut datasets (SRR15275210, SRR15275211, SRR15275212, SRR15275213) downsampled at 15 gigabases, with unique *k*-mer filtering.</figcaption></figure>

*k*-mers, as it contains 21 strains of 17 species. We sampled 5 Gigabases of accession SRR13128014 and report the results in Figure 5. As a large-scale experiment, we chose the human gut metagenome HiFi sequencings used as metagenome assembly benchmark [15,2] accessions SRR15275210, SRR15275211, SRR15275212, and SRR15275213. Pooled, assemblers estimate the genome content of these datasets between 700 and 900 megabases [15]. We sampled 15 Gigabases of the four datasets pooled and report the results in Figure 6.

One might question how much of the observed improvement is due to the loss of certain *k*-mers resulting from the super-*k*-mer filtering heuristic. To confirm the validity of our approach, we conduct the same experiment without unique *k*-mer filtering, i.e., counting all *k*-mers and therefore without super-*k*-mer filtering. The results are shown in Supplementary materials (Figure 13). We observe that Jellyfish's performance remains unchanged, while FastK and KMC's performance significantly degrades in both time and memory usage. While KFC is indeed slower and more memory-intensive without the super-*k*-mer filtering heuristic, it remains competitive even when compared to its competitors that filter unique *k*-mers.

**Pangenome k-mer analysis** In a distinct experiment reported in Figure 7, we run the different tools on one thousand *S. enterica* complete genomes from NCBI to evaluate the cost of counting large *k*-mers for pangenome analysis. We observe that KFC remains the most memory-efficient tool, followed by FastK and then KMC. Regarding runtime, KFC becomes the fastest tool for very large *k*-mer sizes (above 500), despite its currently limited multithreading efficiency compared to KMC when processing low amounts of sequences. This suggests the need for further software engineering improvements for KFC, as it is not yet mature. Notably, when using a lower number of threads, KFC becomes the fastest tool. Additionally, FastK's runtime increases rapidly with *k*. These findings highlight the advantage of KFC in handling genome collections without filtering.
<figure><img src="image_10.png" /><figcaption>Fig. 7: *k*-mer counting benchmark on one thousand *S. enterica* complete genome.</figcaption></figure>

**Internal evaluations** In this section, we present several internal experiments to evaluate key implementation aspects of KFC.

We evaluated the super-*k*-mer abundance threshold heuristic by analyzing the number of *k*-mers lost when applying the unique super-*k*-mer removal heuristics (Figure 8). We observe that the number of “lost” *k*-mers decreases exponentially as the *k*-mer abundance threshold increases. This loss is more significant at low coverage levels, particularly for larger *k*-mer sizes. Similar to classical *k*-mer abundance filtering, higher error rates significantly impact the mean coverage of genomic *k*-mers, resulting in greater *k*-mer loss at high error rates compared to low error rates. Although the proportion of lost *k*-mers may seem substantial, we argue that most of these are low-abundance ones and thus likely erroneous. To substantiate this claim, we count the number of *k*-mers from the reference genome that are absent in both KMC and KFC outputs, considering different *k*-mer sizes and abundance thresholds (Figure 9). At low *k*-mer abundance thresholds, KFC filters more *k*-mers than KMC; however, as the *k*-mer abundance threshold increases, both methods exhibit similar behaviors, with the number of filtered *k*-mers remaining relatively low. We repeated the experiment using a dataset with a HiFi error rate (0.1%) and observed no differences between the outputs of KMC and KFC. This confirms that the super-*k*-mer abundance threshold, while slightly more aggressive than the *k*-mer-level threshold, remains conservative enough to maintain accuracy while delivering substantial performance improvements.

We also report the efficiency of KFC's multithreading in the Supplementary Materials, subsection A.2.

<figure><img src="image_11.png" /><figcaption>Fig. 8: Percentage of *k*-mers lost by removing unique super-*k*-mers, based on the applied abundance threshold and *k*-mer size. The plot on the left represents a simulated HiFi dataset with 100x coverage and an error rate of 0.1%, while the plot on the right shows results from a simulated ONT dataset with the same coverage but an error rate of 1%.</figcaption></figure>
<figure><img src="image_12.png" /><figcaption>Fig. 9: Amount of filtered genomic *k*-mers by KFC and KMC according to the abundance threshold and the *k*-mer size on a simulated 100X ONT *E. coli* dataset with 1% error rate.</figcaption></figure>

# 5 Conclusions and future work

In this work, we studied the problem of memory-efficient *k*-mer set representations and proposed a novel solution, *hyper-*(*k*-mers, which aims to reduce space redundancy caused by *k*-mer overlaps. Theoretical analysis and practical experiments demonstrate that hyper-*k*-mers are more succinct than their direct competitor, *super-*(*k*-mers, achieving space usage closer to sampling techniques such as syncmers, while still providing a direct *k*-mer representation. Hyper-*k*-mers represent sequences as collections of minimizers and the sequences between them. This approach reduces *k*-mer overlaps and, consequently, theoretically allows hyper-*k*-mers to achieve a space usage of 4 bits per (DNA) base. We implemented a novel *k*-mer counter, KFC, based on hyper-*k*-mers, which shows excellent performance. For large *k* values, KFC outperforms all competitors in both speed and memory usage, and uniquely becomes more efficient for increasing *k*-mer sizes. Since longer *k*-mers are expected to become more relevant in the coming years—thanks to steadily improving sequencing technologies leading to longer and less error-prone reads—we believe that hyper-*k*-mers and KFC are future-proof solutions.

Several improvements are possible. First, although our theoretical analysis shows that hyper-*k*-mers are a direct improvement over super-*k*-mers, they are still more space-consuming than the theoretical lower bound of 2 bits per *k*-mer. Finding an optimal representation that achieves this lower bound remains an open question. Second, our current implementation of hyper-*k*-mers does not scale well to short *k* values. Smaller *k*-s are harder to optimize due to the large number of collisions between minimizers and contexts. While very small *k*-s (*k* < 16) are manageable with a simple hash table storing *k*-mers individually, *k*-mer lengths in the range 17 to 63 could still benefit from dynamic linear set representations like hyper-*k*-mers. Developing such a solution remains an open question. Finally, as mentioned in subsection 3.4, the current version of KFC is based on a two-pass algorithm that discards *k*-mers belonging to non-solid super-*k*-mers if no minimizer is shared with any solid super-*k*-mer. While this heuristic is extremely efficient, handling this corner case is another direction for future improvements.

**Disclosure of Interests.** The authors have no competing interests to declare that are relevant to the content of this article.
## References

1. Bankevich, A., Bzikadze, A.V., Kolmogorov, M., Antipov, D., Pevzner, P.A.: Multiplex de bruijn graphs enable genome assembly from long, high-fidelity reads. Nature biotechnology **40**(7), 1075-1081 (2022)

2. Benoit, G., Raguideau, S., James, R., Phillippy, A.M., Chikhi, R., Quince, C.: High-quality metagenome assembly from long accurate reads with metamdbg. Nature Biotechnology pp. 1-6 (2024)

3. Chikhi, R., Limasset, A., Jackman, S., Simpson, J.T., Medvedev, P.: On the representation of de bruijn graphs. In: Research in Computational Molecular Biology: 18th Annual International Conference, RECOMB 2014, Pittsburgh, PA, USA, April 2-5, 2014, Proceedings 18. pp. 35-55. Springer (2014)

4. Chikhi, R., Limasset, A., Jackman, S., Simpson, J.T., Medvedev, P.: On the Representation of de Bruijn Graphs. In: Sharan, R. (ed.) Research in Computational Molecular Biology. pp. 35-55. Springer International Publishing, Cham (2014). https://doi.org/10.1007/978-3-319-05269-4_4

5. Chikhi, R., Limasset, A., Medvedev, P.: Compacting de bruijn graphs from sequencing data quickly and in low memory. Bioinformatics **32**(12), i201-i208 (2016)

6. Cracco, A., Tomescu, A.I.: Extremely fast construction and querying of compacted and colored de Bruijn graphs with GGCAT. Genome Research **33**(7), 1198-1207 (Jul 2023). https://doi.org/10.1101/gr.277615.122, https://genome.cshlp.org/content/33/7/1198

7. Deorowicz, S., Debudaj-Grabysz, A., Grabowski, S.: Disk-based k-mer counting on a pc. BMC bioinformatics **14**, 1-12 (2013)

8. Deorowicz, S., Debudaj-Grabysz, A., Grabowski, S.: Disk-based k-mer counting on a PC. BMC Bioinform. **14**, 160 (2013). https://doi.org/10.1186/1471-2105-14-160, https://doi.org/10.1186/1471-2105-14-160

9. Deorowicz, S., Kokot, M., Grabowski, S., Debudaj-Grabysz, A.: KMC 2: fast and resource-frugal k-mer counting. Bioinformatics **31**(10), 1569-1576 (01 2015). https://doi.org/10.1093/bioinformatics/btv022, https://doi.org/10.1093/bioinformatics/btv022

10. Díaz-Domínguez, D., Leinonen, M., Salmela, L.: Space-efficient computation of k-mer dictionaries for large values of k. Algorithms Mol. Biol. **19**(1), 14 (2024). https://doi.org/10.1186/s13015-024-00259-1, https://doi.org/10.1186/s13015-024-00259-1

11. Dufresne, Y., Lemane, T., Marijon, P., Peterlongo, P., Rahman, A., Kokot, M., Medvedev, P., Deorowicz, S., Chikhi, R.: The k-mer file format: a standardized and compact disk representation of sets of k-mers. Bioinformatics **38**(18), 4423-4425 (2022)

12. Edgar, R.: Syncmers are more sensitive than minimizers for selecting conserved k-mers in biological sequences. PeerJ **9**, e10805 (2021)

13. Erbert, M., Rechner, S., Müller-Hannemann, M.: Gerbil: a fast and memory-efficient k-mer counter with gpu-support. Algorithms for Molecular Biology **12**, 1-12 (2017)

14. Fan, J., Khan, J., Singh, N.P., Pibiri, G.E., Patro, R.: Fulgor: a fast and compact k-mer index for large-scale matching and color queries. Algorithms for Molecular Biology **19**(1), 3 (Jan 2024). https://doi.org/10.1186/s13015-024-00251-9, https://doi.org/10.1186/s13015-024-00251-9

15. Feng, X., Cheng, H., Portik, D., Li, H.: Metagenome assembly of high-fidelity long reads with hifiasm-meta. Nature methods **19**(6), 671-674 (2022)

16. Groot Koerkamp, R., Pibiri, G.E.: The mod-minimizer: A Simple and Efficient Sampling Algorithm for Long k-mers. In: Pissis, S.P., Sung, W.K. (eds.) 24th International Workshop on Algorithms in Bioinformatics (WABI 2024). Leibniz International Proceedings in Informatics (LIPIcs), vol. 312, pp. 11:1-11:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2024). https://doi.org/10.4230/LIPIcs.WABI.2024.11, https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2024.11

17. Khorsand, P., Hormozdiari, F.: Nebula: ultra-efficient mapping-free structural variant genotyper. Nucleic Acids Research **49**(8), e47-e47 (May 2021). https://doi.org/10.1093/nar/gkab025, https://academic.oup.com/nar/article/49/8/e47/6121467

18. Kokot, M., Dlugosz, M., Deorowicz, S.: KMC 3: counting and manipulating k-mer statistics. Bioinformatics **33**(17), 2759-2761 (05 2017). https://doi.org/10.1093/bioinformatics/btx304, https://doi.org/10.1093/bioinformatics/btx304

19. Li, Y., Kamousi, P., Han, F., Yang, S., Yan, X., Suri, S.: Memory efficient minimum substring partitioning. Proc. VLDB Endow. **6**(3), 169-180 (Jan 2013). https://doi.org/10.14778/2535569.2448951, https://dl.acm.org/doi/10.14778/2535569.2448951

20. Li, Y., et al.: Mspkmercounter: a fast and memory efficient approach for k-mer counting. arXiv preprint arXiv:1505.06550 (2015)

21. Limasset, A., Flot, J.F., Peterlongo, P.: Toward perfect reads: self-correction of short reads via mapping on de Bruijn graphs. Bioinformatics **36**(5), 1374-1381 (Mar 2020). https://doi.org/10.1093/bioinformatics/btz102, https://academic.oup.com/bioinformatics/article/36/5/1374/5345559

22. Mamun, A.A., Pal, S., Rajasekaran, S.: Kcmbt: ak-mer counter based on multiple burst trees. Bioinformatics **32**(18), 2783-2790 (2016)
23. Marchet, C., Iqbal, Z., Gautheret, D., Salson, M., Chikhi, R.: Reindeer: efficient indexing of k-mer presence and abundance in sequencing datasets. Bioinformatics **36**(Supplement _1), i177-i185 (2020)

24. Marchet, C., Kerbiriou, M., Limasset, A.: Blight: efficient exact associative structure for k-mers. Bioinformatics **37**(18), 2858-2865 (2021)

25. Marchet, C., Limasset, A.: Scalable sequence database search using partitioned aggregated bloom comb trees. Bioinformatics **39**(Supplement _1), i252-i259 (2023)

26. Marçais, G., Kingsford, C.: A fast, lock-free approach for efficient parallel counting of occurrences of k-mers. Bioinformatics **27**(6), 764-770 (01 2011). https://doi.org/10.1093/bioinformatics/btr011, https://doi.org/10.1093/bioinformatics/btr011

27. Melsted, P., Pritchard, J.K.: Efficient counting of k-mers in dna sequences using a bloom filter. BMC bioinformatics **12**, 1-7 (2011)

28. Myers, G.: FASTK: A fast K-mer counter for high-fidelity shotgun datasets. https://github.com/thegenemyers/FASTK

29. Pandey, P., Bender, M.A., Johnson, R., Patro, R.: A general-purpose counting filter: Making every bit count. In: Proceedings of the 2017 ACM international conference on Management of Data. pp. 775-787 (2017)

30. Pandey, P., Bender, M.A., Johnson, R., Patro, R.: Squeakr: an exact and approximate k-mer counting system. Bioinformatics **34**(4), 568-575 (2018)

31. Pibiri, G.E.: Sparse and skew hashing of K-mers. Bioinformatics **38**(Supplement _1), i185-i194 (Jun 2022). https://doi.org/10.1093/bioinformatics/btac245, https://academic.oup.com/bioinformatics/article/38/Supplement_1/i185/6617506

32. Pibiri, G.E., Shibuya, Y., Limasset, A.: Locality-preserving minimal perfect hashing of k-mers. Bioinformatics **39**(Supplement _1), i534-i543 (2023)

33. Pibiri, G.E., Shibuya, Y., Limasset, A.: Locality-preserving minimal perfect hashing of k-mers. Bioinformatics **39**(Supplement _1), i534-i543 (Jun 2023). https://doi.org/10.1093/bioinformatics/btad219, https://academic.oup.com/bioinformatics/article/39/Supplement_1/i534/7210438

34. Rizk, G., Lavenier, D., Chikhi, R.: DSK: k-mer counting with very low memory usage. Bioinformatics **29**(5), 652-653 (01 2013). https://doi.org/10.1093/bioinformatics/btt020, https://doi.org/10.1093/bioinformatics/btt020

35. Roberts, M., Hayes, W., Hunt, B.R., Mount, S.M., Yorke, J.A.: Reducing storage requirements for biological sequence comparison. Bioinformatics **20**(18), 3363-3369 (Dec 2004). https://doi.org/10.1093/bioinformatics/bth408, https://academic.oup.com/bioinformatics/article/20/18/3363/202143

36. Rouzé, T., Martayan, I., Marchet, C., Limasset, A.: Fractional Hitting Sets for Efficient and Lightweight Genomic Data Sketching. In: DROPS-IDN/v2/document/10.4230/LIPIcs.WABI.2023.15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023). https://doi.org/10.4230/LIPIcs.WABI.2023.15, https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2023.15

37. Roy, R.S., Bhattacharya, D., Schliep, A.: Turtle: Identifying frequent k-mers with cache-efficient algorithms. Bioinformatics **30**(14), 1950-1957 (2014)

38. Schleimer, S., Wilkerson, D.S., Aiken, A.: Winnowing: local algorithms for document fingerprinting. In: Proceedings of the 2003 ACM SIGMOD international conference on Management of data. pp. 76-85. SIGMOD '03, Association for Computing Machinery, New York, NY, USA (Jun 2003). https://doi.org/10.1145/872757.872770, https://dl.acm.org/doi/10.1145/872757.872770

39. Schmidt, S., Alanko, J.N.: Eulertigs: Minimum Plain Text Representation of k-mer Sets Without Repetitions in Linear Time. In: DROPS-IDN/v2/document/10.4230/LIPIcs.WABI.2022.2. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022). https://doi.org/10.4230/LIPIcs.WABI.2022.2, https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2022.2

40. Schmidt, S., Khan, S., Alanko, J.N., Pibiri, G.E., Tomescu, A.I.: Matchtigs: minimum plain text representation of k-mer sets. Genome Biology **24**(1), 136 (2023)

41. Sereika, M., Kirkegaard, R., Karst, S., Michaelsen, T., Sørensen, E., Wollenberg, R., Albertsen, M.: Oxford nanopore r10.4 long-read sequencing enables near-perfect bacterial genomes from pure cultures and metagenomes without short-read or reference polishing. Microbiology **10**(2021.10), 27-466057 (2021)

42. Shibuya, Y., Belazzougui, D., Kucherov, G.: Efficient Reconciliation of Genomic Datasets of High Similarity. In: 22nd International Workshop on Algorithms in Bioinformatics (WABI 2022). pp. 14:1-14:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022). https://doi.org/10.4230/LIPIcs.WABI.2022.14, https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2022.14

43. Sims, G.E., Jun, S.R., Wu, G.A., Kim, S.H.: Alignment-free genome comparison with feature frequency profiles (FFP) and optimal resolutions. Proceedings of the National Academy of Sciences **106**(8), 2677-2682 (Feb 2009). https://doi.org/10.1073/pnas.0813249106, https://pnas.org/doi/full/10.1073/pnas.0813249106

44. Suzuki, S., Kakuta, M., Ishida, T., Akiyama, Y.: Accelerating identification of frequent k-mers in dna sequences with gpu (2014)
45. Zentgraf, J., Rahmann, S.: Fast gapped k-mer counting with subdivided multi-way bucketed cuckoo hash tables. In: 22nd International Workshop on Algorithms in Bioinformatics (WABI 2022). Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2022)

46. Zerbino, D.R., Birney, E.: Velvet: algorithms for de novo short read assembly using de bruijn graphs. Genome research 18(5), 821-829 (2008)
# A Supplementary materials

## A.1 Datasets characteristics

In this section, we report the datasets we used in our experiments and some of their characteristics (Table 2).

<table><caption>Table 2: Datasets used for testing KFC. Min. Avg. and Max. refer to the minimum, average and maximum length of the reads, respectively.</caption><thead><tr><th>Name</th><th>Organism</th><th>Type</th><th>Coverage</th><th># reads</th><th>Total length</th><th>Min.</th><th>Avg.</th><th>Max.</th></tr></thead><tbody><tr><td>SRR11434954</td><td>E.Coli</td><td>HiFi</td><td>5000x</td><td>1,789,131</td><td>23,122,913,014</td><td>46</td><td>12,924.1</td><td>26,294</td></tr><tr><td>SRR28370642</td><td>E.Coli</td><td>ONT (Duplex)</td><td>50x</td><td>114,703</td><td>236,908,842</td><td>349</td><td>2,065.4</td><td>126,029</td></tr><tr><td>SRR28370651</td><td>E.Coli</td><td>ONT (Duplex)</td><td>50x</td><td>109,061</td><td>226,502,819</td><td>330</td><td>2,076.8</td><td>125,012</td></tr><tr><td>SRR28370668</td><td>E.Coli</td><td>ONT (Simplex)</td><td>2000x</td><td>6,819,683</td><td>9,101,103,830</td><td>1</td><td>1,334.5</td><td>396,011</td></tr></tbody></table>

## A.2 Multi-threading efficiency of KFC

In this section, we assess the multi-threading efficiency of KFC (Figure 10). Our results demonstrate that KFC effectively utilizes multi-core architectures, achieving performance gains with up to several dozen cores before experiencing diminishing returns.

<figure><img src="image_13.png" /><figcaption>Fig. 10: Multiple core usage efficiency on the 100X HiFi *E. coli* dataset.</figcaption></figure>

## A.3 Effect of coverage

In this section, we present the performance benchmark similar to Figure 4, but with various coverage. The results of this benchmark are shown in Figure 11.
<figure><img src="image_14.png" /><figcaption>(a) *k*-mer counting benchmark on HiFi *E. coli* dataset () downsampled at 50X coverage, with unique *k*-mer filtering.</figcaption></figure>

<figure><img src="image_15.png" /><figcaption>(b) *k*-mer counting benchmark on ONT Simplex *E. coli* dataset (SRR28370668) downsampled at 200X coverage, with unique *k*-mer filtering.</figcaption></figure>

<figure><img src="image_16.png" /><figcaption>(c) *k*-mer counting benchmark on ONT Simplex *E. coli* dataset (SRR28370668) downsampled at 500X coverage, without unique *k*-mer filtering.</figcaption></figure>

<caption>Fig. 11: *k*-mer counting benchmark on ONT Simplex *E. coli* dataset (SRR28370668) for various coverage.</caption>
<figure><img src="image_17.png" /><figcaption>Fig. 12: *k*-mer counting benchmark on complete HiFi human gut datasets (SRR15275210, SRR15275211, SRR15275212, SRR15275213), with unique *k*-mer filtering.</figcaption></figure>
## A.4 Effect of not filtering unique *k*-mers

In this section, we present the performance of KFC when unique *k*-mers are not filtered out. Figure 13 shows the results discussed in section 4.2. They are similar to Figure 4, but without filtering unique *k*-mers.

<figure><img src="image_18.png" /><figcaption>(a) *k*-mer counting benchmark on ONT Duplex *E. coli* datasets (SRX23975767 and SRX23975758) at approximately 100X depth, without unique *k*-mer filtering</figcaption></figure>

<figure><img src="image_19.png" /><figcaption>(b) *k*-mer counting benchmark on HiFi *E. coli* dataset (SRR11434954) downsampled at 100X depth, without unique *k*-mer filtering.</figcaption></figure>

<figure><img src="image_20.png" /><figcaption>(c) *k*-mer counting benchmark on ONT Simplex *E. coli* dataset (SRR28370668) downsampled at 100X coverage, without unique *k*-mer filtering.</figcaption></figure>

Fig. 13: Comparison of Kmer benchmarks on different *E.coli* datasets without any filtering. Each subfigure shows the memory usage and timing plots for different sequencing technologies.
## A.5 KFC's algorithm

In this section, we present an overview of the two stages of KFC (in Algorithm 1).

<caption>**Algorithm 1 Counting**</caption>

1: **procedure** COUNT_HYPERKMER(*read_set* ∈ (Σ*)*; *k*, *m* and *t* in N with *m* ≤ *k*)
2:     *sk_count* ← empty multimap ▷ maps *minimizer* to (*hash sk*)*, *count sk*)*
3:     *hk_count* ← empty multimap ▷ maps *minimizer* to (*id left hk*, *id right hk*, *count hk*)
4:     *hyperkmer_parts* ← empty vector of string ▷ encoded in 2 bits per character
5:     ▷ first pass
6:     **for** *read* in *read_set* **do** ▷ can be parallelized
7:         **for** (*prev sk*, *sk*, *next sk*) in *read* **do**
8:             *m* ← *minimizer* of *sk*
9:             **if** (*hash sk*)*, *associated_count* ∈ *sk_count*[*m*] **then**
10:                 *current_count* = *associated_count* + 1
11:                 replace *associated_count* by *current_count* in *sk_count*
12:             **else**
13:                 *current_count* = 1
14:                 add (*hash sk*)*, *current_count* to *sk_count*
15:             **end if**
16:         **if** *current_count* = *t* **then**
17:             *left_hk_part* ← left hyper-k-mer part of *sk*
18:             **if** *is solid*(*sk_count*, *prev sk*, *t*) **then**
19:                 ▷ if the previous super-k-mer is solid, we take a reference to its hyper-k-mer part
20:                 *id left hk* ← id of the right hyper-k-mer part of *prev sk*
21:             **else**
22:                 ▷ else, we insert a new hyper-k-mer part
23:                 *id left hk* ← length of *hyperkmer_parts*
24:                 append *left_hk_part* to *hyperkmer_parts*
25:             **end if**
26:         ▷ same with the next super-k-mer
27:         *right_hk_part* ← right hyper-k-mer part of *sk*
28:         **if** *is solid*(*sk_count*, *next sk*, *t*) **then**
29:             *id right hk* ← id of the left hyper-k-mer part of *next sk*
30:         **else**
31:             *id right hk* ← length of *hyperkmer_parts*
32:             append *right_hk* to *hyperkmer_parts*
33:         **end if**
34:     add an entry *m* → (*id left hk*, *id right hk*, *current_count*) to *hk_count*
35:     **else**
36:         **if** *current_count* > *t* **then** ▷ the current super-k-mer is already indexed
37:             (*left_part_id*, *right_part_id*, *exact_match*) ← *get_parts_and_increase_count_if_inclusion*(*hk_count*,
38:                   *hyperkmer_parts*,
39:                   *sk*
40:                   )
41:         **if** not *exact_match* **then**
42:             add an entry *m* → (*left_part_id*, *right_part_id*, 1) to *hk_count*
43:         **end if**
44:     **end if**
45:     **end if**
46:     **end if**
47:     **end for**
48:     **end for**
49:     ▷ second pass
50:     **for** *read* in *read_set* **do** ▷ can be parallelized
51:         **for** (*sk*) in *read* **do**
52:             *m* ← *minimizer* of *sk*
53:             **if** *first iteration* or *last iteration* **then**
54:                 ▷ increase count if exact match
55: ▷ insert new entry while taking a reference to existing parts if possible

56: `(left_part_id, right_part_id, exact_match) ← get_parts_and_increase_count_if_inclusion()`

57: `hk_count`,

58: `hyperkmer_parts`,

59: `sk`

60: )

61: **if** not `exact_match` **then**

62: ▷ the current super-k-mer may be not indexed already

63: ▷ so we have to add its left and right parts if they are not already present

64: **if** `left_part_id = -1` **then**

65: `left_part_id ←` length of `hyperkmer_parts`

66: append left part of `sk` to `hyperkmer_parts`

67: **end if**

68: **if** `right_part_id = -1` **then**

69: `right_part_id ←` length of `hyperkmer_parts`

70: append right part of `sk` to `hyperkmer_parts`

71: **end if**

72: add an entry `m → (left_part_id, right_part_id, 1)` to `hk_count`

73: **end if**

74: **else**

75: ▷ solid super-k-mers were treated during the first pass

76: **if** not `is_solid(sk_count, sk, t)` **then**

77: `get_parts_and_increase_count_if_inclusion(hk_count, hyperkmer_parts, sk)`

78: **end if**

79: **end if**

80: **end for**

81: **end for**

82: **return** `sk_count`, `hk_count`, `hyperkmer_parts`

83: **end procedure**

84:

85: ▷ given a threshold `t`, checks is a super-k-mer is solid

86: **procedure** `IS_SOLID(sk_count, sk, t)`

87: **for** `(hash_sk, count) ∈ sk_count[m]` **do**

88: **if** `hash(sk) = hash_sk` **then**

89: **if** `count ≥ t` **then**

90: **return** `true`

91: **else**

92: **return** `false`

93: **end if**

94: **end if**

95: **end for**

96: **return** `false`

97: **end procedure**

98:

99: ▷ search if a super-k-mer is indexed in the hyper-k-mer index

100: ▷ return the position of the left and right hyper-k-mer parts that include it, and a boolean indicating if the super-k-mer is indexed

101: ▷ if the super-k-mer is indexed, the count of its entry is increased

102: **procedure** `GET_PARTS_AND_INCREASE_COUNT_IF_INCLUSION(hk_count, hyperkmer_parts, sk)`

103: `left_part_id ← -1` ▷ sentinel value for "not found"

104: `right_part_id ← -1`

105: `exact_match ← false`

106: **for** `(id_left_hk, id_right_hk, hk_count) ∈ hk_count[m]` **do**

107: **if** `(hyperkmer_parts[id_left_hk], hyperkmer_parts[id_right_hk]) = sk` **then**

108: increment `hk_count`

109: `exact_match ← true`

110: **break**

111: **else**

112: **if** `sk` starts with `hyperkmer_parts[id_left_hk]` **then**
20 I. Martayan et al.

113: left_part_id ← id_left_hk

114: end if

115: if sk ends with hyperkmer_parts[id_right_hk] then

116: right_part_id ← id_right_hk

117: end if

118: end if

119: end for

120: return left_part_id, right_part_id, exact_match

121: end procedure