Answers.Body: <p>NLP and vectorisation is used to trap non-linearity which is highly applicable to sentences written in English.
  Vectorisation of k-mers for an overlapping sliding window is weird because it's trying to assess the functionality of non-coding sequence, i.e. &quot;silent&quot; and non-cds mutations will be the dominant mutation class, but it would identify localised co-mutations, i.e. within a k-mer.</p>
  <p>The only application I can think is stuff like identifying promoters or mutations in promoters, i.e. non-coding regions with a known function and can be trained against appropriate independent experimental observations, e.g. gene expression. If the k-mers were large it might work for RNA secondary structure because it would trap compensatory mutations. Vectorisation for individual nucleotides, i.e. dumbie variables, would not be successful at trapping compensatory mutations.</p>
  <p>In summary it has niche application.</p>
  <p>BERT is a famous large language model BTW.</p>
  <hr />
  <p>If k-mer =3 that's about non-linearity of proteins, but it depends how the sliding window is deployed. It depends on the step size of the sliding window.</p>
  <p>To try and answer this better, proteins fold back on themself triggering &quot;co-evolution&quot; or more accurately &quot;covariance&quot; between non-linear sites. This defines the triplet codon:</p>
  <ul>
  <li>in machine learning this is needed because it will struggle to find it by itself</li>
  <li>it will help it identify co-evolving mutations at non-linear locations across the gene</li>
  </ul>
  <p>It might also identify selection events better.</p>
  <p><strong>Summary</strong> If you've sat down and thought the equation the RNN is attempting to unravel its mind-boggling. More worrisome does it really do it? It's really complicated to simply discuss, but when you  give it key information the ML/DL gets there quicker. The authors will be aware of that in their training and testing.</p>
  <p>Honestly, we're at the limits of reasonable application of ML/DL without going into RasNet type infrastructure. My system is different the idea is the same - give the training model the key biological information, it gets to the answer quicker, a lot quicker.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-16T21:51:29.767Z
