Revisiting K-mer Profile for Effective and Scalable Genome Representation Learning
Authors: Abdulkadir Celikkanat
Andres R Masegosa
Thomas Dyhre Nielsen
Venue: NeurIPS 2024 spotlight (2024)
Keywords: metagenomic binning
genome representation learning
dna sequences
genome analysis
Primary area: machine_learning_for_other_sciences_and_fields
TL;DR: We propose a lightweight and scalable model for performing metagenomic binning at the genome read level, relying only on the  k-mer compositions of the DNA fragments.

Abstract: Obtaining effective representations of DNA sequences is crucial for genome analysis. Metagenomic binning, for instance, relies on genome representations to cluster complex mixtures of DNA fragments from biological samples with the aim of determining their microbial compositions. In this paper, we revisit k-mer-based representations of genomes and provide a theoretical analysis of their use in representation learning. Based on the analysis, we propose a lightweight and scalable model for performing metagenomic binning at the genome read level, relying only on the k-mer compositions of the DNA fragments. We compare the model to recent genome foundation models and demonstrate that while the models are comparable in performance, the proposed model is significantly more effective in terms of scalability, a crucial aspect for performing metagenomic binning of real-world data sets.

Revisiting K-mer Profile for Effective and Scalable Genome Representation Learning
Abdulkadir Çelikkanat Aalborg University 9000 Aalborg, Denmark abce@cs. aau dk
Andres R. Masegosa Aalborg University 9000 Aalborg, Denmark arma@cs. aau. dk
Thomas D. Nielsen Aalborg University 9000 Aalborg. Denmark tdn@cs. aau dk
Abstract
Obtaining effective representations of DNA sequences is crucial for genome analy- sis. Metagenomic binning, for instance, relies on genome representations to cluster complex mixtures of DNA fragments from biological samples with the aim of determining their microbial compositions. In this paper, we revisit k-mer-based representations of genomes and provide theoretical analysis of their use in repre- sentation learning. Based on the analysis, we propose lightweight and scalable model for performing metagenomic binning at the genome read level, relying only on the k-mer compositions of the DNA fragments. We compare the model to recent genome foundation models and demonstrate that while the models comparable in performance, the proposed model is significantly more effective in terms of scalability, crucial aspect for performing metagenomic binning of real-world datasets.
1 Introduction
Microbes influence all aspects of our environment, including human health and the natural environ- ment surrounding us. However, understanding the full impact of the microbes through the complex microbial communities in which they exist, requires insight into the composition and diversity of these communities [19
Metagenomics involves the study of microbial communities at the DNA level. However, sequencing complex microbial sample using current DNA sequencing technologies 27 rarely produces full DNA sequences, but rather mixture of DNA fragments (called reads) of the microbes present in the sample. order to recover the full microbial genomes, subsequent binning/clustering step is performed, where individual DNA fragments are clustered together according to their genomic origins. The fragments being clustered during the binning process consist of contiguous DNA sequences (contigs) obtained from the reads through (contigs are generally longer and less error- prror-prone than the reads).
This process is also referred as metagenomic binning [9 9]
a so-called assembly process 29
Metagenomic binning typically involves comparing and clustering DNA fragments using a distance metric in suitable genome representation space. State-of-the-art methods for metagenomic binning typically rely on representations that include or build on top of the k-mer profiles of the contigs [1 12 [8] These representations have mostly been studied from empirical perspective [6], although general theoretical analyses into their representational properties have also been considered 25 With A 4 (i.e.. (etra-nucleotides) 256-dimensional vector is used to describe the genome, each entry in the vector encoding the frequency of a specific k-mer (e.g., ACTG, ATTT) in the genome sequence. The k-mer representation of sequence thus has fixed size and is independent of sequence length and downstream analysis tasks, providing a computationally efficient representation.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

A more recent and popular line of research focuses on using approaches inspired by modern Large Language Models (L.. to derive more powerful representations of genome fragments. The goal is to replicate the suc- cess of LLMs used in natural language processing for genomic data. These models, known as genome foun- dation models, have seen numerous versions proposed
DNABERT-2
DNABERT-S
HARADDA DNABERI-3
Number of parameters (log (oggall (el
HYENADNA
recently 32 31.
Similarly to popular LLMs, existing genome founda- tion models utilize next-token prediction or masked- prediction approaches within tausfoormrr-bsee architec- tures, where the tokens to predicted are the nucleotides composing the genome fragments. These models, akin L.Mss, enable trainable and contextualized represen- tations that can be defined either in task-dependent aask-independent manner [32] According to standard- ized benchmarks, the embeddings derived from these foundation models have the potential to offer substantial improvements over those based on k-mmers (32). However, these embeddings are also computationally far more in- tensive, reducing their scalability in light of the massive amounts of data generated by modern sequencing tech-
OUrS(Nl)
OURS (POIS)
Figure 1: Number of parameters of the different evaluated models (log1o-scan) -scale..
nologies. For instance, 23 conducted -err-base metagenomic binning 28 9
samples from wastewater treatment plants, encompassing approximately 1.9 x 10 base pairs and resulting in the recovery of over 3700 high medium quality clsters/metaggnnome-ssemeem
genomes (MAGs).
this paper, we demonstrate how k-mer-based embeddings of genome fragments provide a scalable and lightweight alternative to genome foundation models. We revisit the theoretical basis of k-mers and offer a theoretical characterization of the identifiability of DNA fragments based on their mer profiles. For non-identifiable fragments, establish lower and upper bounds their edit distance using the 4 distance between their respective k-mer profiles. These findings offer theoretical justifications for k-mer-basse genome representations and hold potential significance beyond the scope of this study. Building on these theoretical insights, we propose simple and lightweight model for learning embeddings of genome fragments using their k-mer representations.
empirically assess the proposed embeddings on metagenomic binning tasks and compare their performance with large state-of-the-art genome foundation models. Our findings indicate that, while both sets of models produce comparable quality in terms of the MAGs recovered, the proposed models require significantly fewer computational resources. Figure demonstrates this by showing the number of parameters in our k-mer embedding methods compared to those in the state-of-the- genome foundation models. The k-mer-based embedding approaches involve models with several orders of magnitude fewer parameters.
The main contributions of the paper can be summarized as follows:
We provide a theoretical analysis of the k-mer space, offering insights into why k-mers as powerful and informative features for genomic tasks.
We demonstrate that models based k-mers remain viable alternatives to large-scale genome foundation models.
We show that scalable, lightweight models can provide competitive performance in the metagenomic binning task, highlighting their efficiency handling complex datasets.
The datasets and implementation of the proposed architectures can be found at the following address: http://gitttuub..o//bbbbeeeede http//ddwe..kkaaaaeeeeessttnneee
Backgroud and Related Works
When analyzing the microbial content of biological samples (e.g., soil samples or samples from the intestine), we deal with genomic material originating from multiple different species. For such

---

analyses, the general workflow consists of sequencing the DNA fragments in the sample, producing electrical signals that are subsequently converted into sequences of letters corresponding to the four DNA bases (A, C, T, G). During the sequencing process, the full DNA sequences are fragmented into smaller subsequences (called reads), resulting in millions or even billions of reads for each sample. Depending on the sequencing technology being used, reads are typically either classified as short reads (100-150 bases) or long reads (2k-30k bases), and while long reads are generally preferable, they are also more prone to translation errors.
Identifying the microbial composition of sample involves clustering the DNA fragments according to their genomic origin (a process referred to as metagenmoic binning) Clustering the DNA fragments relies not only on representation of the genome fragments, but typically also includes information about the read coverages in the sample, reflecting the relative abundances of the individual species that make up the sample [2..
For the current paper, the focus is on representations of DNA fragments. Existing works on metage- nomic binning typically either rely on predefined features (e.g.. ( [2) or, more recently, on genome foundation models (e.g.. [6 (32) for representing the DNA fragments. Predefined features for metagenomic binning include the k-mer frequencies of the genome (e.g., for k = the genome is represented by 256-dimensional vector), which have shown to exhibit a degree of robustness across different areas of the same genome 4 These k-mer vectors/profiles are either used as direct representations of the DNA fragments as in, e.g., МЕ METABAT2Ø9, VAMP [17. and SEMIBIN2 [18] in the spirit of WORD2VEC 14.
ir used for learning k-mer-basee embeddings [ 21
More recently, genome foundation models have also been proposed, which include DNABERT 8.
DNABERT-2 (31), HYENADNA [T6] and DNABERT-S [2). These foundation models provide embedding of the raw DNA fragments as represented by the sequences of four nucleotide letters.
In this work, we show that although the contextualized embeddings produced by foundation models provide a strong basis for downstream genome analysis tasks, the complexity the models also makes them less scalable to the vast amounts of data currently being generated by the state-of off-the-art art sequencing technologies. Consequently, we consider more lightweight models and explore the use and theoretical basis for models relying on k-mer representations of DNA fragments.
3 k-mmer embeddings
As we discussed in the previous section, the metagenomic binning problem aims to cluster the sequences (i.e. reads) according to their respective genomes. For the sake of the argument, denote with f R + [K] the function that maps each read to the (index) ground-truth genome from which the read originates. Here, we use R to denote the set of reads where each read is supposed to originate from one of the K genomes.
Performing clustering directly on the reads has been shown to provide very poor performance 11] mainly because reads lie in a complex manifold in a very high dimensional space. A well-tested approach is to instead embed each of the objects in a lower dimensional space, known as the embedding or latent space, whose structure is much closer to Euclidean space, where clustering is far simpler to perform. More formally, we characterize the problem as follows:
Problem Definition, Let R Σ be finite set of reads with a genome mapping function & where Σ = (A, C,T. G). For given threshold value E R+,, the objective is to leam an embedding function : R - Rd that embeds reads into a low-dimensional metric space (X, dx), usually a Euclidean space, such that (x)) < y if and only if f(r) f(q) for all reads r, q R where d <<< R
Once establish an embedding function like the one described earlier, it becomes, in principle, straightforward to employ a simple clustering algorithm to bin or group the reads. However, for this purpose, the embedding function È must be capable of distinguishing the intrinsic features of the various genomes, producing similar latent representations for reads that originate from the same genomes. In the following subsection, we will discuss novel theoretical arguments that help to better understand why k-mer profiles are a powerful representation of reads.
In practice, the reads are not clustered directly. Instead overlapping reads are first combined into so-called contigs through assembly process (10).
3

---

3.1 k-mers are powerful representation of reads
The use of k-mer profiles to represent reads helps overcome several challenges encountered during the clustering or binning of reads. These challenges include (i) the variation in read lengths in practical scenarios, such as in genome sequencing where read lengths can differ significantly, (ii) ambiguity in read direction, which is result of reads lacking inherent directionality, complicating the analysis, and (iii) the equivalence of a DNA sequence to its complementary sequence because DNA composed of two complementary strands, meaning the information from one strand corresponds to that from its complementary strand.
An initial important question concerns the identifiability of reads, which examines to what extent different reads share the same k-mer profiles. We will call the reads that can be uniquely reconstructed from their given k-mer profile as identifiable and this is crucial because if many reads possess the same k-mer profile, they will invariably be grouped into the same cluster, potentially leading to the loss of significant information. In this context. Ukkonen et al. 255 conjectured in their study on the string matching problem that two sequences sharing the same k-mer profile could be transformed into one another through two specific operations, and this claim was later proved by Pevzner (20). However, these specified operations fail to consider cases where sequences include repeated overlapping occurrences of the same k-mer.
In this regard, in Theorem 3.1 we demonstrate that a read can be perfectly reconstructed from its k-mer profile under certain conditions, which become less restrictive with larger l values. In the following theorem, we use r,, with < j. to denote any subsequence of a read that includes consecutive nucleotides from position i to position j.
Theorem 3.1. Let be read of length E. There exists no other distinct read having the same k-mer profile if and only if it does not satisfy any of the following conditions:
1. ri Tk-1 rt-k-2 Tg and ri F for some 1 < i < k-
2. r4 ... k = r3. 1. - and rgg " T = -hh- -h-kk-2 for some indices 1 I
9 マ - k + where ritk-1 -g-1 + rjtk-1 ... -hh-1-
3. r.... r r3 T k-2 .h. Th+k-2 for some indices 1 S < < h t- k- where Ti4k-1 ... rー *
Tj+k-1 ... --
Proof. The proof is omitted due to the limitation on the number of pages. Please see the appendix.
is important to note that it is always possible to find an optimal k value that ensures that each read does not meet any of the previously mentioned conditions and, in consequence, becomes identifiable. Clearly, when & is equal to the length of the reads, all reads become identifiable. However, as increases, the k-mer profiles become more prone to errors, and it will be harder to identify the underlying patterns in the reads (in the extreme case scenario where k equals the length of the reads, each read will correspond the results show that even with smaller l values, identifiability could still be potentially achieved not by all but by some of the reads. We hypothesize that the effectiveness of k-mer representations stems, in part, from this fact.
unique k-mer). Thus, using large values of l is impractical. However,
Another perspective to consider is the extent to which two similar reads share similar k-mer profile. The identifiability approach from the previous result addresses this issue by establishing that if two reads have identical profiles, then the reads themselves are identical. However, identifiability is limited by the conditions outlined in Theorem 3.1 which may not always be met. The observation given in Proposition 3.2 provides broader and more applicable finding.
demonstrates that if two k-mers are similar according to the I distance, then the corresponding reads are also similar according to the Hamming distance in the read space. It is important to note that both the 4 and Hamming distances are natural measures for evaluating similarity in this context. Technically speaking, we show that the ( distance between k-mer profiles can be upper and lower bounded by the Hamming distance between the corresponding identifiable reads, so they are Lipschitz equivalent spaces. In the next result, : R x E + N denotes the function showing the number of occurrences of a given k-mer in a given read. For simplicity, we use the notation, Cr. to indicate the k-mer profile vector of a read whose entries are ordered lexicographically. In other words, cy (x) is the number of appearances of x e * in read E R.
4

---

Proposition 3.2. Let Mi = (Be,dz) and M2 = -N*%1, . II)) be the metric spaces denoting the set of identifable reads and their corresponding k-mer profiles equipped with edit and & distances, respectively. The k-mer profile function, e: M1 + M2, mapping given any read, r, to its corresponding k-mer profile, Cr = c(r), a Lipschitz equivalence, i.e. it satisfies
Vr,q E (rdz(r;9)) S l|cr - calli S (r, for on = 1/8 and Or k| so M1 and M2 are Lipschitz equivalent.
Proof. The proof is omitted due to the limitation on the number of pages, Please see the appendix.
Unfortunately, when one a clustering algorithm directly top of the raw k-mer profiles, the results are not competitive as demonstrated in numerous studies, see, e.g.. [31]. Instead, we will consider methods for learning embeddings of k-mer profiles and, more generally, genome sequences.
3.2 Linear read embeddings
Below we consider two simple genome sequence models defining the embedding of read as a linear combination of the k-mer representations. The first model (k-mer profile) does not involve any learning procedure and it simply defined by the k-mer counts of the read, whereas the second model (Poisson model) expands on the k-mer profile model by explicitly representing the dependencies between k-mers. Both models will serve as baselines for more complex models.
k-mer profile: First, consider the definition of k-mer profiles:
EXMER (I)
Σ
cx)xzx
(2)
XEE*
where zx represents the canonical basis vector for the k-mer x E E i.c (Zx E ((u up=t)) E
{0, 1)12=1 Σ, 04 =1 )
As previously mentioned, our primary objective is to represent reads in a lower-dimensional space, where their relative positions in latent space reflect their underlying similarities. By Equation [ the k-mer profile of a read can also be considered as its embedding vector, but its entries are not independent. In other words, if change one letter in read, it can affect most k different k-mer counts. In this regard, it might be possible to learn better representations than simple k-mer profiles.
Poisson model: For given read in the read are not independent. For instance, the k-mers located at position indices i and i + 1, (i.c. x -i+ and y := Ti-1 &.+ share the same substring Ti+1 "..1- Ti+--1, which highlights the inherent dependencies between k-mers. Hence, we will learn the representation, 2x. of each k-mer, x, instead of using the canonical basis vectors. We propose model the co-occurrence frequency of specific k-mer pairs within a fixed window size, w, using the Poisson distribution. In other words, 0x.y Pois(>x.y), where Ox.y indicates the number of co-appearances of k-mers, x = ri ....... Titk-1 and y == rj Tj+k-1 for i - jl S w.
(ri...re) it is easy to that the consecutive k-mers
In order to achieve close representations for highly correlated k-mers, and distant embeddings for the dissimilar ones, we define the rate the Poisson distribution as follows:
Xx.y
exp
(- 1 2y 11²)
The loss function used for training the embeddings with respect to the reads is simply defined in terms of the Poisson distribution model of the k-mer pairs:
Crois ((xx.Ix.veEs (aatevexx/Zzzxrrr (zxbxEr*)
Σ
Ox zyl1 + exp (-1lzx - 1y) (4)
XEX Y
where Ox.y is the average number of co-occurrences of k-mers and y per read within window of size w in the dataset. Once we have obtained the k-mer embeddings, we can obtain the read embeddings by combining the ie-me embeddings with their respective occurrence counts, given in Equation More specifically, the embedding of read, r, is given by
Eyois (r) = E EXE (x)
Cr (x()xxx
(5)
XEDA
where (Zxlxxxx corresponds to the learned k-mer embeddings of Eq.
5

---

MATAS THE GAGOTS
Ail
a
AMA
CAOOTA AN ATTOO
3) Read Ditaace
8) Posttive and Negative Pairs
Bi Kotter Procies
(v) Learning Representtiioss
Bizning
Figure 2: Illustration of the non-linear k-mer embedding approach described in Section 3.3
3.3 Non-linear read embeddings
In the experimental section, we will show that the linear k-mer embeddings described previously outperform k-mer profiles in metagenomic binning tasks. However, the literature machine learning frequently emphasizes that non-linear embeddings typically provide superior results when the data, such as genomic sequences in this context, exist in complex high-dimensional manifold spaces [3
We design simple and efficient neural network architecture utilizing supervipe contrastive learning. Our model consists of two linear layers, and the first one takes k-mer profile features as input, projecting them into a 112-dimensional space. A sigmoid activation function is applied, followed by a batch normalization operation and a dropout with a ratio 0.2. The second layer maps them into the final 256-dimensional embedding space.
Our approach is inspired by previous methods in the context of metagenomic binning the contig level [8]. The primary aim here is not to introduce a novel methodology for learning embeddings to demonstrate that simple non-linear embeddings, built upon k-mer representations, can match the effectiveness of existing state-of-the-art genomic foundation models for metagenomic binning tasks while being significantly more scalable.
The methodology is graphically depicted in Figure 2 Initially, we create positive and negative pairs of read segments using the dataset provided. To create positive pair, we split an existing read into two equal-sized segments. Conversely, a negative pair is formed by combining two segments originating from the splitting of two distinct reads chosen at random. Subsequently, for each pair, we calculate the k-mer profile for the two segments in the pair. These two k-mer profiles are then input into the same neural network, which maps them to two vectors within embedding space. The loss function evaluates the quality of these two embeddings; it penalizes distant embeddings in positive pairs and close embeddings in negative pairs. The learning process involves optimizing the neural network's weights to minimize this loss function across numerous positive and negative samples.
Let R [r:).V be the of reads and rf and rí are the segments indicating the left and right halves of read r; E R. As described above, we use these segments to construct the positive and negative pair samples required for the self-supens supervisdd contrastive learning procedure. Let ( rj. Mty (6,)ez be the set of triplets where I S [N] [N] is the index set for the pairs, and the symbol, Viş E {0, 1} is used to denote whether (r" r is positive sample (i.e. +1), or negative (i.e. 0). The positive label means that the pair corresponds the left and right segments of the same read, while negative label indicates they are segments from different reads. Then, we define the loss function as follows:
Lxx. (1Us) = I
Σ (GJ)ZI
Vij Doilogpe log + (1 (1-9is) log(1 Pij)
where Q indicates the all trainable weights of the neural network. Here, the success probability, Pij- corresponds to the case of positive pair, occurring when Vij +1, and computed as:
Pij = exp (-11Em. (1;) En (r,))l²)
where (x/( denotes the output embedding of the neural network for segment rÇ.

---

Synchetic:
Plant
Marine 5
KMER-COSINE
HYENADNA
DNABERT-2
DNABERT-S
(KMER-))
OURS(POIS)
(URS(NL)
1000
15X1
2001
101
410
301
60
1221
150
210
Syathetic
Plant
Macine
KMER-COSINE
HYENADNA
DNABERT-2
DNABERT' S
OURS(KMER-()
(URS(POIS)
(URS(NI.)
25
50 75 100 125
150
175 200
0 10
20
30
40
50
60
70
30
60
90
210 240 Species countt
120 150 180
Species count
Species countt
Fi Runges
(0.5, [.6
(1.6, 0.7]
(0.7, 0.8]
(0.8, 0.9)
(0.9, 1.0)
Figure 3: Evaluation of the models on multiple datasets for the metagenomic binning task. Each color represents the number of clusters within specific Fi score range, and the number of clusters with the highest quality highlighted in dark blue.
Given large number of distinct genomes (i.e., clusters), it is highly likely that negative pairs consist of segments from different genomes, they originate from different reads. Conversely, positive pairs are composed of segments from the same genome, as they originate from the same read. Consequently, the neural network's 's embedding function will learn to produce similar embeddings for k-mer profiles belonging to the same genome and different embeddings for k-mer profiles belonging to different genomes. demonstrated in the next section, this straightforward approach built k-mer profiles competes effectively with state-of-the-an genomic foundation models, which involve neural networks with several orders of magnitude more parameters.
4 Experiments
In this section, we will provide the details regarding the experiments, datasets, and baseline approaches that we consider to assess the performance the proposed linear and non-linear models.
Datasets. We utilize the same publicly available datasets used to benchmark the genome foundation models 33). The training set consists of million pairs of non-overlapping DNA sequences, each 10, 000 bases in length, constructed by sampling from the dataset, including 17, 636 viral, 5, 01 fungal, and 6, 402 distinct bacterial genomes from GenBank 3. For model evaluation, we use datasets derived from the CAMI2 challenge data [33. representing marine and plant-associated environments and including fungal genomes. These datasets propose realistic and complex reads, making them of the most utilized benchmarks for the metagenomics binning task. Additionally, the synthetic datasets consist of randomly sampled sequences from the fungi and viral reference genomes, excluding any samples from the training data 332
Baselines and proposed models. For our experiments, we have employed the recent genome foundation models to assess the performance of our approach. (i) KMER is one of the most widely used baselines, and also serves as a fundamental component of our model. The DNA sequences are represented as 4-mer profiles Tetramucleotide Frequencies given in Eq. so each read is represented by 256-dimensional vector. (ii) HYENADNA [16] is genome foundation model, HYENADNA. pre-trained on the Human Reference Genome
7 with context lengths up to 10 tokens single

---

nucleotide resolution. (iii) DNABERT-2 2 species genomes, and proposes Byte Pair Encoding (BPE) for DNA language modeling to address the computational inefficiencies related to k-mer tokenization. It also incorporates various techniques, such as Attention with Linear Biases (ALiBi) and Low-Rank Adaptation (LoRA), to address the limitations of current DNA language models. (iv) DNEBERT-S (2) aims to generate effective species-aware DNA representations and relies on the proposed Manifold Instance Mixup (MI-Mix) and Curriculum Contrastive Learning approaches. It relies the pre-trained DNABERT-2 model as the initial point of contrastive training. (v) OURS(KKER-() is similar to the KMER approach presented in (i), but it uses 1 distance instead of the cosine-similante
B1 is another foundation model pre-trained on multi-
distance so we will also name the first one as (KMER COSINE) to distinguish both models. (vii) (URS() refers to the Poisson approach described in Section 3.2 (vi) OURS(NL) refers to the non- con-linear& k-mer embedding
approach based on self-supervised constractive learning described in Section 3.3
Parameter Settings. Our proposed models were trained on cluster equipped with various NVIDIA GPU models. For the optimization of our models, we employed the Adam optimizer with learning rate of 10-3 We used smaller subsets of the dataset for training reads for OURS(POIS) and 10t sequences for OURS(NL). The OURS(NL) model was trained for 300 epochs with mini-batch size of 10a, while (URS(POIS) was trained for 1000 epochs using full-batch updates and window size of 4. Since we incorporated the contrastive learning strategy for OURS(NL), randomly sampled 200 read halves to form the negative instances for each positive sample (one half of a read). We have set k = and the final embedding dimension to 256 for our
models, and we sampled 10
all models. Following the experimental set-up of [32]. we used the publicly available pre- pre-trained versions of the baseline genome foundation models in the Hugging Face platform.
4.1 Metagenomics Binning Task
We assess the performance of the models based on the number of detected species/clusters and these clusters are classified into five different quality levels in terms of their F1 scores. Our methods and each baseline approach generate embeddings for the reads, and we cluster these read representations by following the work [32] with the modified K-Medoid algorithm. We refer readers to the cited work for further details on this approach. In line with standard practices in the field, we use cosine similarity for the baseline methods measure the similarity between read embeddings required for the K-Medoid algorithm. For OURS(KMER-B) ), we employed the exp(-dis((-: dis((-.))) -)) function with I distance, while Euclidean distance was used for (URS(POIS) and OURS(NL).
Figure 3 highlights the number of detected bins/clusters across different quality levels. For instance, the number of bins/species whose Fi scores above 0.9 is represented in dark blue while those with Fi scores between 0.5 and 0.6 are highlighted in red. Since we observe that the deviation in the number of detected species in most cases changes between most +5,, the error bars were not included.
The results underscore the effectiveness of k-mer features, which are central to our paper's 's focus. More specifically, as it was observed in the study (32), k-mer feature vectors (i.e., KMER-COSINE) surpass some genome foundation models like HYENADNA and DNABERT-2. Furthermore, we highlight the importance of choosing appropriate similarity measure by showcasing the perfor- mance of the OURS(KMER-L) variant. We note that Proposition 3.2 establishes a link between k-mer space equipped with l distance and read space with edit or Hamming distance. Thus, leveraging an appropriate metric in defining the similarities between reads in the binning stage also contributes to the performance improvement of (URS(KMER-()).
Despite the OURS(NL) model's lightweight design compared to recent genome foundation archi- tectures, our non-linear embeddings effectively identify both high and low-quality bins. In the metagenomics binning task, for practical purposes, the high-quality bins are typically prioritized (depicted in dark blue), and our model demonstrates comparable performance to the DNABERT-S model on both Synthetic and Plant datasets, and also outperforms DNABERT-S on the Marine dataset. Overall, our findings emphasize the efficacy of lightweight non-linear embeddings built on top of k-mer profiles.
4.2 Ablation Study
We conduct series of ablation studies in order to gain deeper insights into different components of the proposed architectures. We will start first by examining the impact of the parameter l which
8

---

Plant
Plant
Species Count (F)
Synthetic 5
Syuthetic 6
Marine 5
Marine
2
5
6
2
3
5
5
6
Parameter (B)
Parmmeter (k)
Parameter (A:)
Figure 4: Influence of parameter the OURS(KMER-l) model across different datasets.
Species Count (F) >> 0.90
Syuthetic 5
Plant
Marine 5
Synthetic 6
Plant
Marine
2'
2-
2'
2
2
2
2
2
2
2
2
Parameter
(d)
Parameter (d)
Parameter (d)
Figure 5: Influence of dimension size (d) on the OURS(NL) model across different datasets.
used define the k-mer profiles. plays a fundamental role in the paper because all the model variants that we introduced rely on it. As also explained in Section the selection of k also influences the identifiability of reads. In this regard, we evaluate the performance of the OURS(KMER-J) model across various & values. Tigure4shove the number of high-quality bins (i.e., Fi > 0.9) for different i settings and reveals that the optimal performance generally achieved when set to on different datasets. It also holds true across our different architectures, we have set l 4 in our models.
We also examine the influence of the output dimension size on the performance for the OURS(NL) model. We employed a very shallow architecture as described in Section B.3 the output dimension size plays vital role in the computational cost and performance. As can be observed in Figure 5 the increase in dimension size also positively contributes the number of detected high-quality bins, and the performance mostly saturates after 27. In order to have fair comparison with the baselines, we also used 2 as an output dimension size in our architectures.
For the OURS(NL) architecture, it is very natural to use Bermoulli distribution to model whether a given pair of reads belongs to the same genome or not. However, different organisms might share similar regions in their genetic codes; therefore, assuming binary interactions might not suit well in every situation. In this regard, we rewrite Eq. by Poisson distribution that also employed for the OurS(POIS) architecture as follows:
Apoisson
Σ (K,))T
-Wi log d1z + Xdg
NL
I
where X == exp(-IlExu(rr)) ExL. (r, 1 and Mi E [0 denotes if reads i and j belong to the same genome or not. We also test the loss function proposed by (18), which we refer as hinge loss:
clinge
(r.) - Ex,(r)))1 (1 -1 Vis) max 1 (1E ExC. (r, (K.))Z
Σ
NL.
Table I outlines the number of high-quality bins, and the Bernoulli and Poisson loss functions show comparable performances. the other hand, we observe that is possible to obtain even higher scores using the Hinge loss. However, it fails have a probabilistic interpretation.

---

Table 1: Comparison of loss functions by the number of clusters (with Fj
0.9).
Synthetic 5
Synthetic 6
Plant 5
Plant 6
Marine
Marine 6
Bernoulli 123
121
29
30
120
134
Poisson
128
123
30
28
121
128
Hinge
135
131
40
32
131
140
Conclusion
In this study have shown the efficacy of non-linear k-mer-based embeddings for metagenomic bin- ning tasks, providing compelling alternative to more recently proposed complex genome foundation models. Our work revisits and expands the theoretical framework surrounding k-mers, specifically addressing the identifiability of DNA fragments through their k-mer profiles and establishing new bounds on the distances defining relevant metric spaces. This theoretical insight not only reinforces the validity of using k-mer-based approaches for genome representation but also highlights their broader applicability in genomic research, such as taxonomic profllingClassification 22 26 and phylogenetic analysis [30].
The lightweight model being proposed in the paper, grounded in these theoretical principles, shows considerable promise the field of metagenomic binning. achieves a performance comparable to that of state-of-the-arr genome foundation models while requiring orders of magnitude fewer computational resources. This feature is especially important for large-scale genomic analyses that are currently driven by recent advances in sequencing technologies and where computational efficiency is paramount.
Limitations and Societal Impact
The ability to scale up metagenomic binning holds the potential for broader socictal impacts through an improved understanding of the diversity and function of the microbial communities that influence health and environment. Insights into these communities achieving the sustainability goals [24] Π. in particular good health and well-being (SDG-3), life below water LDDG-14), and life on land (SDG-15), to name few. The current study is partly limited by the experimental setup, which is only based on synthetically generated genomic data following the experimental setup of similar studies such [31 32 While the discussions about computational resources are not expected to be significantly affected by the type of data being used, the evaluations and comparisons of the quality of the recovered genomes most likely will. For instance, samples containing genomes of closely related species or strains of the same species will generally be more difficult separate into distinct clusters. As part future work, we plan pursue more rigorous analysis of the binning quality using long-read sequences from real-world data.
also play essential role in
Acknowledgements
We would like to thank the reviewers for their constructive feedback and insightful comments. We would also like to thank Mads Albertsen, Katja Hose and all members of Albertsen Lab at Aalborg University for the valuable and fruitful discussions. This work was supported by a research grant (VIL50093) from VILLUM FONDEN.
References
[1] Adenike A. Akinsemolu. The role of microorganisms in achieving the sustainable development 155, 2018.
goals. Journal of Cleaner Production,
[2] Mads Albertsen, Philip Hugenholtz, Adam Skarshewski, Käre L. Nielsen, Gene W. Tyson, and Per H. Nielsen. Genome sequences of rare, uncultured bacteria obtained by differential coverage binning of multiple metagenomes. Nature Biotechnology. 31(6):533-533, 2013.
[3] Dennis A Benson, Mark Cavanaugh, Karen Clark, Ilene Karsch-Mizrachi, David J Lipman, James Ostell, and Eric W Sayers. Genbank. Nucleic acids research, 41(D1):D36-De) D32-D422, 2012.
10

---

[4] C Curge, A M Campbell, and S Karlin. Over- and under- rnder-representation of short oligonucleotides in DNA sequences. Proceedings of the National Academy of Sciences, 89(4): (399)::358-1322 1992.
[5] Hugo Dorla-Torre, Liam Gonzalez, Javier Mendoza-Revilla, Nicolas Lopez Carranza, Adam Henryk Grzywaczewski, Francesco Oteri, Christian Dallago. Evan Trop, Bernardo P de Almeida, Hassan Sirelkhatim, et al. The nucleotide transformer: Building and evaluating robust foundation models for human genomies. BioRxiv, pages 2023-002200 023--1.220 2023.
[6] Veronika B. Dubinkina, Dmitry S. Ischenko, Vladimir I. Ulyantsev, Alexander V. Tyakht, and Dmitry G. Alexeev. Assessment of k-mer spectrum applicability for metagenomic dissimilarity analysis. BMC Bioinformatics, 17:38, 2016.
[7] Simon G Gregory, KF Barlow, KE McLay, Kaul, D Swarbreck, A Dunham, CE Scott, KL Howe, Kathryn Woodfine, CCA Spencer, et al. The dna sequence and biological annotation of human chromosome 1. Nature, 441((091):315-32)
2006.
[8] Yanrong Ji, Zhihan Zhou, Han Liu, and Ramana V Davuluri. Dnabert: pre-trained bidirectional encoder representations from transformers model for dna-language in genome. Bioinformatics, 37(15):212-22200 2021.
[9] Dongwan D. Kang, Feng Li, Edward Kirton, Ashleigh Thomas, Rob Egan, Hong An, and Zhong Wang. MetaBAT 2: An adaptive binning algorithm for robust and efficient genome reconstruction from metagenome assemblies. PeerJ, 7:e7359, 2019.
[10] Mikhail Kolmogorov, Derek M. Bickhart, Bahar Behsaz, Alexey Gurevich, Mikhail Rayko, Sung Bong Shin, Kristen Kuhn, Jeffrey Yuan, Evgeny Polevikov, Timothy P. L. Smith, and Pavel A. Pevzner. metaFlye: Scalable long-read metagenome assembly using repeat graphs. Nature Methods, 17(11):1003111) 2020.
[11] Olexiy Kyrgyzov, Vincent Prost, Stéphane Gazut, Bruno Farcy, and Thomas Brüls. Binning unassembled short reads based on k-mer abundance covariance using sparse coding. Giga- Science, 9(4)ggaa, 2020.
[12] Andre Lamurias, Alessandro Tibo. Katja Hose, Mads Albertsen, and Thomas Dyhre Nielsen. Metagenomic Binning using Connectivity-conster Variational Autoencoders. In Proceed- ings of the 40th International Conference Machine Learning, pages 18471-18481. PMLR, 2023.
[13] Fernando Meyer, Adrian Fritz, Zhi-Luo Deng, David Koslicki, Till Robin Lesker, Alexey Gurevich, Gary Robertson, Mohammed Alser, Dmitry Antipov, Francesco Beghini, et al. Critical assessment of metagenome interpretation: the second round of challenges. Nature methods, 19(4):429 440, 2022.
[14] Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed Repre- sentations of Words and Phrases and their Compositionality. In Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013.
[15] Patrick Ng. dna2vec: Consistent vector representations of variable-length k-mers, arXiv preprint arXiv:1701.06279 2017.
[16] Eric Nguyen, Michael Poli, Marjan Faizi, Armin Thomas, Michael Wornow, Callum Birch- Sykes, Stefano Massaroli, Aman Patel, Clayton Rabideau, Yoshua Bengio, et al. Hyenadna: Long-range genomic sequence modeling at single nucleotide resolution. Advances in neural information processing systems, 36, 2024.
[17] Jakob Nybo Nissen, Joachim Johansen, Rosa Lundbye Allesde, Casper Kaae Sønderby, Jose Juan Almagro Armenteros, Christopher Heje Grønbech, Lars Juhl Jensen, Henrik Bjørn Nielsen, Thomas Nordahl Petersen, Ole Winther, and Simon Rasmussen. Improved metagenome binning and assembly using deep variational autoencoders. Nature Biotechnology, 39(5)5555-560, 2021.
[18] Shaojun Pan, Xing-Ming Zhao, and Luis Pedro Coelho. SemiBin2: Self-supervised con- trastive learning leads better MAGS for short- and long-read sequencing. Bioinformatics, 1)pppllmmmmtt__ii21-222111 2023.
11

---

[19] Edoardo Pasolli, Francesco Asnicar, Serena Manara, Moreno Zolfo, Nicolai Karcher, Federica Armanini, Francesco Beghimi, Paolo Manghi. Adrian Tett, Paolo Ghensi, Maria Carmen Collado, Benjamin I.. Rice, Casey Dul Long, Xochitl C. Morgan, Christopher D. Golden, Christopher Quince, Curtis Huttenhower, and Nicola Segata. Extensive Unexplored Human Microbiome Diversity Revealed by Over 150,000 Genomes from Metagenomes Spanning Age, Geography, and Lifestyle. Cell, 176()):499-62.cc2 2019.
[20] Pavel A. Pevzner. Dna physical mapping and alternating eulerian cycles in colored graphs. Algorithmica, 13(1-2):77-105, 1995.
[21] Ruohan Ren, Changehuan Yin, and Stephen S.-T. Yau. Kmer2vec: A Novel Method for Comparing DNA Sequences by word2vec Embedding. 2900):0011-1021, 2022.
[22] Wei Shen, Hongyan Xiang, Tianquan Huang, Hui Tang. Mingli Peng, Dachuan Cai, Peng Hu, and Hong Ren. KMCP: Accurate metagenomie profiling of both prokaryotic and viral populations by gpeudo-mpppnng Bioinformatics, 39(1 (011)bbt 2023.
[23] Caitlin M. Singleton, Francesca Petriglieri, Jannie M. Kristensen, Rasmus H. Kirkegaard, Thomas Y. Michaelsen, Martin H. Andersen, Zivile Kondrotaite, Søren M. Karst, Morten Dueholm, Per H. Nielsen, and Mads Albertsen. Connecting structure to function with the recovery of over 1000 high-quality metagenome-assemble genomes from activated sludge using long-read sequencing. Nature Communicationss 12(1):2009) 2021.
[24] Kenneth Timmis, Willem M. de Vos, Juan Luis Ramos, Siegfried E. Vlaeminck, Auxiliadora Prieto, Antoine Danchin, Willy Verstraete, Victor de Lorenzo, Sang Yup Lee, Harald Brüssow, James Kenneth Timmis, and Brajesh K. Singh. The contribution of microbial biotechnology to sustainable development goals. Microbial Biotechnology, 10(5):984-987, 2017.
[25] Esko Ukkonen. Approximate string- matching with q-grams and maximal matches. Theoretical computer science, 92(1):191 221,, 1992.
[26] Jens-Uwe Urrich and Bernhard Renard. Fast and space-efficient taxonomic classification of long reads with hierarchical interleaved XOR filters. Genome Research, page gr.278623.123, 2024.
[27] Ryan R. Wick, Louise M. Judd, Louise T. Cerdeira, Jane Hawkey, Guillaume Méric, Ben Vezina, Kelly L. Wyres, and Kathryn F. Holt. Trycycler: Consensus long-read assemblies for bacterial genomes. Genome Biology, 22(1):266, 2021.
[28] Yu-We Wei Wu, Blake A. Simmons, and Steven W. Singer. MaxBin 2.0: An automated binning algorithm to recover genomes from multiple metagenomic datasets. Bioinformatics, 32(4):605- 607, 2016.
[29] Chao Yang, Debajyoti Chowdhury, Zhenmiao Zhang. William K. Cheung, Aiping Lu, Zhaoxiang Bian, and Zhang. review computational tools for generating getagenome-assembllee genomes from metagenomic sequencing data. Computational and Structural Biotechnology Journal, 19:6301-6314 2021.
[30] Chenglong Yu, Mo Deng, Shiu- Yuen Cheng, Shek-Chung Yau, Rong L. He, and Stephen S. T. Yau. Protein space: A natural method for realizing the nature of protein universe. Journal of Theoretical Biology, 318: 197-247, February 2013.
[31] Zhihan Zhou, Yanrong Ji, Weijian Li, Pratik Dutta, Ramana Davuluri, and Han Liu. Dnabert- 2: Efficient foundation model and benchmark for multi-species genome. arXiv preprint arXiv:2306.15000 2023.
[32] Zhihan Zhou, Winmin Wu, Harrison Ho, Jiayi Wang, Lizhen Shi, Ramana V Davuluri, Zhong Wang, and Han Liu. Dnabert-s: Learning species- aware dna embedding with genome foundation models. arXiv preprint arXiv:2402.08777, 2024.
[33] Abdulkadir Çelikkanat, Yanning Shen, and Fragkiskos D. Malliaros. Multiple kernel repre- sentation learning on networks. IEEE Transactions on Knowledge and Data Engineering, 35(6):6113 13- 13-6125, 2023.
12

---

A Appendix
A.1 Theoretical Analysis
Lemma A.I. Let = 11 TI be a read satisfying Cr (x;) = for its every (k - 1)-mer, X; T where 1 ii for some i" E (I....,. ..,,. + 2}. If there exists a read q = 91 ...... 9.
having the same k-mer profile then T; qi for all 1 < S 1 22
Proof. Let r be a read where (k - 1)-mers, x; == ri.... Titk- 2, appears only once in for all 1 S S i". As a basis step, we first show that the initial k-mer of q must be the same as that of r, i.e. Tk. Suppose this is not the case, then there must exist an index 1 S. j S l k such that 93 ... 4j+k-1 1 = r1 ..... T3 since they have identical k-mer profiles by initial assumption. Note that j X 1; otherwise, the reads would share the same prefixes. Therefore, Qj-1 1i.1....0 ... is another k-mer of q, and must also present in r because they share the same k-mer profile Since Tk- 4i Uj+k 2, k-mer 9j-1 4j+k-2 must be the prefix of r; otherwise (A- 1)- G3... 92.-2 (i.c. T1 Tk-1) appears in r more than once and it violates the assumption that (x,) for all x, T2 T where i {I....,," } However, if qj-1 9g+k-2 2 is the prefix of r. then enforces that 4--1 = qj = = dj+k-2 = 4j+k-1 and a (A - mm- occurs more than once in the substring r1 TT reads and q must have the same initial k-mer.
For the inductive step, suppose that reads r and q agree up to position index j where k - < - k- i.e., r; 9. for all 1 I i S j. We will show r,41 and 9j+1 are also the same. Since j < k+2 substring 4--b-2 ... 4j+1 is also a k-mer of q. Since reads have the same k-mer profiles, r also includes it. By the inductive hypothesis, we have Qj-k+2 .. "j Tj-k42"-' and we know (k- - 1)-mer T .., occurs only once so it implies that fj- 1...........
1-2..-.---- 2.t...11111111 = - r i.e. rj+1 9j+1- In conclusion, we have T; q. for all <i +
Corollary A.2. If the (k- 1)-mer profile of read contains at most one occurrence for each of its (k- - 1)-mers, then there is no other read having the same k-mer profile.
Proof. Letr r1 ..... -e and q = Q1 ... qe be reads having the same k-mer profile and each of their (k- - 1)-mers appear only once. By Lemma A. have r; q: for all 1 <is < l since cx(x))
for all (k- - m)-me x; = r;... ritk where O si -
Theorem A.3. Let r be a read of length f. There exists no other distinct read having the same k-mer profile if and only if does not satisfy any of the following conditions:
1. ri Tk-1 = Tt-k-2 ... Te and r; F rı for some 1 <i<e-R 2-
2. ... Ti-k k-2 == =r .... T.....jfteee............ f and rg. TTgk-- = Th+k-2 for some indices 1 Sic
9 <j < S 1: + where ritk-1' ................................
.......--- T1- # rj+k-1 ... Th
3. Ti. TT-kk2 = Vj . T
= Th .. Thh*k 2. for some indices Siiijjee Sisjchst-ae where Ti4k-1 ... TT rj-1 # rjtk-1 1h
Proof. Let r = TI be a read of length L, and we will first show that if read sat- isfies one of these conditions, then we can find a read other than having the same k- mer profile. (i) Suppose that we have rT-
Ti-k+2 -.-r, Tr, then the read defined as ryTi+1 TT -TE---T-T2 2--2 ... "TE-"---T-TT'e TE-ITEEETEHH "T;"--2'-11 will be distinct from for some i E .k.....f
k + 11. and it shares the same k-mer profile. (ii) Let be a read holding the second condition so we have 7, Tith-2 = Ty -TT----2 and rg "Tookkk-2 = Fh ... Th+t-2 for some indices 1 S < 9 < < h L. Then, we can construct different read having the same k-mer profile by interchanging the substrings T-tk-1 T. 9- and Tjtk-1 ... Th-1- (ii) As the last con- dition, suppose that we have r, -Titk-
TA -h+A-2 for some indices 1 i < < - l + 2 such that substrings 1itk-1...77 T- and rj+k-1 - are not the generate new read with an equivalent k-mer profile by swapping these substrings.
Ty.--Tjtk-
same
Conversely, assume that there exists read q that shares the same k-mer profile as r but doesn't 't meet any of the conditions outlined. Let x be the first (A: -m-r in where it appears more than once in r, and let i S i2 S ... & in be the position indices where occurs in r, i.e. x = Ti, ... -. vh E {l...., ) and (x) n. It must satisfy i > 1 or in < é t- k + 2; otherwise, it violates the
13

---

first condition. By Lemma A.1 r and q must match up to the position index in + k 3. Since r and
q have the same k-mer prohles and c, -r Tig-k+1) = (%,11111 ... 9; -k+1) we can also write that rj = Oj for all 1 < j S i1 + k 2 and we will show that reads, r and q. must be the same up to the position index in k 2.
If (A: merr x, occurs more than twice in r (i.e., n > 2), then either in+1 in = 1 or substrings Ti ...- 41 for each h (1.n- } must be the same due to the third condition. Thus, obtain identical reads up to i,2 + k - 2.
Now, will consider the case in which appears exactly twice in (i.e., n 2). If substring Th ... -r,-1 consists only of (k me-s occurring at most once in r, then again, we achieve the equivalence of the reads up to index i, k- - 2. Therefore, suppose that there exists a (k: 1)- y # x appearing more than once in r and let ji....,Jm be its position occurrence indices (i.e. y ri, TT, + Vh {1,.... fm )). Note that jm cannot be greater than in since it violates the second condition, so we assume that all occurrences of y are within +1 ... TT, Ts, +k-3 By recursively applying the same strategies for the substring, +j -mm- we can conclude that the reads must be the same up to in + k- --2 2.
Note that the remaining part of the read, Th.-k-1 Te,, does not contain any (k-1)- mer appearing in T1 .. 4 so by applying the same strategy to the rest of the read, we can obtain that r q.
Proposition A.4. Let M1 (Re, du) and M2 (NI -I I11) be the metric spaces denoting the set of identifiable reads and their corresponding k-mer profiles equipped with edit and f distances. respectively. The k-mer profile function, M, - M2, mapping given any read, r, to its corresponding k-mer profile, Gr == c(r),, is a Lipschitz equivalence, iee. it satisfies
Vr,q E Et ordz(r; 9) S ||cr calli S cadu(r,
for aq 1/e and au k|>2),, so M1 and M2 are Lipschitz equivalent.
Proof. By definition, we have (x(x) = -.E [r. ... - = x] where the symbol, [:]. denotes the Iverson bracket. Then, we can write the upper bound
||0r - -alll= = Σ
[cr(x) - (x)]
X
k-k++
t-k+1
Σ
[r: P Titk-1 - =x]-
Σ
[ aa...ee 1itk-
X
É-K+1
Σ
(ne--- =x] -. -ith- x))
x
[n [re-- = - 1-
k-1+1
Σ
[re Ti # qs [1++-]]
X
i=1
k
frita + mit]]
X
t-k+1
Mrr # vil
< k
Σ
Ira + 9m)
x
1=1
| du (r, 9)
For the lower bound, we know that dx (r, q) must be greater than if and only if and q are different since r, Ny (i.c. identifiable); otherwise we have ||c, cqll1 dx (I, q) = 0. For non non-identical
14

---

reads, there must exist at least one 1 < i I such that & Qto so it implies that there is an k-mer x' t such that cx(x') & (x'). Then we can write that
dx (r, q)
S ||e - call
A.2 Experiments
For the evaluation of the models, we follow the same experimental set-up proposed by the recent genome foundation model [2]. and we assess the performance the models with respect to the quality of the number of detected clusters.
We suppose that the number of clusters (i.e., genomes) in the evaluation datasets is unknown, we utilize the modified K-medoid algorithm to infer the clusters. It requires a threshold value separate datasets derived
due to the initially unknown number of clusters so address this, from the same source as the target evaluation datasets. For each method, we first compute the cluster centroids using the ground-trute labels and the embeddings generated by the respective approaches. Then, we calculate the similarities between the centroid vector and the read embeddings within the same cluster. The threshold value selected as the 70th percentile of these sorted similarity scores. After inferring the clusters by the modified K-medoid algorithm, the extracted cluster labels are then aligned with the ground truths labels by the Hungarian algorithm.
For the experiments, we use the publicly available datasets provided by Zhou et al. which include training set of 2 million non-overlapping DNA sequence pairs. For model evaluation, work with 3 types of datasets, each having two variants, and we provide various statistics about them in Table The datasets named as Dataser are only used detect the optimal threshold value for the K-medoid algorithm and the other variants (i.e., Dataset 5 and Dataset 6) are considered for the evaluation. We truncated sequences longer than 10, 000 bases, excluded those shorter than 2, 500 bases, and omitted species represented by fewer than 10 sequences.
Table 2: Statistics of the datasets used in the experimental evaluations.
Sequences (RR)
Min. Seq. Length
Max. Seg. Length
Avg. Seq. Length
Dataset
Species
Synthetic 0
200
20, 000
9, 944
10, 000
9, 9,999
Synthetic 5
323
37, 278
9,919
10, 000
9, 999
Synthetic
249
28, 206
9,913
10, 000
9, 999
Plant 0
108
10, 800
2, 089
20, 20,000 000
9, 040
Plant 5
323
10, 800
81
20, 000
3, 953
Plant 6
374
111,
80
20, 000
3, 709
Marine 0
326
32, 600
1971
20, 000
9, 600
Marine
660
167, 875
83
20, 000
4, 755
Marine 6
664
175, 316
80
20,000
4,840
A.3 Notation and Symbols
provide a comprehensive of all symbols used throughout paper in Table This table might serve reference to help readers easily follow the notation employed in our work.
15

---

Table Symbols and their descriptions used throughout the paper.
Symbol
Description
Genetic alphabet
R
Set of reads
E()
Embedding function
&
Read
Read length
k
Length of k-mers
y
All k-mers of length
Binary variable showing if the pair is positive sample
Pij
Success probability of positive pair
Xijo Xxy
Rate of the Poison distribution
Window size
(x)
Number of occurrences of x in r
(x (x)
Number of co-occurrences of x and y within a window of size
16

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes].
We carefully reviewed the abstract and introduction, and they do contain any claims that are not justified in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: In the paper, we discuss the strengths and weaknesses of the proposed architec- ture in detail with computational requirements.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sellsspeciiiationn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
17

---

Answer: [Yes]
Justification: Yes, we clearly emphasize the assumptions that we make and the proofs of our theoretical contributions are given in the appendix due to the space limitations.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Yes, provide the implementation of the proposed architectures, and perform the experiments on the publically available datasets so the results can be easily reproduced.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
18

---

reproducible, they 5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: Yes, we provide open access to the codes, and the data can be easily found online by following the references in the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/nipss wttpcc/ccccccccccccocooooo http:/guuuddeeooeSSuubbbiiiii wwwtanssssonppo. swiniioisiiiyccy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Yes, we provide the details regarding the training and test data sets, as well as the optimization details.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: Since we observe that the deviation in the number of detected species changes between at most +4, we decided to omit the error bars to make the figure readable.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
19

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Yes, we provide the detailed computational resources that we used in the experiments.
Justification:
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neuripss.
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Yes, in the paper, we discuss both potential positive and negative socictal impacts of the work.
Guidelines:
20

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g.. gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper does not pose such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Yes, in the paper, we cite the resources of the datasets that we used in the experiments.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
21

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssi
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
22

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
23


Reviews:
[{"review_id": "Zfdxhl3iRd", "reviewer": "Reviewer_xd8g", "summary": "The authors provides a theoretical analysis for k-mer-based representation of genomes and then propose a lightweight and scalable model for performing metagenomic binning at the genome read level, relying on the k-mer compositions of the DNA fragments and achieve pretty good results.", "questions": "See Weekness", "limitations": "Yes, they Have.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The logical is exceptionally clear and well-structured. \n\n2. The issues examined in this paper are interesting and relevant.", "weaknesses": "1. Limited comparison with the current methods. Zhang[1] has propose a novel k-mer natural vector for representing biological sequences with the consideration of positional information in sequence. What is your strengths compared with the novel k-mer natural vector. Could you make comparison with it in the task of Metagenomics Binning. In addition, there are various pseudo features extracted from biological sequences directly [2], why not compare with them in terms of performance.\n\n2. Limited experimental results. The article just shows the results just on one task of Metagenomics Binning, which may not fully demonstrate the effectiveness of k-mer. If possible, please design more downstream tasks.\n\n3. The poor framework. We all know k-mer feature can work, but how to design a framework to its strength. As shown in the Figure 3, DNABERT-S outperforms ‘Ours-linear’ and ‘Ours-nonlinear’ in all datasets. In addition, METABAT2, VAMP and SEMIBIN2 are the common binning algorithm, why not compare with them to highlight the effectiveness of “Ours-linear” and “Ours-nonlinear”.\n\n4. Lack of guidance from theory to experiment. The proof of Theorem 3.1 is a wonderful process, but how to use it to guide the experiment, how to select a suitable k according the special dataset. And if we consider the position of k-mers in sequences, then we can assure that any sequences are identifiable unless they are exactly the same.\n\n5. Lack more detailed explanation for the effectiveness of k-mers. The DNABERT family builds a vocabulary based on k-mers and then uses a nonlinear network to extract the embedding for each tokens, which is also a nonlinear representation, but what is the difference between this and \"Ours nonlinear\". Apart from the dimensional difference, where is the disadvantage.\n \nReference:\n\n[1] Zhang, YuYan, Jia Wen, and Stephen S-T. Yau. \"Phylogenetic analysis of protein sequences based on a novel k-mer natural vector method.\" Genomics 111.6 (2019): 1298-1305.\n\n[2] Pse-in-One: a web server for generating various modes of pseudo components of DNA, RNA, and protein sequences B Liu, F Liu, X Wang, J Chen, L Fang, KC Chou - Nucleic acids research, 2015", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are thankful to Reviewer xd8g for the thoughtful feedback and suggestions. We address the reviewer's questions in detail below:\n\n**1. Limited comparison with the current methods.**\n\nThank you for your helpful reference, which we have added to the conclusions/future work section.  We agree that exploring alternative k-mer-based representations [1] and/or pseudo-features [2] could indeed be interesting in relation to metagenomic binning. However, our aim is not to determine the best $k$-mer or pseudo-feature representation (or tokenization in general). Rather, we aim to i) contribute to the theoretical understanding of standard $k$-mer-based representations used in the literature and to ii) demonstrate how simple $k$-mer-based model architectures can provide competitive accuracy results compared to recently proposed foundation models, but using only a fraction of the number of model parameters. We thus believe that even though a comparison with other tokenization methods could indeed be interesting, we also feel that it is a bit out of scope for the present paper, but could indeed be a relevant topic for future work. Please see also the first comment for *Reviewer tV95*.\n\n**2. Limited experimental results.**\n\nWe acknowledge the importance of evaluating a model across a broad range of tasks. However, metagenomics binning is a complex and challenging task on its own. It is an emerging field attracting significant attention and is a primary approach for identifying new species [3,4]. Consequently, any advancement in this area is highly relevant. Given the complexity of this study and the application domain, we have focused exclusively on the metagenomics binning problem. We plan to extend our analysis to include additional downstream tasks in future work. \n\n*[3] Dongwan D. Kang, Feng Li, Edward Kirton, Ashleigh Thomas, Rob Egan, Hong An, and381 Zhong Wang. MetaBAT 2: An adaptive binning algorithm for robust and efficient genome382 reconstruction from metagenome assemblies. PeerJ, 7:e7359, 2019.*\n\n*[4] Singleton et al. (2024, jun. 27). Microflora Danica: the atlas of Danish environmental microbiomes. https://doi.org/10.1101/2024.06.27.600767*\n\n\n**3. The poor framework.**\n\nAs noted for Question 1 above, the aim of this paper is to i) contribute to the theoretical understanding of standard $k$-mer-based representations used in the literature and to ii) demonstrate how simple $k$-mer-based model architectures can provide competitive accuracy results compared to recently proposed foundation models, but using only a fraction of the number of model parameters. Our goal is, therefore, not to propose a novel competitive binning method, which (we agree) should otherwise have been compared to state-of-the-art binners like VAMB, METABAT2, or SemiBin2. That being said, our non-linear model is inspired by SemiBin2 with a similar neural network architecture for deriving embeddings from $k$-mers. Additionally, we employ the same clustering algorithm as DNABERT-2 to ensure that the clustering algorithm itself does not influence the comparison, and, as discussed in the global response, we are using the exact same experimental setup as in the DNABERT-S paper.\n\nLastly, we would also like to provide a bit of nuance to the comment that “DNABERT-S outperforms ‘Ours-linear’ and ‘Ours-nonlinear’ in all datasets.” When focusing on the number of high-quality bins ($\\geq 0.9$) that are recovered (which is typically the main focus in the metagenomic binning task), we see that ‘Ours-nonlinear’ outperforms DNABERT-S on two data sets (Marine 5 and 6) and achieves comparable results on the remaining datasets. \n\n\n**4. Lack of guidance from theory to experiment.**\n\nIn this paper, we explored the relationship between reads (i.e., small DNA fragments) and their $k$-mer profiles to understand how $k$-mers can approximate distances within the read spaces. We introduced the concept of \"identifiability\" for the reads and demonstrated that these sequences can be perfectly reconstructed from their given $k$-mer profiles. It is also straightforward to see that setting the $k$ value to the length of the reads makes all sequences identifiable. However, finding the smallest $k$ value that makes all (or a certain percentage of) reads identifiable is challenging. \n\nOur primary interest is to obtain similar read representations in a latent space for the reads belonging to the same genome/species so that clustering methods can easily distinguish reads with respect to their species. However, reads seeming dissimilar might belong to the same species, so we use linear and non-linear models to learn the underlying patterns and properties among these reads, enabling them to be represented closely within a latent space. In this regard, we relax the identifiability condition to give more flexibility to the models. Our empirical findings indicate that using around $k=4$ provides optimal results for the metagenomic binning task (please see Figure 4 in the main paper and Figures 1-3 in the attached pdf file of the global comment).\n\n**5. Lack more detailed explanation for the effectiveness of k-mers. What is the difference between this and \"Ours nonlinear\". Apart from the dimensional difference, where is the disadvantage.**\n\nIt is correct that the original DNABERT model is based on $k$-mers, but the more recent DNABERT versions, which are used for our comparisons (DNABERT-2 and DNABERT-S), rely on byte pair encoding as tokenization. For DNABERT-2, the authors note that DNABERT-2 has 21x fewer parameters than DNABERT, and since our experiments were designed to demonstrate that comparative performance can be obtained with simpler and more scalable model architectures, the DNABERT method was not included in the comparison.  The DNABERT-S method is also the recent state-of-the-art genome foundation model considering the metagenomic binning task. In this regard, we have included the DNABERT-2 and DNABERT-S approaches in our experimental analysis.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MfJS8HalYX", "reviewer": "Reviewer_e86P", "summary": "The authors describe an embedding approach for binning metagenomic reads via a k-mer approach. The authors motivate the need for scalable solutions for metagenomic analysis and provide theoretical motivation for k-mer based approaches, which have value on their own. Then they motivate a strategy to learn non-linear embedding of short, correlated k-mers for binning purposes. They compare their approach to several large language models that have been used for that purposes and while having much higher complexity and foodprint, these do not provide better performance on commonly used standard benchmarking data.", "questions": "* Could the authors reconfirm that there is no overlap between the training data and the CAMI2 testing data? How was this ensured?\n* I understand the reasoning to not show errors bars, but could the authors (in the appendix) still provide the data for completeness reasons?\n* I am not sure this is feasible and this is really a discretionary question out of curiousity (and does not need to be answered for changing my mind on acceptance). Can the authors establish a conceptual relation of their embeddings to the probabilistic data structures (most recent example: https://genome.cshlp.org/content/early/2024/06/17/gr.278623.123.abstract) that are commonly used in algorithmic binning?\n* Can the authors compare to algorithmic approaches on CAMI2 data to give a ballpark orientation of the performance of their learning based approach?", "limitations": "Limitations are well addressed in the manuscript", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "* very well written manuscript, nicely incorporating algorithmic and learning approach for a relevant application\n•\tImpressive results (considering the scalability of the solution and the importance of scalability for the problem) in a well chosen benchmark\n•\tGood theoretical foundation of the provided solution (which has value beyond the proposed solution)", "weaknesses": "* The authors may want to acknowledge a little more in depth that there are also excellent algorithmic solutions for metagenomic binning that are directly evaluated on the CAMI2 data (in the CAMI2 publication).\n* Related, there is also no comparative evaluation to algorithmic approaches available (although very good ones to other machine learning based approaches).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to Reviewer e86P for the constructive review and helpful recommendations. We address Reviewer e86P’s concerns in detail below. \n\n> **The authors may want to acknowledge a little more in depth that there are also excellent algorithmic solutions for metagenomic binning that are directly evaluated on the CAMI2 data (in the CAMI2 publication).**\n\nThanks for reminding us of the inclusion of CAMI2. We will discuss it in the paper. \n\n> **There is also no comparative evaluation to algorithmic approaches available**\n\nWe completely agree that algorithmic approaches can be highly competitive with machine learning (ML) methods. However, we believe that such a comparison is not necessary for this particular study. Our objective is to demonstrate that ML methods based on k-mers are surprisingly competitive with large foundational models and to provide a theoretical explanation for this phenomenon. We are not asserting that our methods are superior to other ML or algorithmic approaches. Instead, we view this paper as evidence supporting the development of ML approaches that leverage $k$-mer-based representations to design more scalable meta-genomic binning methods.\n\n> **Could the authors reconfirm that there is no overlap between the training data and the CAMI2 testing data? How was this ensured?**\n\nWe utilized the publicly available datasets provided by the authors of the genome foundational model, DNABERT-S, and the authors have stated that the training and testing sets do not overlap.\n\n> **I understand the reasoning to not show errors bars, but could the authors (in the appendix) still provide the data for completeness reasons?**\n\nWe provide the detailed results for five runs of the non-linear model in the attachment of the global comment (Tables 1 & 2), and we will also include them in the appendix of the final version of the paper.\n\n> **I am not sure this is feasible and this is really a discretionary question out of curiousity (and does not need to be answered for changing my mind on acceptance). Can the authors establish a conceptual relation of their embeddings to the probabilistic data structures**\n\nThank you for the highly relevant question. The paper referenced above together with other state-of-the-art taxonomic classifiers such as [1], rely on or incorporate $k$-mer based representations for querying reference databases. The theoretical results in our paper can thus provide support for these approaches, but it would be interesting to investigate whether our results could be further developed to more specifically address taxonomic classification.  We have acknowledged this relation in the paper and included the two references. \n\n*[1] Wei et al: Kmcp: accurate metagenomic profiling of both prokaryotic and viral populations by pseudo-mapping. Bioinformatics, 39(1), 2023.*\n\n> **Can the authors compare to algorithmic approaches on CAMI2 data to give a ballpark orientation of the performance of their learning based approach?**\n\nAs we have previously stated, while we agree that this comparison would be quite interesting, we believe it is beyond the scope of this paper. Our focus is to demonstrate and analyze why $k$-mer-based ML methods are competitive with large foundational models for the metagenomic binning task.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GI78YnzocA", "reviewer": "Reviewer_8HNd", "summary": "The paper explores the use of k-mer profiles in genome representation for metagenomic binning. The authors propose a new, scalable model that leverages k-mer profiles to represent DNA fragments efficiently. This model is theoretically grounded and empirically validated against state-of-the-art genome foundation models.", "questions": "See W2, W3.", "limitations": "NA", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. **Theoretical Contributions**: The paper broadens the theoretical understanding of k-mer. By establishing theoretical bounds and providing a detailed analysis of DNA fragment identifiability, it contributes valuable insights that can guide future research and applications in genome analysis.\n    \n2. **Scalability and Computational Efficiency**: The proposed model addresses the computational demands associated with large genomic datasets. By demonstrating that their k-mer-based model requires significantly fewer resources compared to more complex genome foundation models, the paper appeals to practical needs in genomic research, particularly in resource-limited scenarios.\n    \n3. **Empirical Validation**: Through extensive empirical testing, the paper substantiates the theoretical claims by showing that the k-mer-based model performs comparably to genome foundation models in metagenomic binning tasks. This not only validates the model but also emphasizes its practicality for real-world applications.", "weaknesses": "1. **Comparison Basis**: The paper positions k-mer profiles as a competing approach against DNA language models (LMs). This comparison is somewhat misleading as k-mer is fundamentally a tokenization method (i.e. one initial step of DNA FM), and a more appropriate comparison would be between different tokenization strategies (k-mer vs. BPE) rather than against the entirety of DNA LMs.\n    \n2. **Experimental Clarity**: The experimental setup lacks detailed discussion, particularly on how the DNA foundation models are integrated and utilized in the experiments. There is a concern about potential unfair comparisons, especially if the study only uses the embeddings from DNA LMs for classification without fine-tuning the full models, which is the standard practice for such models. This could lead to skewed results favoring the proposed method.\n    \n3. **Technical Details and Minor Errors**: The paper has several minor but notable issues, such as the lack of clarity in the definition of the loss function at line 199 and missing labels for equations post Equation 3. These issues, while minor, could impede the understanding and reproducibility of the research.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate Reviewer 8HNd 's assessment and valuable comments. We address the reviewer’s questions in detail below: \n\n**1. Comparison Basis:**\n\nIn the literature, $k$-mers are widely used as feature vectors, but their effectiveness has not been examined well and is often attributed solely to practical reasons, such as the fixed-length input vectors. To address this, we reexamined $k$-mer features to understand why they are effective, and we explored the theoretical connection between DNA sequences and their $k$-mer profiles.\n\nAlthough the $k$-mers are a tokenization method, we demonstrated with simple $k$-mer based models that it is still possible to have comparable performances to large genome foundational models without requiring extensive computational resources. Our main motivation was to show that $k$-mer profiles remain powerful features (motivated by our theoretical analysis), and $k$-mer based models can achieve comparable or even superior results in the metagenomic binning task compared to these large foundational models. With advancements in sequencing technologies, large datasets have become more accessible, making the scalability of models a critical consideration. We believe our analysis, grounded in theoretical principles, can spark the development of novel $k$-mer-based approaches for obtaining more scalable and efficient methods, potentially playing a significant role in future research. \n\n\n**2. Experimental Clarity:**\n\nIn our paper, we adopted the same experimental setup established by the DNABERT-S method [3], which is the latest state-of-the-art genome foundational model performing the metagenomic binning task. This setup is also endorsed by researchers involved with other leading genome foundational models [1, 2]. In this regard, we have run all the baseline methods as their authors suggested by following the established practices in the literature. \n\nWe also utilized the publicly available datasets provided by the authors of DNABERT-S [4], and we shared all source codes for our proposed models to ensure that our results are easily reproducible. By adhering to established standards in the field, we maintain consistency and reliability in our experimental settings. \n\n*[1] Ji, Yanrong, et al. \"DNABERT: pre-trained Bidirectional Encoder Representations from Transformers model for DNA-language in genome.\" Bioinformatics 37.15 (2021): 2112-2120.*\n\n*[2] Zhou, Zhihan, et al. \"Dnabert-2: Efficient foundation model and benchmark for multi-species genome.\" arXiv preprint arXiv:2306.15006 (2023).*\n\n*[3] Zhou, Zhihan, et al. \"Dnabert-s: Learning species-aware dna embedding with genome foundation models.\" ArXiv (2024).*\n\n*[4] https://github.com/MAGICS-LAB/DNABERT_S*\n\n\n\n**3. Technical Details and Minor Errors:**\n\nWe appreciate the reviewer for pointing out the notational mistakes, and we will correct all errors in the final version of the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vvZ6fZIGuZ", "reviewer": "Reviewer_tV95", "summary": "This paper proposes a novel tokenization method for DNA sequence foundatnion model. According to the authors' experiments, their model has similar performances by comparing with other foundation models with larger scale, while their scalability looks better.", "questions": "Please see the weaknesses.", "limitations": "Please see the weaknesses, as well as their limitation section.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The tokenization process is interesting, and the paper contains theoricial proofs. It seems that their-TNF outperforms other methods in 1 out of 6 datasets.", "weaknesses": "Major:\n1. Their proof majorly focus on arguing the problems of k-mers tokenization. However, some baselines like DNAHyena utilizes single nucleobase as tokens. Is it possible to justify the superority of the authors' method comparing with other tokenization approach (e.g., single nucleobase token, and BPE used by DNABERT-2).\n\n2. According to their experiment result, it seems that their approach does not show comparable performances across all the datasets, which makes me hard to believe its superority. Moroever, some methods like HyenaDNA is only trained based on human genome, the testing dataset might be not suitable for benchmarking with these methods. Is it possible to select some genome overlapped with all of these methods? Also, it will be interesting if the authors can include NT [1] in the comparison.\n\n3. In section 4.1, the authors utilize two datasets to analyze the effect of hyper-parameters, are there any reasons for not using other datasets?\n\n4. The rest of benchmarked methods are all in Million level not billion level, and thus the superority of scaling it not very interesting. It will be helpful if the authors can discuss and try to scale their method to 1B or 7B level, which will be a breakthrough in this area. NT is 1B at max.\n\n[1] https://github.com/instadeepai/nucleotide-transformer\n\nMinor:\n\n1. It seems that there is a block near line 176 and I cannot click it, is it a typo?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate Reviewer tV95's thorough review and valuable comments. We address the reviewer's questions below:\n\n>**1. Their proof majorly focus on arguing the problems of k-mers tokenization. However, some baselines like DNAHyena utilizes single nucleobase as tokens. Is it possible to justify the superority of the authors' method comparing with other tokenization approach (e.g., single nucleobase token, and BPE used by DNABERT-2).**\n\nThe work reported in our paper is partly motivated by the prevalent use of $k$-mer representations for, among other tasks, metagenomic binning. These representations have, however,  mainly been studied from an empirical perspective. With this paper, our aim is to also i) contribute to the theoretical understanding of $k$-mer representations and to ii) demonstrate that $k$-mers, together with simple and scalable model architectures, can provide a viable alternative to the more complex foundation models that have recently been proposed. Our experiments and comparisons have been designed with this focus in mind. While we fully agree that a rigorous comparison with other tokenization methods is interesting, we also believe that such a comparison is a bit out of scope for the present paper. However, it could indeed be relevant as part of future work. Please also see the first comment for *Reviewer xd8g*.\n\n>**2. According to their experiment result, it seems that their approach does not show comparable performances across all the datasets, which makes me hard to believe its superority. Moroever, some methods like HyenaDNA is only trained based on human genome, the testing dataset might be not suitable for benchmarking with these methods. Is it possible to select some genome overlapped with all of these methods? Also, it will be interesting if the authors can include NT [1] in the comparison.**\n\nAs mentioned in our global response, our objective is to demonstrate that ML methods based on $k$-mers are surprisingly competitive with large foundational models and to provide a theoretical explanation for the $ k$-mer-based models. We are not claiming our methods are superior to other ML approaches. Instead, this paper supports the development of ML approaches leveraging $k$-mer-based representations to create more scalable metagenomic binning methods. As highlighted in the global response and by other reviewers, scalability is a crucial issue in metagenomic binning.\n\nIn terms of accuracy results, we would also like to provide a bit of nuance to the comment that “their approach does not show comparable performances across all the datasets”. When focusing on the number of high-quality bins ($\\geq 0.9$) that are recovered (which is typically the main focus in the metagenomic binning task), we see that ‘Ours-nonlinear’ outperforms DNABERT-S (as well as the other methods) on two data sets (Marine 5 and 6) and achieves comparable results on the remaining datasets. \n\nLastly, we would also like to note that in our paper, we adopted the exact same experimental setup established by the DNABERT-S method, which is the latest state-of-the-art genome foundational model performing the metagenomic binning task. This setup is also endorsed by researchers involved with other leading genome foundational models. In this regard, we have run all the baseline methods as their authors suggested by following the established practices in the literature. See also the first comment for reviewer 8HNd.\n\n>**3. In section 4.1, the authors utilize two datasets to analyze the effect of hyper-parameters, are there any reasons for not using other datasets?**\n\nBecause of the space limitations in the main paper, we chose only two datasets to show the impact of the hyper-parameters, but we provide the additional results in the attached file of the global response (Figures 1-6). \n\n>**4. The rest of benchmarked methods are all in Million level not billion level, and thus the superority of scaling it not very interesting. It will be helpful if the authors can discuss and try to scale their method to 1B or 7B level, which will be a breakthrough in this area. NT is 1B at max.**\n\nOur experiments demonstrate that we can achieve similar performance with $k$-mer-based representations using significantly smaller models. As you suggest, a very interesting experiment would be to create  $k$-mer-based models of the same size as existing foundational models to see if they perform better. We believe this is a promising line of research, and we hope this paper will motivate other researchers to explore this direction in future works.\n\n*[1] https://github.com/instadeepai/nucleotide-transformer*", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We sincerely thank all the reviewers for their valuable feedback and thoughtful insights, which we believe will greatly enhance the quality and clarity of the final version of the paper. While we have addressed each reviewer's questions in their respective rebuttal sections, we would like to provide further clarification on the following main points:

**1. Motivation:**

The main purpose of the paper is to show how $k$-mer-based representation, combined with a simple non-linear model and chosen appropriate metric spaces, can compete with or even surpass the performance of genome foundational models in the metagenomic binning task. The presented surprising results demonstrate that the community needs to better understand why $k$-mers are effective features because, despite their widespread use in various DNA sequence analysis tasks, the reasons behind their effectiveness and their potential as alternative representations of DNA sequences have not been thoroughly studied.

Therefore, our paper focuses on the relationship between DNA sequences and their corresponding $k$-mer profiles, and we provide detailed theoretical analysis to comprehend how $k$-mers can approximate distances and similarities in the DNA sequence spaces.  We believe our theoretical and experimental analysis will help researchers understand why the $k$-mer profiles are effective representations, as well as inspire other researchers to design better and more scalable k-mer-based models for metagenomic binning tasks. 


**2. A scalable approach:**

As we argue in the paper and other reviewers have noticed, scalability is an important issue in metagenomic binning tasks.  With advancements in sequencing technologies, large-scale genome datasets have become more prevalent [1]. However, addressing these datasets with resource-intensive models is challenging. Therefore, we aimed to demonstrate that one can have more lightweight models relying on $k$-mers that balance performance and computational requirements. Our experimental evaluations showed that the proposed architecture can achieve performance comparable to recent large genomic foundational models while using a number of parameters which are several orders of magnitudes smaller. 


**3. Experimental setup and results:**

In the paper, we used exactly the same experimental setup proposed by the DNABERT-S method [4]. It is the most recent state-of-the-art genome foundational model for the metagenomic binning task, which was also suggested by researchers, including the authors of the other foundational models [2,3]. Similarly, for the training and testing sets, we utilized the publicly available datasets provided by the authors [5].

We have made all the source codes for our proposed models available so all results can be easily reproducible. In this regard, our experimental settings follow the established standards in the field, ensuring consistency and reliability. We believe that this transparency and adherence to recognized methods will facilitate further research and validation of our approach. The additional experimental results can be found in the attached file.

*[1] Singleton, Caitlin M., et al. "Microflora Danica: the atlas of Danish environmental microbiomes." bioRxiv (2024): 2024-06.*

*[2] Ji, Yanrong, et al. "DNABERT: pre-trained Bidirectional Encoder Representations from Transformers model for DNA-language in genome." Bioinformatics 37.15 (2021): 2112-2120.*

*[3] Zhou, Zhihan, et al. "Dnabert-2: Efficient foundation model and benchmark for multi-species genome." arXiv preprint arXiv:2306.15006 (2023).*

*[4] Zhou, Zhihan, et al. "Dnabert-s: Learning species-aware dna embedding with genome foundation models." ArXiv (2024).*

*[5] https://github.com/MAGICS-LAB/DNABERT_S*

Meta-review: This paper presents a k-mer binning algorithm using language models, which is an emerging area. The paper appears to be well written and all reviewers are borderline accept or above, with one strong accept. From a quick look myself, the theoretical result and experimental results aren't per say strong/extensive, but appear to be well-presented/written. This clearly is an accept, and a spotlight is appropriate.
Decision: Accept (spotlight)