Questions tagged [k-mer]

for questions related to k-mer based algorithms, data structures, or concepts

Filter by
Sorted by
Tagged with
4
votes
1answer
80 views

Generating DNA sequences with constraints

I would like some advice on potential strategies to address the following problem. I want to write a program that will generate DNA sequences that are optimized on two constraints based on an input ...
1
vote
2answers
149 views

mapping heteryzygous kmers on a genome

I have a set (a couple of millions) of kmer pairs of known length (usually 21) that I know that are heterozygous in the middle nucleotide. For instance: ...
3
votes
1answer
157 views

python does not quit when the input file is too big

I have a script that extracts the set of unique kmer pairs from a kmer dump file (& then using them downstream to guess ploidy). The script seems to work correctly (it's reporting a meaningful ...
9
votes
1answer
383 views

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

edit: Results are current as of Dec 4, 2018 13:00 PST. Background K-mers have many uses in bioinformatics, and for this reason it would be useful to know the most RAM-efficient and fastest way to ...
3
votes
0answers
90 views

Histosketch vs Count-Min sketch: preserving similarity

A preprint describing a new tool and its application to microbiome analysis was recently published in bioRxiv[1]. At the core of this new tool, HULK, is a new data structure called a histosketch[2] ...
8
votes
1answer
675 views

estimate genome size: kmer-based approach from PacBio reads

Can anyone suggest a software/method for kmer analysis using PacBio reads (RSII)? Something similar to Jellyfish, that I saw in a nice tutorial - but must be suitable for long, noisy reads. ...
8
votes
1answer
237 views

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

Working on a fastQ file, I would like to get the occurrences of repeated sequences for all possible kmers of a given length that cover at least 90% of the read's length for the whole data set. ...
6
votes
1answer
68 views

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

I'm looking for some software that can "efficiently" (time and memory) compute the exact percentage of non-unique k-mers in a genome for given k. I don't need the k-mers or the abundances itself, I ...
8
votes
1answer
260 views

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

I have a Fastq file and I want to get the exact count of each possible kmer from this file. On a previous post called How to use khmer to count k-mers? Daniel Standage proposed a custom script based ...
7
votes
2answers
745 views

Stranded vs. unstranded library preparation protocols in RNAseq

I've been reading this paper lately: Sailfish Enables Alignment-Free Isoform Quantification from RNA-Seq Reads Using Lightweight Algorithms I don't really understand the second paragraph under ...
8
votes
3answers
378 views

How to calculate the memory usage of storing kmers in RAM

I want to write a program in C++ that stores kmers in a hash or in a trie. How can I calculate how much RAM I would need for each type of data structure? For this application my kmers are strand-...
7
votes
2answers
376 views

How to write a hash function for canonical kmers?

This question is a follow up from How do kmer counters determine which kmer is 'canonical'?. In that question we learned that kmer counting programs use a 2-bit hash function to internally represent ...
6
votes
1answer
653 views

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

When counting canonical kmers, ie kmers in which both the forward and reverse complement of a sequence are treated as identical, how do kmer counting programs decide which kmer to use as the canonical ...
7
votes
1answer
193 views

server for finding kmers in set of sequences

Is there a server/website somewhere where I can submit a list of DNA/RNA sequences and find the list of kmers hits and organisms where it's found? I checked the kraken website, but they don't have a ...
8
votes
2answers
1k views

Formula for k-mer coverage

Let $C$ be base coverage, $R$ is the length of reads and $K$ is the length of $k$-mer. Then $k$-mer coverage $C_k$ can be computed as $C_k = C\cdot(R - K + 1)/R$. Could someone please explain why is ...
12
votes
2answers
177 views

Is there a standard k-mer count file format?

I am doing a research project involving calculating k-mer frequencies and I am wondering if there is any standard file format for storing k-mer counts.
3
votes
1answer
120 views

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

When I use blastn and prokka (I will detail exactly how I did so below) on a 2.8 million bp fasta file I get output start/end numbers that do not seem to cover the entire genome. Starting with a ....
4
votes
1answer
129 views

Preparing binary matrix data for Scikit classification algorithms

I made this post in regular stack overflow but I was told about this awesome feature by @nbryans. I am a researcher (my programming knowledge is small) conducting analysis on a set of antibiotic (...
7
votes
2answers
5k views

How to use Python to count k-mers?

I have some FASTQ sequence files and a FASTA file for some regions I'm interested in. I would like: Build an index for the FASTA file Use the index to count number of k-mers occurred in my sequence ...
8
votes
3answers
103 views

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

I have about 200 short nucleotide motifs (6-12 bp in length) from the human genome, and I'm trying to see how conserved they are across vertebrates. I was thinking that I'd need to make a bed file ...
30
votes
2answers
1k views

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

Why do some assemblers like SOAPdenovo2 or Velvet require an odd-length k-mer size for the construction of de Bruijn graph, while some other assemblers like ABySS are fine with even-length k-mers?
14
votes
3answers
293 views

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

In Computer Science a De Bruijn graph has (1) m^n vertices representing all possible sequences of length n over ...
22
votes
4answers
1k views

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

A common bioinformatics task is to decompose a DNA sequence into its constituent k-mers and compute a hash value for each k-mer. Rolling hash functions are an appealing solution for this task, since ...