Hot answers tagged

29 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 ...
user avatar
  • 5,287
13 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 ...
user avatar
  • 233
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 ...
user avatar
  • 5,645
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$,...
user avatar
  • 5,645
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 ...
user avatar
  • 11.5k
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 ...
user avatar
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}$...
user avatar
  • 5,645
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 ...
user avatar
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 ...
user avatar
  • 744
7 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 ...
user avatar
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 ...
user avatar
  • 744
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/...
user avatar
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-...
user avatar
  • 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 ...
user avatar
  • 11.5k
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 ...
user avatar
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 ...
user avatar
  • 5,645
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: ...
user avatar
  • 19.3k
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 ...
user avatar
  • 5,645
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 ...
user avatar
  • 5,645
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, ...
user avatar
  • 19.3k
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 ...
user avatar
  • 19.3k
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.
user avatar
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 ...
user avatar
  • 19.3k
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 ...
user avatar
  • 11.5k
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 ...
user avatar
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 ($...
user avatar
  • 5,287
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 +...
user avatar
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 ...
user avatar
  • 5,287
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, ...
user avatar
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 (...
user avatar

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