Yoshihiro Shibuya

Djamal Belazzougui

Gregory Kucherov

Space-Efficient Representation of Genomic k-Mer Count Tables

Keywords: 2012 ACM Subject Classification Applied computing k-mer counting, data structures, compression, minimizers, compressed static function, Bloom filter, empirical entropy Digital Object Identifier 10.4230/LIPIcs.WABI.2021

Motivation. k-mer counting is a common task in bioinformatic pipelines, with many dedicated tools available. Output formats could rely on quotienting to reduce the space of k-mers in hash tables, however counts are not usually stored in space-efficient formats. Overall, k-mer count tables for genomic data take a considerable space, easily reaching tens of GB. Furthermore, such tables do not support efficient random-access queries in general.

Results.

In this work, we design an efficient representation of k-mer count tables supporting fast random-access queries. We propose to apply Compressed Static Functions (CSFs), with space proportional to the empirical zero-order entropy of the counts. For very skewed distributions, like those of k-mer counts in whole genomes, the only currently available implementation of CSFs does not provide a compact enough representation. By adding a Bloom Filter to a CSF we obtain a Bloom-enhanced CSF (BCSF) effectively overcoming this limitation. Furthermore, by combining BCSFs with minimizer-based bucketing of k-mers, we build even smaller representations breaking the empirical entropy lower bound, for large enough k. We also extend these representations to the approximate case, gaining additional space. We experimentally validate these techniques on k-mer count tables of whole genomes (E.Coli and C.Elegans) as well as on k-mer document frequency tables for 29 E.Coli genomes. In the case of exact counts, our representation takes about a half of the space of the empirical entropy, for large enough k's.

Introduction

