1
$\begingroup$

I was reading through the DNABERT 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.

$\endgroup$
6
  • $\begingroup$ @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. $\endgroup$
    – Avatrin
    Commented Sep 18, 2023 at 18:57
  • $\begingroup$ @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? $\endgroup$
    – Avatrin
    Commented Sep 18, 2023 at 19:14
  • $\begingroup$ @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). $\endgroup$
    – Avatrin
    Commented Sep 18, 2023 at 20:31
  • $\begingroup$ Let us continue this discussion in chat. $\endgroup$
    – Avatrin
    Commented Sep 18, 2023 at 20:34
  • $\begingroup$ 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. $\endgroup$
    – Alexlok
    Commented Sep 21, 2023 at 19:48

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – Avatrin
    Commented Sep 16, 2023 at 21:51
  • $\begingroup$ I've tried my best above. $\endgroup$
    – M__
    Commented Sep 19, 2023 at 0:01
0
$\begingroup$

[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, DNAGPT or MuLan-Methyl 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, 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).

$\endgroup$
8
  • $\begingroup$ 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)." $\endgroup$
    – Avatrin
    Commented Sep 21, 2023 at 22:18
  • $\begingroup$ 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? $\endgroup$
    – Niklas
    Commented Sep 22, 2023 at 7:10
  • $\begingroup$ @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) $\endgroup$
    – Avatrin
    Commented Sep 22, 2023 at 8:06
  • $\begingroup$ 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: academic.oup.com/bioinformatics/article/38/8/2102/… 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. $\endgroup$
    – Niklas
    Commented Sep 22, 2023 at 11:17
  • $\begingroup$ 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 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 $\endgroup$
    – Alexlok
    Commented Sep 22, 2023 at 14:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.