Answers.Text: I am sorry, but this does not answer my question regarding why one would use k-mers for k>1 versus 1-mers with positional encoding as is the norm with transformers. Not just BERT and other NLP transformer-like models (aka LLMs) but even ViT uses positional encoding
Answers.UserDisplayName: Avatrin
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-19T00:01:34.867Z
Answers.Text: I've tried my best above.
Answers.UserDisplayName: M__
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-16T21:27:58.337Z
Answers.LastActivityDate: 2023-09-19T12:17:24.950Z
Answers.LastEditDate: 2023-09-19T12:17:24.950Z
Answers.UserDisplayName: M__
Answers.Body: <p>[I'm not an expert in this field, this is only my &quot;best try&quot;. Maybe you could get better mathematically motivated answers on ai.stackexchange]</p>
  <p>First note that, as pointed in the DNA BERT paper, k-mers are a very common approach to working with sequences. This is true both for older approaches as well as newer Transformer-type models. For example the recent <a href="https://www.biorxiv.org/content/10.1101/2023.01.11.523679v3" rel="nofollow noreferrer">Nucleotide Transformer</a>, <a href="https://www.biorxiv.org/content/10.1101/2023.07.11.548628v2" rel="nofollow noreferrer">DNAGPT</a> or <a href="https://academic.oup.com/gigascience/article/doi/10.1093/gigascience/giad054/7230465" rel="nofollow noreferrer">MuLan-Methyl</a> also use k-mers.</p>
  <p>While I'm not aware of a published systematic comparison between k-mers and single bases, I'm sure I've seen papers that vary <code>k</code> as a hyperparameter (so would notice if <code>k=1</code> gives best results), and I have to believe someone somewhere at some point has thought about not using k-mers.</p>
  <p>There are some Deep Learning papers that use individual one hot-encoded nucleotides, for example <a href="https://www.sciencedirect.com/science/article/pii/S0092867418316295" rel="nofollow noreferrer">SpliceAI</a>, but they typically only look at relatively short, fixed-length, sequences (<em>relatively</em>: this paper does go up to 10k).</p>
  <p>As to the &quot;why&quot;, my (limited) understanding is that there are two factors. If you think of NLP, a token is typically a word from the language. Taking each nucleotide as a token means you consider a language with only 4 words, that is a very limited amount of information. It does make sense to use more meaningful tokens: to respond to your comment, even ViT uses patches (and does not attempt to work on individual pixels). Based on our knowledge of biology, we can expect that most sequences have meaningful &quot;motifs&quot; that are made of a few consecutive nucleotides. If you feed the nucleotides to the Transformer, it has to use attention to detect these motifs as well as their long-range interaction. If instead you use a &quot;patch&quot; (or k-mer) that captures entire motifs, this can be learned by an initial linear projection and you only use the attention for long-range interactions.</p>
  <p>Finally, the other reason is computing power, as hinted to in the DNAGPT paper:</p>
  <blockquote>
  <p>In the non-overlapped k-mers strategy, the shift is equal to K, resulting in N/k tokens for an N-length sequence and improving the efficiency by k times.</p>
  </blockquote>
  <p>Maybe taking 1-mers could work just as well as 6-mers, but the number of relationships to consider increases even more, a non-overlapping k-mer strategy does decrease the of interactions to consider, and an overlapping k-mer strategy where each patch is preprocessed (e.g. with a linear model) can also increase efficiency (so to speak the model does not need to consider short-range interactions which are already accounted for).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-21T22:18:52.533Z
Answers.Text: I would have actually given this an upvote if I hadn't just discovered DNABERT-2 where they demonstrate the exact opposite case; That k-mers are computationally inefficient. Also, I have a hard time understanding why this would be so different from proteomics. As I wrote to M_, "You don't need k-mers to use language model; If you tokenize 1-mers, you essentially have a language with four words and can thus use language models. I've done this in proteomics before (having a 21 word language, one for each amino acid, in that case)."
Answers.UserDisplayName: Avatrin
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-22T07:10:31.147Z
Answers.Text: Since you bring proteins into the question: There are some differences between DNA and protein sequences with regards to their biology though. Protein sequences are in many cases the result of stringent selection, while for DNA sequences there is more sequence space that may not have "meaning". Large portions of the genome are non-coding, some of that sequence space is regulatory, but there is also a large fraction that is basically broken transposons. Was your attempt using a "1 amino acid - 1 word" approach in proteomics successful / better than other approaches?
Answers.UserDisplayName: Niklas
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-22T08:06:00.823Z
Answers.Text: @Niklas Are there other approaches? Even AlphaFold one-hot-encodes amino acids, which is the simplest "1 amino acid - 1 word"-approach out there (and more practical in proteomics than in NLP since there aren't as many amino acids as there are words in languages)
Answers.UserDisplayName: Avatrin
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-22T11:17:08.877Z
Answers.Text: Sure there are other conceivable approaches, you could encode amino acids based on various chemical properties (charge, hydrophobicity, side-chain size). Especially for proteomics, you could also expand the alphabet to included chemical modifications. I do not know if they have been tried. ProteinBERT uses a 26-letter alphabet: https://academic.oup.com/bioinformatics/article/38/8/2102/6502274?login=false#394300229
  But I feel we are getting a bit away from your initial question, which I think is difficult to know, unless you ask the creators of DNABert why they chose kmers.
Answers.UserDisplayName: Niklas
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-22T14:27:46.190Z
Answers.Text: For proteins, note also that even with one-hot encoding, you get an alphabet with 22 "words", which is already much better than 4. The [DNABERT-2](https://arxiv.org/abs/2306.15006) paper also doesn't use one-hot encoding, but (see section 3.1 and Fig. 3) builds a vocabulary with 4096 "words" of length 6-7 nucleotides. So I think my tentative answer still stands: single nucleotide encoding (1-mers) hasn't appeared to be better in most of the literature. Note also (in their intro) their reported problem is that they used *overlapping* k-mers, which i)leaks information and ii) increases length
Answers.UserDisplayName: Alexlok
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-22T14:30:44.117Z
Answers.Text: As for other tokenization approaches in DNA, you can also look at [this](https://arxiv.org/pdf/1608.05949.pdf), [that](https://www.mdpi.com/2073-4409/8/2/122), or [that](https://www.hindawi.com/journals/bmri/2014/623149/), with the caveat that I haven't seen these approaches used much in other papers.
Answers.UserDisplayName: Alexlok
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-22T15:12:41.337Z
Answers.Text: Additional clarification: with the overlapping k-mers from DNABERT, you have as many k-mers as nucleotides in the sequence (minus k), so the "computational efficiency" argument of DNABERT-2 applies as well to 1-mers. What is more efficient is either non-overlapping k-mers or other tokenizations that create groups of nucleotides (as in DNABERT-2 or seq2vec).
Answers.UserDisplayName: Alexlok
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-23T10:59:02.747Z
Answers.Text: @Alexlok Actually, I kind of regret how I have phrased my objections in the comments and the summary in the title; The body of the question is fine though. My objection does not apply to non-overlapping k-mers (since then we are not talking about using a rolling window on DNA sequences anymore; So, there's not redundancy in repeating information). I'll edit the title to make this clearer.
Answers.UserDisplayName: Avatrin
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-09-21T19:45:32.263Z
Answers.LastActivityDate: 2023-09-21T19:45:32.263Z
Answers.UserDisplayName: Alexlok
Body: <p>I was reading through the <a href="https://academic.oup.com/bioinformatics/article/37/15/2112/6128680" rel="nofollow noreferrer">DNABERT</a> paper and found that their input features were k-mers. This is essentially using rolling window features.</p>
  <p>Why train a transformer-like model on sequences of the form  <span class="math-container">${a_n,..,a_{n+k}}$</span> rather than training it on the complete sequence <span class="math-container">${a_1,...,a_{m}}$</span> with positional encoding?</p>
  <p>To directly quote the paper:</p>
  <blockquote>
  <p>Instead of regarding each base as a single token, we tokenized a DNA
  sequence with the k-mer representation, an approach that has been
  widely used in analyzing DNA sequences. The k-mer representation
  incorporates richer contextual information for each deoxynucleotide
  base by concatenating it with its following ones. The concatenation of
  them is called a k-mer.</p>
  </blockquote>
  <p>There doesn't seem to be any ablation study in this paper showing that this really is of any benefit.</p>
  <p>I would appreciate any more information: I just don't see how the 3-mers  {ATG, TGG, GGC, GCT} contain more information than the sequence {A,T,G,G,C,T}, 1-mers, with positional encoding.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-09-18T18:57:53.187Z
Comments.Text: @M_ While DNABERT is in the title and is the only example used, it's only because I am quite new to bioinformatics. Moreover, the type of tokenization is completely irrelevant to my question. The question in the body is my main one; Why would you train any model with sequence of k-mers at all? Rolling window features makes sense in many contexts, but I cannot find any example anywhere of rolling window features being used the way they are in the DNABERT paper.
Comments.UserDisplayName: Avatrin
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-09-18T19:14:25.773Z
Comments.Text: @M_  So, you're saying that k-mer for k>1 allows that but not for k=1? Please point me to the source saying that rolling windows are required for transformers to approximate non-linear functions. Which version of the universal approximation theorem is this?
Comments.UserDisplayName: Avatrin
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-09-18T20:31:53.490Z
Comments.Text: @M_ Look, saying "this is really complicated" is not answering the question. Even listing a set of books I'll have to read to understand your claim would be better. You don't need k-mers to use language model; If you tokenize 1-mers, you essentially have a language with four words and can thus use language models. I've done this in proteomics before (having a 21 word language, one for each amino acid, in that case).
Comments.UserDisplayName: Avatrin
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-09-18T20:34:51.383Z
Comments.Text: Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/148614/discussion-between-avatrin-and-m).
Comments.UserDisplayName: Avatrin
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-09-21T19:48:23.200Z
Comments.Text: My answer below is about k-mers with k>1. For positional embedding, if you look at Fig. 1b you can see DNABERT did use positional encodings.
Comments.UserDisplayName: Alexlok
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-09-21T22:10:26.757Z
Comments.Text: @Alexlok Actually, I just discovered there's a DNABERT-2 by the same team where they abandon k-mers altogether and get better performance (writing " However, we argue that the
  computation and sample inefficiencies introduced by k-mer tokenization are primary obstacles in
  developing large genome foundational models." in the abstract). So, I no longer believe this needs any explanation; Reading it, it feels like using k-mers was a mistake. Fair point about figure 1b, though; I completely missed that.
Comments.UserDisplayName: Avatrin
Tags: <k-mer><deep-learning>
Title: Why does DNABert use overlapping k-mers as input?
ThreadText: # Why does DNABert use overlapping k-mers as input?
  
  (Asked by: username_0 on 2023-09-15)
  
  I was reading through the [DNABERT](https://academic.oup.com/bioinformatics/article/37/15/2112/6128680) paper and found that their input features were k-mers. This is essentially using rolling window features.
  
  Why train a transformer-like model on sequences of the form ${a\_n,..,a\_{n+k}}$ rather than training it on the complete sequence ${a\_1,...,a\_{m}}$ with positional encoding?
  
  To directly quote the paper:
  
  > Instead of regarding each base as a single token, we tokenized a DNA
  > sequence with the k-mer representation, an approach that has been
  > widely used in analyzing DNA sequences. The k-mer representation
  > incorporates richer contextual information for each deoxynucleotide
  > base by concatenating it with its following ones. The concatenation of
  > them is called a k-mer.
  
  There doesn't seem to be any ablation study in this paper showing that this really is of any benefit.
  
  I would appreciate any more information: I just don't see how the 3-mers {ATG, TGG, GGC, GCT} contain more information than the sequence {A,T,G,G,C,T}, 1-mers, with positional encoding.
  
  **Tags:** k-mer, deep-learning
  
  > **Comments:**
  > **username_0**: @M_ While DNABERT is in the title and is the only example used, it's only because I am quite new to bioinformatics. Moreover, the type of tokenization is completely irrelevant to my question. The question in the body is my main one; Why would you train any model with sequence of k-mers at all? Rolling window features makes sense in many contexts, but I cannot find any example anywhere of rolling window features being used the way they are in the DNABERT paper.  
  > **username_0**: @M_  So, you're saying that k-mer for k>1 allows that but not for k=1? Please point me to the source saying that rolling windows are required for transformers to approximate non-linear functions. Which version of the universal approximation theorem is this?  
  > **username_0**: @M_ Look, saying "this is really complicated" is not answering the question. Even listing a set of books I'll have to read to understand your claim would be better. You don't need k-mers to use language model; If you tokenize 1-mers, you essentially have a language with four words and can thus use language models. I've done this in proteomics before (having a 21 word language, one for each amino acid, in that case).  
  > **username_0**: Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/148614/discussion-between-username_0-and-m).  
  > **username_1**: My answer below is about k-mers with k>1. For positional embedding, if you look at Fig. 1b you can see DNABERT did use positional encodings.  
  > **username_0**: @username_1 Actually, I just discovered there's a DNABERT-2 by the same team where they abandon k-mers altogether and get better performance (writing " However, we argue that the computation and sample inefficiencies introduced by k-mer tokenization are primary obstacles in developing large genome foundational models." in the abstract). So, I no longer believe this needs any explanation; Reading it, it feels like using k-mers was a mistake. Fair point about figure 1b, though; I completely missed that.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2023-09-16. Score: 1
  
  NLP and vectorisation is used to trap non-linearity which is highly applicable to sentences written in English.
  Vectorisation of k-mers for an overlapping sliding window is weird because it's trying to assess the functionality of non-coding sequence, i.e. "silent" and non-cds mutations will be the dominant mutation class, but it would identify localised co-mutations, i.e. within a k-mer.
  
  The only application I can think is stuff like identifying promoters or mutations in promoters, i.e. non-coding regions with a known function and can be trained against appropriate independent experimental observations, e.g. gene expression. If the k-mers were large it might work for RNA secondary structure because it would trap compensatory mutations. Vectorisation for individual nucleotides, i.e. dumbie variables, would not be successful at trapping compensatory mutations.
  
  In summary it has niche application.
  
  BERT is a famous large language model BTW.
  
  ---
  
  If k-mer =3 that's about non-linearity of proteins, but it depends how the sliding window is deployed. It depends on the step size of the sliding window.
  
  To try and answer this better, proteins fold back on themself triggering "co-evolution" or more accurately "covariance" between non-linear sites. This defines the triplet codon:
  
  * in machine learning this is needed because it will struggle to find it by itself
  * it will help it identify co-evolving mutations at non-linear locations across the gene
  
  It might also identify selection events better.
  
  **Summary** If you've sat down and thought the equation the RNN is attempting to unravel its mind-boggling. More worrisome does it really do it? It's really complicated to simply discuss, but when you give it key information the ML/DL gets there quicker. The authors will be aware of that in their training and testing.
  
  Honestly, we're at the limits of reasonable application of ML/DL without going into RasNet type infrastructure. My system is different the idea is the same - give the training model the key biological information, it gets to the answer quicker, a lot quicker.
  
  > **Comments:**
  > **username_0**: I am sorry, but this does not answer my question regarding why one would use k-mers for k>1 versus 1-mers with positional encoding as is the norm with transformers. Not just BERT and other NLP transformer-like models (aka LLMs) but even ViT uses positional encoding  
  > **username_2**: I've tried my best above.  
  
  ---
  
  ### Answer by username_1 on 2023-09-21. Score: 0
  
  [I'm not an expert in this field, this is only my "best try". Maybe you could get better mathematically motivated answers on ai.stackexchange]
  
  First note that, as pointed in the DNA BERT paper, k-mers are a very common approach to working with sequences. This is true both for older approaches as well as newer Transformer-type models. For example the recent [Nucleotide Transformer](https://www.biorxiv.org/content/10.1101/2023.01.11.523679v3), [DNAGPT](https://www.biorxiv.org/content/10.1101/2023.07.11.548628v2) or [MuLan-Methyl](https://academic.oup.com/gigascience/article/doi/10.1093/gigascience/giad054/7230465) also use k-mers.
  
  While I'm not aware of a published systematic comparison between k-mers and single bases, I'm sure I've seen papers that vary `k` as a hyperparameter (so would notice if `k=1` gives best results), and I have to believe someone somewhere at some point has thought about not using k-mers.
  
  There are some Deep Learning papers that use individual one hot-encoded nucleotides, for example [SpliceAI](https://www.sciencedirect.com/science/article/pii/S0092867418316295), but they typically only look at relatively short, fixed-length, sequences (*relatively*: this paper does go up to 10k).
  
  As to the "why", my (limited) understanding is that there are two factors. If you think of NLP, a token is typically a word from the language. Taking each nucleotide as a token means you consider a language with only 4 words, that is a very limited amount of information. It does make sense to use more meaningful tokens: to respond to your comment, even ViT uses patches (and does not attempt to work on individual pixels). Based on our knowledge of biology, we can expect that most sequences have meaningful "motifs" that are made of a few consecutive nucleotides. If you feed the nucleotides to the Transformer, it has to use attention to detect these motifs as well as their long-range interaction. If instead you use a "patch" (or k-mer) that captures entire motifs, this can be learned by an initial linear projection and you only use the attention for long-range interactions.
  
  Finally, the other reason is computing power, as hinted to in the DNAGPT paper:
  
  > In the non-overlapped k-mers strategy, the shift is equal to K, resulting in N/k tokens for an N-length sequence and improving the efficiency by k times.
  
  Maybe taking 1-mers could work just as well as 6-mers, but the number of relationships to consider increases even more, a non-overlapping k-mer strategy does decrease the of interactions to consider, and an overlapping k-mer strategy where each patch is preprocessed (e.g. with a linear model) can also increase efficiency (so to speak the model does not need to consider short-range interactions which are already accounted for).
  
  > **Comments:**
  > **username_0**: I would have actually given this an upvote if I hadn't just discovered DNABERT-2 where they demonstrate the exact opposite case; That k-mers are computationally inefficient. Also, I have a hard time understanding why this would be so different from proteomics. As I wrote to M_, "You don't need k-mers to use language model; If you tokenize 1-mers, you essentially have a language with four words and can thus use language models. I've done this in proteomics before (having a 21 word language, one for each amino acid, in that case)."  
  > **username_3**: Since you bring proteins into the question: There are some differences between DNA and protein sequences with regards to their biology though. Protein sequences are in many cases the result of stringent selection, while for DNA sequences there is more sequence space that may not have "meaning". Large portions of the genome are non-coding, some of that sequence space is regulatory, but there is also a large fraction that is basically broken transposons. Was your attempt using a "1 amino acid - 1 word" approach in proteomics successful / better than other approaches?  
  > **username_0**: @username_3 Are there other approaches? Even AlphaFold one-hot-encodes amino acids, which is the simplest "1 amino acid - 1 word"-approach out there (and more practical in proteomics than in NLP since there aren't as many amino acids as there are words in languages)  
  > **username_3**: Sure there are other conceivable approaches, you could encode amino acids based on various chemical properties (charge, hydrophobicity, side-chain size). Especially for proteomics, you could also expand the alphabet to included chemical modifications. I do not know if they have been tried. ProteinBERT uses a 26-letter alphabet: https://academic.oup.com/bioinformatics/article/38/8/2102/6502274?login=false#394300229 But I feel we are getting a bit away from your initial question, which I think is difficult to know, unless you ask the creators of DNABert why they chose kmers.  
  > **username_1**: For proteins, note also that even with one-hot encoding, you get an alphabet with 22 "words", which is already much better than 4. The [DNABERT-2](https://arxiv.org/abs/2306.15006) paper also doesn't use one-hot encoding, but (see section 3.1 and Fig. 3) builds a vocabulary with 4096 "words" of length 6-7 nucleotides. So I think my tentative answer still stands: single nucleotide encoding (1-mers) hasn't appeared to be better in most of the literature. Note also (in their intro) their reported problem is that they used *overlapping* k-mers, which i)leaks information and ii) increases length  
  > **username_1**: As for other tokenization approaches in DNA, you can also look at [this](https://arxiv.org/pdf/1608.05949.pdf), [that](https://www.mdpi.com/2073-4409/8/2/122), or [that](https://www.hindawi.com/journals/bmri/2014/623149/), with the caveat that I haven't seen these approaches used much in other papers.  
  > **username_1**: Additional clarification: with the overlapping k-mers from DNABERT, you have as many k-mers as nucleotides in the sequence (minus k), so the "computational efficiency" argument of DNABERT-2 applies as well to 1-mers. What is more efficient is either non-overlapping k-mers or other tokenizations that create groups of nucleotides (as in DNABERT-2 or seq2vec).  
  > **username_0**: @username_1 Actually, I kind of regret how I have phrased my objections in the comments and the summary in the title; The body of the question is fine though. My objection does not apply to non-overlapping k-mers (since then we are not talking about using a rolling window on DNA sequences anymore; So, there's not redundancy in repeating information). I'll edit the title to make this clearer.  
  
  ---
  
  