Nowadays, many bioinformatics pipelines rely on k-mers to perform a multitude of different tasks. Representing sequences as sets of words of length k generally leads to more timeefficient algorithms than relying on traditional alignments. For these reasons, alignment-free algorithms have started to replace their alignment-based counterparts in a wide range of practical applications, from sequence comparison and phylogenetic reconstruction [34, 36, Our first contribution is the enhancement of CSFs with a Bloom Filter to deal with datasets of very small entropy and to achieve better space usage. We chose an E.Coli and a C.Elegans genome to test our implementation. With these examples, we demonstrate the advantages of our BCSF implementation over a simple CSF.

Our second improvement takes advantage of the fact that similar k-mers tend to have identical (or similar) counts (see also [START_REF] Marchet | REINDEER: efficient indexing of k-mer presence and abundance in sequencing datasets[END_REF]). Following this insight, we introduce a minimizerbased bucketing scheme to cluster together count values of k-mers with the same minimizer. A similar idea is used by some k-mer counting algorithms [START_REF] Rizk | DSK: k-mer counting with very low memory usage[END_REF][START_REF] Kokot | KMC 3: counting and manipulating k-mer statistics[END_REF][START_REF] Lemane | kmtricks: Efficient construction of Bloom filters for large sequencing data collections[END_REF] with the difference that in our case buckets contain counts rather than k-mers themselves. By choosing a representative value for each bucket, we obtain a "bucket table" that we encode using Bloom-enhanced CSF. Bucketing allows us to break the empirical entropy lower bound, as we show on both E.Coli and C.Elegans examples. To demonstrate the advantages of bucketing on higher-entropy distributions, we apply it to represent a table of "document frequencies" [START_REF] Spärck | A statistical interpretation of term specificity and its application in retrieval[END_REF][START_REF] Cong | A novel alignment-free method for detection of lateral genetic transfer based on TF-IDF[END_REF][START_REF] Moussa | Single cell RNA-seq data clustering using TF-IDF based methods[END_REF][START_REF] Koren | Canu: scalable and accurate long-read assembly via adaptive k-mer weighting and repeat separation[END_REF] of each k-mer across multiple strains of E.Coli.

We study different implementation schemes based on these ideas and compare their space performance, as well as associated query time. For large enough k (and large enough minimizers lengths), we are able to consistently break the barrier of the empirical entropy of the input table. To the best of our knowledge, this is the first implementation proposing such a compact representation. We also study an extension to the approximate case when query answers are within a pre-defined absolute error from the true value, for which we achieve an even smaller space.

Technical preliminaries

Throughout the paper we consider a k-mer count table to be an associative array f mapping a set of k-mers K, considered static, to their counts, i.e. number of occurrences in a given dataset. ||f || 1 stands for the L1-norm of f , that is q∈K f (q).

Minimizers

Minimizers are a popular technique used in different applications involving k-mer analysis. Given a k-mer q of length k, its minimizer of length m, with m ≤ k, is the smallest substring of q of length m w.r.t. some order defined on m-mers. The use of minimizers for biosequence analysis goes back to [START_REF] Roberts | Reducing storage requirements for biological sequence comparison[END_REF], whereas a similar concept, named winnowing, has been earlier applied in [START_REF] Schleimer | Winnowing: local algorithms for document fingerprinting[END_REF] to document search. The guiding idea is that a minimizer can be considered as a "footprint" (hash value) of a corresponding k-mer so that similar (e.g. neighboring in the genome) k-mers are likely to have the same minimizer. Thus, if the order of m-mers is randomly chosen, minimizers can be seen as a specific instance of locality-sensitive hashing, in particular of MinHash sketching [START_REF] Broder | On the resemblance and containment of documents[END_REF].

Minimizers have been successfully applied to various data-intensive sequence analysis problems in bioinformatics, such as metagenomics (Kraken [START_REF] Wood | Kraken: ultrafast metagenomic sequence classification using exact alignments[END_REF]) or minimizing cache misses in k-mer counting (KMC [START_REF] Kokot | KMC 3: counting and manipulating k-mer statistics[END_REF]), or mapping and assembling long single-molecule reads [START_REF] Li | Minimap and miniasm: fast mapping and de novo assembly for noisy long sequences[END_REF][START_REF] Li | Minimap2: pairwise alignment for nucleotide sequences[END_REF]. Recently, there has been a series of works on both theoretical and practical aspects of designing efficient minimizers, see e.g. [START_REF] Zheng | Lower Density Selection Schemes via Small Universal Hitting Sets with Short Remaining Path Length[END_REF][START_REF] Ekim | A Randomized Parallel Algorithm for Efficiently Finding Near-Optimal Universal Hitting Sets[END_REF] and references therein.

Bloom filters

Bloom filter is a very common probabilistic data structure that supports membership queries for a given set S drawn from a large universe U , admitting a controlled fraction of false positives. To insure a false positive rate ε, that is the probability ε for an item from U \ S to WA B I 2 0 2 1

8:4

Compressed k-Mer Count Tables be erroneously classified as belonging to S, a Bloom filter B requires |S| log e log 1 ε bits, i.e. ≈ 1.44 log 1 ε bits per element of S. For a set T ⊆ U \ S, we denote F P B (T ) the set of false positives of T , of expected size ε|T |.

Compressed static functions

A static function (SF) is a representation of a function defined on a given subset S of a universe U such that an invocation of the function on any element from S yields the function value, while an invocation on an element from U \ S produces an arbitrary output. The problem has been studied in several works (see references in [START_REF] Belazzougui | Compressed Static Functions with Applications[END_REF][START_REF] Genuzio | Fast scalable construction of ([compressed] static | minimal perfect hash) functions[END_REF]) resulting in several solutions that allow function values to be retrieved without storing elements of S themselves. One natural solution comes through MPHFs: one can build an MPHF for S and then store function values in order in a separate array. This solution, however, incurs an overhead associated with the MPHF, known to be theoretically lower-bounded by about 1.44 bits per element of S.

This overhead is especially unfortunate when the distribution of values is very skewed, in which case the value array may be compressed into a much smaller space. Compressed Static Functions try to solve this problem by proposing a static function representation whose size depends on the compressed value array. The latter is usually estimated through the zero-order empirical entropy, defined by

H 0 (f ) = ℓ∈L |f -1 (ℓ)| |K| log( |K| |f -1 (ℓ)| ), where L is the set of all values (i.e. L = {f (t) | t ∈ K}}) and f -1 (ℓ) = {t | f (t) = ℓ} is the set of k-mers with count ℓ. |K| • H 0 (f )
can be viewed as a lower bound on the size of compressed value array, in absence of additional assumptions. Thus, the goal of CSFs is to approach the bound of H 0 (f ) bits per element as closely as possible, in representing a static function f . An overview of different algorithmic solutions for SFs and CSFs is out of scope of this paper, we refer the reader to [START_REF] Belazzougui | Compressed Static Functions with Applications[END_REF][START_REF] Genuzio | Fast scalable construction of ([compressed] static | minimal perfect hash) functions[END_REF] and references therein. [START_REF] Belazzougui | Compressed Static Functions with Applications[END_REF] proposed a solution for CSF taking an asymptotically optimal nH 0 (f ) + o(nH 0 (f )) space (n size of the underlying value set), however the solution is rather complex and probably not suitable for practical implementation. As of today, to our knowledge, the only practical implementation of a CSF is GV3CompressedFunction [START_REF] Genuzio | Fast scalable construction of ([compressed] static | minimal perfect hash) functions[END_REF], found in the Java package Sux4J (https://sux.di.unimi. it/). Although entropy-sensitive, the method of [START_REF] Genuzio | Fast scalable construction of ([compressed] static | minimal perfect hash) functions[END_REF], however, has an intrinsic limitation of using at least 1 bit per element, due to involved coding schemes. This is a serious limitation when dealing with very skewed distributions of values, where one value occurs predominantly often and the empirical entropy can be much smaller than 1. This is precisely the case for count distributions in whole genomes, studied in this paper.

Representation of low-entropy data

As mentioned earlier, Compressed Static Functions (CSF) of [START_REF] Genuzio | Fast scalable construction of ([compressed] static | minimal perfect hash) functions[END_REF] do not properly deal with datasets generated by low-entropy distributions, in particular with entropy smaller than 1. This case occurs when the dataset has a dominant value representing a large fraction (say, more than a half) of all values. This is typically the case with genomic k-mer count data, especially whole-genome data, where a very large fraction of k-mers occur just once. For example, in E.Coli genome (≈5.5Mbp), about 97% of all distinct 15-mers occur once, and only the remaining 3% of 15-mers occur more than once. For such datasets, the method of [START_REF] Genuzio | Fast scalable construction of ([compressed] static | minimal perfect hash) functions[END_REF] does not approximate well the empirical entropy, as it cannot achieve less than 1 bit per key. Here we propose a technique to circumvent this deficiency in order to achieve, in combination with CSFs of [START_REF] Genuzio | Fast scalable construction of ([compressed] static | minimal perfect hash) functions[END_REF], a compression close to the empirical entropy.

We build a Bloom filter for all k-mers whose value is not the dominant one, and then construct a CSF on all positives (i.e. true and false positives) of this filter. At query time, we first check the query k-mer against the Bloom filter and, if the answer is positive, recover its value with the CSF.

Formally, let K 0 be the k-mers with the most common frequency. Let |K 0 | = α|K|. Assume that our Bloom filter implementation takes C BF log 1 ε bits per key (a standard value is C BF = log e ≈ 1.44) and our CSF implementation takes C CSF bits per key. As explained earlier, C CSF depends on the data, however, for the purpose of this section, we abstract from this dependency. In Sec. 6 below, we will specify C CSF for the implementation we use.

We store keys K \ K 0 in a Bloom filter B and build a CSF for (K

\ K 0 ) ∪ F P B (K 0 ). The total space is C BF (1 -α)|K| log 1 ε + C CSF |K|((1 -α) + εα). ( 1
)
The Bloom filter enables space saving only if α is sufficiently large. To decide if we need a Bloom filter, we have to verify if the inequality

C BF (1 -α)|K| log 1 ε + C CSF |K|((1 -α) + εα) < C CSF |K|. (2)
holds for some ε < 1. Note again that C CSF on the left and right sides are not exactly the same in reality, however assuming them the same is not reductive because of specificities of the CSF implementation we use. We will elaborate further on this later on. Then (2) rewrites to

C BF C CSF 1 -α α log 1 ε + ε < 1. (3)
Using simple calculus, we obtain that if

C BF C CSF 1-α α > ln 2 (that is, C BF C CSF 1-α
α log e > 1), then (3) never holds for 0 < ε < 1. The left-hand side of (3) reaches its minimum for

ε 0 = C BF C CSF 1 -α α log e, (4)
and this minimum is smaller than 1 if ε 0 < 1. We conclude that in order to decide if a Bloom filter enables space saving, we have to check the value ε 0 . If ε 0 ≥ 1, we do not need a Bloom filter, otherwise we need one with ε = ε 0 . This shows that a Bloom filter is needed whenever

α > C BF log e C CSF + C BF log e (5)
For C BF = C CSF , this gives α > 0.59.

In the rest of the paper we use the term Bloom-enhanced Compressed Static Function, BCSF for short, to speak about CSF possibly augmented by a prior Bloom filter, as described in this section. Algorithm 1 summarizes the computation of the BCSF data structure.

4

Using minimizers

Bucketing

A key idea to reduce the computational burden of counting k-mers, is to use minimizers to bucket k-mers and split the counting process across multiple tables (cf e.g. [START_REF] Kokot | KMC 3: counting and manipulating k-mer statistics[END_REF]).

Data: A counting table f between keys and (integer) values

Result: A BCSF for f Compute R, the k-mer spectrum of f ; Compute ε with (4); if ε < 1 then let K 0 ⊆ K be the k-mers with the most common item in R; C = K \ K 0 ; Initialise Bloom filter B of ⌈log(e)|C| log 2 ( 1 ε )/⌉ bits; Insert C into Bloom filter; Compute E = F P B (K 0 ); S = C ∪ E; else S = K end Construct CSF for S;
{µ m (q) | q ∈ K} be the set of minimizers of all k-mers of K of a given length m < k. We map the input set K onto the (smaller) set M m (K). To each minimizer s ∈ M m (K), corresponds the bucket {f (q) | q ∈ K, µ m (q) = s}. We call a minimizer and the corresponding bucket ambiguous if this set contains more than one value. The guiding idea is to replace f by a mapping g of M m (K) to N. Querying value f (q) for a k-mer q ∈ K will reduce to first querying g(µ m (q)) and then possibly "correcting" the retrieved value. In other words, for each bucket, we replace its set of counts with one representative value and we split the query into two operations: retrieving the representative from the buckets and correcting to reconstruct the original value. The rationale is that k-mers having the same minimizer tend to have the same count allowing multiple values to be dealt with by a single bucket.

We consider two implementations which differ on how the representatives are chosen and how corrections are applied. In the first implementation, that we name FIL (from FILtration, see Algorithm 2), g(s) is defined to be the majority value among all values of its bucket, ties resolved arbitrarily. In particular, if s is a non-ambiguous minimizer then g(s) is set to the unique value of the bucket. In practice, computing the majority value may incur a computational overhead as this requires storing bucket values until all values are known. An option to cope with this is to use the "approximate majority" computed by the online Boyer-Moore majority algorithm [START_REF] Boyer | MJRTY -A Fast Majority Vote Algorithm[END_REF].

We then store a "correcting mapping" h : K → N defined by h(q) = f (q)-g(µ m (q)). That is, we construct another counting table h where each k-mer is associated to the correction factor h(q), which, added to the representative g(s) results in the original count c. Both mappings g and h are stored using BCSFs.

The rationale for this scheme is that, due to properties of minimizers, h(q) is supposed to be often 0, which makes h well compressible using BCSF. Note that because of the majority rule, 0 will always be the majority value of h. Therefore, the Bloom filter of the BCSF storing h (if any) will hold k-mers q with f (q) ̸ = g(µ m (q)) (i.e. h(q) ̸ = 0). Then the CSF will store h restricted to k-mers with h(q) ̸ = 0 together with a subset of k-mers (false positives of the Bloom filter) for which h(q) = 0.

In our second implementation, named AMB (from AMBiguity, see Algorithm 3), for non-ambiguous minimizers u, g(u) is again defined to be the unique value of the bucket. For ambiguous minimizers v, we set g(v) = 0, where 0 is viewed as a special value marking Algorithm 2 FIL construction algorithm.

Data: A mapping f of keys to (integer) values, a minimizer length m 0 Result: FIL compressed structure Sort L by increasing order; T = f ; Initialise an array A of buckets; for (q, c) in f do z = µ m0 (q) Insert c into g(z); end for b in A do Select representative r of bucket b by majority rule; end Compress A by using BCSF; Create output table O; for (q, c) in f do if g(µ m (q)) ̸ = c then Write q and c -g(µ m (q)) to O; end end Compress O by using BCSF; ambiguous buckets (k-mers with count 0 are not present in the input). This has the disadvantage of providing no information about the values of ambiguous buckets, and also of making g less compressible (because of an additional value). On the other hand, this has the advantage of distinguishing between ambiguous and non-ambiguous buckets and allows the query to immediately return the answer for k-mers hashing to non-ambiguous buckets. As a consequence, unambiguous k-mers are not propagated to the second layer, and if g(µ m (q)) ̸ = 0 it can be immediately returned as f (q). We then have to store mapping f restricted only to k-mers from ambiguous buckets, which we denote f . Both mappings g and f are stored using BCSFs.

Cascading

An intermediate layer corresponding to a minimizer length m < k, introduced in Section 4.1, can be viewed as a "filter" providing values for some k-mers and "propagating" the other k-mers to the next layer. Therefore, both implementations can be cascaded into more than one layer. This construction is reminiscent of the BBHash algorithm [START_REF] Limasset | Fast and Scalable Minimal Perfect Hashing for Massive Key Sets[END_REF] or to cascading Bloom filters from [START_REF] Salikhov | Using cascading Bloom filters to improve the memory usage for de Brujin graphs[END_REF].

For

m 1 < m 2 < ...m ℓ ≤ k, each layer i is then input some map f i-1 defined on a subset of k-mers K i-1 ⊆ K (f 0 = f , K 0 = K)
and outputs another map f i defined on a smaller subset

K i ⊆ K i-1 . Each layer stores a bucket table for minimizers M mi (K) = {µ mi (q) | q ∈ K i-1 }.
The specific definition of f i and K i depends on the implementation.

The multi-layer scheme is particularly intuitive for the AMB implementation, where each layer stores a unique value for non-ambiguous minimizers and a special value 0 otherwise. In this case, K i consists of those k-mers of K i-1 hashed to ambiguous buckets, and f i is simply a restriction of f to those k-mers. Algorithm 3 shows a pseudo-code of multi-level AMB extended to the approximate case (see Section 5 below). The multi-layer version of the FIL scheme is shown in Appendix (Algorithm 4).

Experimental results

We report experiments on three datasets, two with lower and one with higher empirical entropy. The first is the k-mer counts computed on the Sakai strain of E.Coli from [START_REF] Yi | Co-phylog: an assembly-free phylogenomic approach for closely related organisms[END_REF] (NCBI accession number B000007). The second one is a full genome of C.Elegans, strain Bristol N2 downloaded from RefSeq (accession number GCF_000002985.6). The last one is the whole dataset from the same paper [START_REF] Yi | Co-phylog: an assembly-free phylogenomic approach for closely related organisms[END_REF], hereafter referred to as "df", of k-mer "document frequencies" across 29 E.Coli genomes made of approximately 25 million k-mers. Here the document frequency of a k-mer is the number of genomes containing this k-mer.

Experiments were performed on a machine equipped with an Intel ® Core ™ i7-4770k (Haswell), 8 GB of RAM and Kubuntu 18.04. All construction code is written in python, except for the CSF part which is handled by a simple Java program using Sux4J [START_REF] Genuzio | Fast scalable construction of ([compressed] static | minimal perfect hash) functions[END_REF]. Time measurements are performed by a program written in C using the code provided by Sux4J for reading and querying its CSFs. We use xxHash 1 as µ m (q) to define an ordering over the minimizers of a given k-mer q. All code is available at https://github.com/yhhshb/locom. git.

We only report the best methods for each case with the following naming convention: CSF: baseline CSF implementation from Sux4J. BCSF: extended CSF with Bloom Filter from Section 3. It may get reduced to a simple CSF if the Bloom Filter is not useful. FIL m 1 k: our first implementation, saving into each bucket a majority-selected representative and saving corrections into its second layer. FIL m 1 m 2 k: same as before but with an additional layer. AMB m 1 k: our second implementation, selecting each representative by minimum and marking colliding buckets with a special value. AMB m 1 m 2 k: same as before but with an additional layer.

In order to apply equation (4), we have to have estimates of C BF and C CSF , that is, estimates of the number of bits per element taken by our implementations of Bloom filter and CSF. For C BF , we have C BF = 1.44 corresponding to the theoretical coefficient. For C CSF , we empirically estimated the value as a function of the empirical entropy H 0 of experimental data, and obtained the following estimate:

C CSF = 0.22H 2 0 + 0.18H 0 + 1.16, if H 0 < 2 1.1H 0 + 0.2, otherwise. (6)
To better understand how different minimizer lengths affect the final compression ratio, we ran FIL and AMB on all possible combinations of 2 and 3 minimizers lengths for k = 10,11,12,13,15,18,21. As mentioned earlier, simple CSF takes more than 1 bit/k-mer, which is considerably larger than the entropy of our data. Bloom-enhanced CSF (BCSF) considerably reduces space bringing it closer to the entropy value. For relatively small k's (k = 13) AMB and FIL give almost the same results as BCSF, that is, bucketing is not helpful. For larger k's, however, minimizer-based schemes, AMB and FIL, lead to a reduction of space, eventually breaking the entropy barrier for larger values of k (k = 18, 21). This demonstrates that for larger k's, minimizers provide an effective way of factoring the space of k-mers in such a way that k-mers with equal counts tend to have the same minimizer.

Compression of skewed data

More in detail, for larger k, the overwhelming majority of buckets are unambiguous (e.g. more than 99% of them, for k = 18, m = 13). As a consequence, AMB "filters out" a very large number of k-mers at the first layer, propagating to the second layer only a small fraction of them -those corresponding to ambiguous buckets. The special collision value then becomes the dominant value of the bucket table, making it highly compressible with BCSF. Note also that due to the skewedness of the distribution, i.e. the prevalence of one value, the k-mer tables of the last layer are well compressible as well. Altogether, this enables breaking the empirical entropy lower bound. The situation is similar for FIL: its first layer is even better compressible than the one of AMB, due to the absence of the additional special value which makes the table of AMB slightly less compressible. On the other hand, the BCSF of the second layer table of FIL turns out to take more space than that of AMB. This is because its Bloom filter operates on the large set of all k-mers, which implies a very small value of ε to keep the set of false positives under control, and as a consequence, a relatively large Bloom filter. Overall, FIL turns our to yield a slightly larger space.

The advantages of AMB and FIL tend to vanish for smaller values of k. For small k's, none of the methods beats the empirical entropy, which means that minimizers do not provide an efficient mean to factor the space of k-mers according to count values. We observe that in this case, applying BCSF to the input table provides the most efficient solution.

Since longer k-mers lead to more skewed data, and by extension, to a smaller entropy, both AMB and FIL better compress whole genome count tables for increasing ks. In order to test our algorithms in a more complex and challenging situation, we chose to compress the reference genome of C.Elegans (around 100Mbp). Taking into account the considerations presented previously, we quickly found that the best results for AMB and FIL were given by k = 18 when using 2 layers. We randomly chose m 1 = 19 and m = 21 for three-layer AMB and FIL, respectively. Figure 2 demonstrates that our algorithms are not limited to bacterial genomes. Larger values of k only reduce the entropy of the data, leading to more succinct representations whereas simple CSF could not go below 1.2 bits/k-mer.

Compression of higher entropy data

With very skewed data, collisions of k-mer counts may happen between unrelated k-mers simply because one counter value strongly dominates the spectrum. In order to demonstrate that minimizers are useful as well for less skewed distributions than whole genome count tables, we applied our methods to the df dataset, see Figure 3. The use of minimizers for larger k's, proves to be beneficial again, with AMB and FIL requiring much less space that the empirical entropy of the data. A similar scenario to the previous case represents itself for relatively small k (k = 13), for which both AMB and FIL do not have an advantage over a simpler (B)CSF. For even smaller k-mers (B)CSF remains the best option (results not shown).

The seemingly erroneous exceptions (BCSF taking more space than simple CSF) are explained by the approximation carried by formula (2) (assumption of equal values of C CSF in both sides).

Approximate counts

In many applications, it is acceptable to tolerate a small absolute error in retrieved counts. Figure 5 shows that, in such case, it is possible to achieve a better memory consumption than simple CSFs even for small values of k. For medium values of k, neither too small nor too big, approximation can lead to the smallest compressed size, even when δ = 1. Unlike Figure 4, reported here for comparison, Figure 5 does not use the best minimizer lengths found for AMB with two layers. This is because we want to use δ to remove ambiguity from as many buckets as possible in each layer, by ignoring small collisions. For small k's this would not be possible with the best solutions found before, because minimizer lengths 4, AMB is able to break the empirical entropy lower bound when small errors are acceptable.

WA B I 2

are too small to allow unambiguity even for δ > 0. Therefore, in this case only, we just use contiguous minimizer lengths for each layer (e.g. if k = 10, layers will be 8, 9, 10 for three-layer AMB).

Another interesting observation about the approximate case is that AMB with three layers is substantially better than AMB with two layers only for k = 12 and k = 13. For k = 10 and k = 11 both versions give almost the same results.

Query speed

Figure 6 shows query time averaged over all distinct k-mers, in ns/k-mer. Simple CSFs, not surprisingly, are the fastest method, with BCSF having a negligible effect on the average query speed. On the other hand, bucketing has a tangible effect on performance, with speed negatively affected by additional layers. For short k-mers, both FIL and AMB are slower than the simple CSF by a factor equal to their number of layers.

The situation is different for larger k's where AMB is only marginally slower than a bare-bones CSF. This is because most queries are solved without accessing all layers every time, thanks to unambiguous buckets. Two layered FIL, on the other hand, gives almost constant average query times across all test, since all queries have to access both of its layers to reconstruct the exact count value. We did not perorm tests for FIL with 3 layers because it will always be slower than the two layered version.

Choosing minimizer lengths

In all reported cases, good minimizer lengths for the first layer (m 0 ) follow the rule: m 0 > m s = (log 4 (|G|) + 2) with |G|, the size in base pair of the genome. Smaller m 0 , are no longer capable of partitioning k-mers in a meaningful way. Furthermore, space tends to first monotonically decrease to a minimum for increasing minimizer lengths, to increase again once the optimal value is passed. It is therefore possible to find the minimum by sequentially trying all possible minimizers greater than m s and stop as soon as the compressed size starts to increase again.

Our results also show how multiple layers have a marginal effect on final compression sizes. In case of AMB, using three layers is always helpful, compared to the two-layer case. Best results are usually achieved for combinations including the best minimizer length obtained for the two-layer case.

On the other hand, FIL with three layers seems to be advantageous only for low entropy data, performing worse that its two-layer counterpart on the df dataset and for small k's.

Conclusions

In this work, we introduced three data structures to represent compressed k-mer count tables.

Our BCSF algorithm combines Compressed Static Functions, as implemented in Sux4J software [START_REF] Genuzio | Fast scalable construction of ([compressed] static | minimal perfect hash) functions[END_REF], with Bloom Filters. This allows for a much better compression for skewed distributions with empirical entropy smaller than 1. Note that to our knowledge, this is the first time that CSFs are used in bioinformatic applications. We also provide a method to dimension the Bloom filter in a BCSF in order to minimise the final space. Our two other algorithms, FIL and AMB, pair BCSF with a bucketing procedure where count values are mapped into buckets according to minimizer values of respective k-mers. This locality-sensitive hashing scheme allows us to efficiently factor the space of counts, which leads to breaking the empirical entropy lower bound for large enough k's. FIL and AMB use slightly different strategies in decomposing the input table across minimizer layers.

Our last contribution is an extension of AMB to the approximate case, gaining more space at the expense of a small and user-definable absolute error on the retrieved counts.

We validated our algorithms on three different datasets, two fully assembled genomes (E.Coli and C.Elegans), and one document frequency example, for different k-mer lengths showing how BCSF, AMB and FIL behave in different situations. FIL and AMB have a clear advantage when minimizers are long enough to bucket k-mers in a meaningful way, for both skewed and high entropy data. When it is not possible to define a long-enough minimizer length, the advantage of using intermediate minimizer layers vanishes, and simple CSF and its BCSF provide a better solution.

At query time, CSF and BCSF are the fastest methods requiring about 100ns on average for a single query. For a fixed number of layers, AMB is faster than FIL in all situations when minimizers are useful. FIL becomes faster than AMB only for those cases when both algorithms achieve worse compression ratios than simple (B)CSF.

We consider this study to be the first step towards designing efficient representations for kmer count tables occurring in data-intensive bioinformatics applications. One possible future direction is compression of RNA-Seq experiments where counts may translate expression levels of genes. Another example is metagenomics where different species may be present with different abundances which can be captured by k-mer counts. In such applications, efficient representation of k-mer counts can be particularly beneficial.

B

WA

  Here we use the same principle to bucket count values instead of k-mers themselves. Let M m (K) =

Figure 1

 1 Figure 1 reports memory usage for k = 13, 15, 18, 21, when compressing the Sakai dataset.As mentioned earlier, simple CSF takes more than 1 bit/k-mer, which is considerably larger than the entropy of our data. Bloom-enhanced CSF (BCSF) considerably reduces space bringing it closer to the entropy value. For relatively small k's (k = 13) AMB and FIL give almost the same results as BCSF, that is, bucketing is not helpful. For larger k's, however,

Figure 1

 1 Figure 1Results for the Sakai dataset for big values of k. For presentation purposes, H0 is represented as an additional red column in each subgroup.

Figure 2

 2 Figure 2 Results when compressing the reference genome of C.Elegans.

Figure 4

 4 Figure 4Space usage for the Sakai dataset with small k when using AMB (FIL is slightly worse and was omitted). Minimizer lengths vary between 1 and 5 indicating that the best option is to use a simple (B)CSF.

Figure 6

 6 Figure 6Average query time for AMB with 2 and 3 layers and FIL with 2 layers.

Figure 8

 8 Figure 8 Space usage across all values of k, for the df dataset.

2 0 2 1 8:10 Compressed k-Mer Count Tables

		1.0 1.2 1.4	1.34	0.87	0.87	0.87	0.90	0.91	1.23					1.22						1.22	H0 CSF BCSF AMB 2 layers AMB 3 layers FIL 2 layers FIL 3 layers
	bits / k-mer	0.6 0.8	0.61
		0.2 0.4						0.24	0.34	0.26	0.26	0.29	0.29	0.19	0.26	0.11	0.10	0.13	0.13	0.18	0.25	0.08	0.07	0.10	0.10
		0.0			13				15		k			18			21

1 https://github.com/Cyan4973/xxHash

WA B I

0 2 1 8:12 Compressed k-Mer Count Tables

  Compressed space usage for the high entropy df dataset.

	bits / k-mer	2 3 4	3.95 4.43 4.43 4.43 4.43 4.43 4.43	3.58 4.07 4.13 3.23 3.15 3.63 4.13	2.25 2.11 2.59 2.61 4.10 3.97 3.48	1.94 1.80 2.29 2.29 4.06 3.89 3.41	1.84 1.71 2.18 2.20 4.00 3.82 3.36	H0 CSF BCSF AMB 2 layers AMB 3 layers FIL 2 layers FIL 3 layers
		1
		0	13			15				18 k					21			24
	0 1 2 3 Figure 3 10 bits / k-mer 4 3.88 4.38 4.38	4.38	4.38	2.27	2.61	11 2.68	2.67	2.67	k	1.20	1.62	12 1.61	1.61	1.61	0.61	1.34	13 0.87	0.87	0.87	H0 CSF BCSF AMB 2 layers AMB 3 layers

  Space usage when using the approximated version of AMB. Entropy (red columns) and CSF (blue columns) are reported for comparison. Unlike Figure

	3.88 4.38 4.42 4.16 3.83 3.44 3.08 4.45 4.18 3.83 3.44 3.02	2.27 2.61 2.35 1.87 1.46 1.16 0.94 2.38 1.80 1.35 0.99	1.20 1.62 1.04	1.01	1.34	H0 CSF AMB 2 layers, d=1 AMB 2 layers, d=2 AMB 2 layers, d=3 AMB 2 layers, d=4 AMB 2 layers, d=5 AMB 3 layers, d=1 AMB 3 layers, d=2 AMB 3 layers, d=3 AMB 3 layers, d=4 AMB 3 layers, d=5
		0.74	0.69 0.52 0.44 0.40	0.55 0.32 0.20 0.14	0.61	0.45 0.34 0.31 0.30 0.29 0.37 0.19 0.14 0.11 0.11
	Figure 5

  Space usage across all values of k, for the Sakai dataset.

			Additional figures
	bits / k-mer	2 3 4	3.88 4.38 4.38 4.38 4.38 4.41 4.47	2.27 2.61 2.68 2.67 2.67 2.68 2.68	1.62 1.61 1.61 1.61 1.65 1.67				H0 CSF BCSF AMB 2 layers AMB 3 layers FIL 2 layers FIL 3 layers
							1.20	1.34		1.23	1.22	1.22
		1						0.61	0.87 0.87 0.87 0.90 0.91
		0	10		11		12		13 k	0.24	15 0.34 0.26 0.26 0.29 0.29	0.19	18 0.26 0.11 0.10 0.13 0.13	0.18	21 0.25 0.08 0.07 0.10 0.10
	bits / k-mer	2 3 4 5	2.68 3.07 3.37 3.28 3.28 3.46 3.51	4.46 5.01 5.01 5.01 5.01 5.01 5.16	4.40 4.94 4.94 4.94 4.94 4.94 4.94	3.95 4.43 4.43 4.43 4.43 4.43 4.43	3.58 4.07 4.13 3.23 3.15 3.63 4.13	2.25 2.11 2.59 2.61 4.10 3.97 3.48	1.80 1.94 2.29 2.29 4.06 3.89 3.41	1.84 1.71 2.18 2.20 4.00 3.82 3.36	H0 CSF BCSF AMB 2 layers AMB 3 layers FIL 2 layers FIL 3 layers
		1
		0	10		11		12	13		k	15	18	21	24

Figure 7

Funding Gregory Kucherov: partially funded by RFBR project 20-07-00652 and joint RFBR and JSPS project 20-51-50007.

: https://github.com/yhhshb/locom.git

Compressed k-Mer Count Tables

Algorithm 3 AMB multi-layer construction algorithm. Exact AMB can be obtained by setting δ = 0.

Data: A mapping f of keys to (integer) values, a list L of minimizer lengths, a maximum absolute error δ Result: One BCSFs for each layer Sort L by increasing order;

Initialise an array A of buckets;

Extension to approximate counts

In addition to cascading, the AMB implementation can also be easily extended to work as an approximation algorithm. Consider, to this end, the layered bucketing procedure desribed in 4.2. In the exact case, a bucket is marked as colliding whenever it contains two or more distinct count values. In the approximate case, a collision is defined if a bucket contains a pair of counts, c i , c j such that |c i -c j | > δ with δ a pre-defined maximum absolute error. With this modification, the algorithm guarantees to output a value within the absolute error δ from the true count.

Implementing this modification is simple when the majority is computed with the Boyer-Moore majority vote algorithm. Another option is to define g(s) to be the minimum, instead of majority. The rationale of using minimum is the decreasing behavior of k-mer spectra which implies that smaller counts are more frequent and therefore more likely to constitute the majority. It is then sufficient to only remember the maximum max(s) and minimum min(s) values seen by each bucket and check if max(s) -min(s) > δ. If that is the case, then the bucket is marked as colliding, otherwise min(s) is chosen as representative. The latter solution is reported in Algorithm 3.

8:18

Compressed k-Mer

Write q and c -g(µ m (q)) to O; p q = p q + 1; end end α = (n -p q )/n; ϵ = (1 -α)/α; if ϵ < 1 then Initialise an empty Bloom Filter of size 1.44 log 2 (1/ϵ); Insert all elements of O into B; for (q, c) in T do if g(µ m (q)) = c and B(q) then Write q and c -g(µ m (q)) to O end end end T = O; end