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 ...
- 61
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
Formula for k-mer coverage
I was still puzzled from the answers, so I tried to calculate with all the steps. I take this definition "$C_k$ is the number of reads containing a k-mer." and corresponding definition for coverage ($...
- 5,517
5
votes
Are there any rolling hash functions that can hash a DNA sequence and its reverse complement to the same value?
At its easiest, you just store the forward ($F$) and reverse ($R$) hash value.
You update the forward hash value by conventional means, e.g. bit-shifting the base value into its lower bits:
$$
F_{n +...
- 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