# Tag Info

## Hot answers tagged k-mer

31 votes
Accepted

### Why do some assemblers require an odd-length kmer for the construction of de Bruijn graphs?

From the manual of Velvet: it must be an odd number, to avoid palindromes. If you put in an even number, Velvet will just decrement it and proceed. the palindromes in biology are defined as ...
• 5,517
14 votes

### Why do some assemblers require an odd-length kmer for the construction of de Bruijn graphs?

To expand on the answer above, in case it isn't clear, we show: Why palindromic sequences must be even in length Why palindromic sequences induce self-loops in a de Bruijn graph Why self loops in a ...
• 243
9 votes

### Are there any rolling hash functions that can hash a DNA sequence and its reverse complement to the same value?

Let f and r be two integers. They always keep the k-mer on the forward and reverse strand, respectively. At a new base ...
• 6,485
8 votes
Accepted

### How do kmer counters determine which kmer is 'canonical'?

When a k-mer is identical to its reverse complement, both are canonical. Note that a canonical k-mer is a sequence, irrelevant to its position(s) in the input string. More precisely, give a string $s$,...
• 6,485
8 votes
Accepted

### Are there any rolling hash functions that can hash a DNA sequence and its reverse complement to the same value?

A rolling hash function for DNA sequences called ntHash has recently been published in Bioinformatics and the authors dealt with reverse complements: Using this table, we can easily compute the ...
• 1,899
8 votes
Accepted

### Stranded vs. unstranded library preparation protocols in RNAseq

Short answer: cDNA is double-stranded. I'll try to explain the concepts surrounding this with a nanopore read, where the cDNA component of the read (from the mouse genome) is indicated in a light ...
• 13.8k
7 votes
Accepted

### How to calculate the memory usage of storing kmers in RAM

To follow up on Devon Ryan's answer, I thought it would be a little fun to write a Python script that demonstrates using a bit array to maintain a presence/absence table. Note: I wrote a C++ port ...
• 3,125
7 votes
Accepted

### How to write a hash function for canonical kmers?

You can convert any string hash function to a "canonical" DNA string hash function. Given a DNA string $s$, let $\overline{s}$ be its Watson-Crick reverse complement. Suppose $h:\Sigma^*\to\mathbb{Z}$...
• 6,485
7 votes

### How to make a distinction between the "classical" de Bruijn graph and the one described in NGS papers?

Several papers have made this distinction, and a few indeed use different terms to distinguish between them. For example, Kazaux et al. (2016) acknowledge that: These constraints favour the use of ...
• 669
7 votes

### Are there any rolling hash functions that can hash a DNA sequence and its reverse complement to the same value?

If your goal is to minimise storage by just having one hash per kmer and its reverse complement, there is a simple solution for non-rolling hashes. For any sequence S, you compute and store the hash ...
• 754
7 votes

### Have DNA motifs 6-12bp long, trying to get conservation scores

In case you have only ACGT in your motifs The short motifs make it sound as if you are in the business of looking for a kmer counter. You can choose to use existing software or build your own. Using ...
• 754
7 votes

### How to use Python to count k-mers?

I wrote a command-line k-mer counter called kmer-counter that will output results in a form that your Python script can consume: https://github.com/alexpreynolds/...
• 3,125
6 votes
Accepted

### Server for finding kmers in set of sequences

One Codex is powerful and user friendly, and works in a similar way to Kraken underneath https://www.onecodex.com/ The Kaiju web server might be of interest and is more sensitive than exclusively k-...
• 248
6 votes
Accepted

### Is there a standard k-mer count file format?

Not as far as I am aware. The Ray assembler used to (and possibly still does) store the kmers as FASTA files where the header was the count of the sequence, which I thought was a pretty neat ...
• 13.8k
6 votes

### Why do BLASTn and prokka not seem to be searching the whole fasta file?

With a k-mer size of 28 it shouldn't be finding that many matches. And the prokka results are suspicious as well. Maybe you have multiple contigs (none larger than 100kb) in that file? What is the ...
6 votes

### How to calculate the memory usage of storing kmers in RAM

I think that my calculations must be wrong. Otherwise, how could programs count kmers in RAM? Hash table based k-mer counters only keep k-mers seen in data. For $16<k\le32$, you need 64-bit ...
• 6,485
6 votes
Accepted

### How to get the count of each kmer past 255 using khmer

255 is the default maximum size of a Counttable in khmer. You want to do the following: ...
• 19.6k
6 votes

### Counting repeated kmers sequences that match at least x % of reads sequence

The following javascript does what you want. You need node.js to run it. It should be easy to translate the code to Python. I have not carefully tested it. Use with caution. EDIT (response to new ...
• 6,485
6 votes
Accepted

### What is the most compact data structure for canonical k-mers with the fastest lookup time?

The question and the accepted answer are not about k-mer data structure at all, which I will explain in detail below. I will first answer the actual question OP intends to ask. The simplest way to ...
• 6,485
5 votes

### How to efficiently compute the exact percentage of non-unique k-mers in a genome for given k?

You can do all of that with khmer. For example, abundance-dist-single.py produces a file with columns: k-mer abundance, ...
• 19.6k
5 votes

### Stranded vs. unstranded library preparation protocols in RNAseq

There are a number of library preparation methods out there. Some, like the popular dUTP-based methods, result in libraries where the orientation of a read's alignment confers information regarding ...
• 19.6k
5 votes

### Is there a standard k-mer count file format?

Based on my experience reviewing k-mer counting software and as a core contributor to the khmer project, I can confidently say that there is no widely used standard format.
• 5,060
5 votes

### How to calculate the memory usage of storing kmers in RAM

If you simply need a set of present/absent k-mers and your kmer length is short, then convert the sequence length to an integer (a 13-mer would require 26 bits or 4 bytes) and use that as an index ...
• 19.6k
5 votes

### How to write a hash function for canonical kmers?

However you want. One way to do this is to generate both the forward and reverse complement kmers, then choose the lexicographically-least kmer for the storage key. To delve further into this ...
• 13.8k
5 votes
Accepted

### How to use Python to count k-mers?

If you want to count the number of unique k-mers that occur in your data set, you should use the unique-kmers.py script, which implements a HyperLogLog-based cardinality estimator. If the number of ...
• 5,060
5 votes

• 4,845
5 votes
Accepted

### estimate genome size: kmer-based approach from PacBio reads

I don't think there is a method that would estimate a genome size using raw long reads. The genome size estimates based on raw reads are done by fitting a model to kmer spectra (for instance ...
• 5,517
5 votes
Accepted

### mapping heteryzygous kmers on a genome

I don't know if this is the best answer, but one quick-n-dirty approach I commonly use involves tweaking bwa mem to report only perfect matches. So in your case, ...
• 5,060
4 votes

### How to make a distinction between the "classical" de Bruijn graph and the one described in NGS papers?

In addition to the regular De Bruijn graph as depicted on the wikipedia, some implementations in bioinformatics feature additional processing. I guess the main reason figure 1 in the paper you linked (...
• 455

Only top scored, non community-wiki answers of a minimum length are eligible