Questions tagged [k-mer]

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

Filter by
Sorted by
Tagged with
1 vote
1 answer
81 views

Why does randomized motif search work?

I'm looking for intuition for why a randomized motif search works. My current thinking is as follows: We are selecting many random kmers from our DNA sequences. The chosen kmers will bias the profile ...
user avatar
  • 127
1 vote
1 answer
57 views

Comparing homozygosity of k-mer plots

Attached are two kmer plots from two closely related species. Is that safe to say that the one on the left has higher homozygosity than the one in the right k-mer plot, due to a low to almost flat ...
user avatar
0 votes
1 answer
60 views

Understand this Kmer plot from Merqury?

The attached figure is generated based on Illumina reads from multiple individuals compared to genome assembly. Looks like there are a lot of kmers are reads only (grey colored). Also, a blue peak (2x ...
user avatar
1 vote
1 answer
47 views

Why do we count reverse compliments when counting kmers in a single DNA strand?

When looking for repeat patterns in a DNA sequence, we can look for the pattern and its reverse compliment with up to d mismatches. However, why do we look for ...
user avatar
  • 127
1 vote
1 answer
45 views

Assembling all transcripts for an individual gene? (using single sequence to seed the assembly)

Let's say I have a candidate gene and I believe that in an individual sample, the genome sequence differs from the reference which then interferes with alignment. Is there a way for me to do a "...
user avatar
  • 1,498
0 votes
1 answer
68 views

calculating kmer nucleotide frequency per column

I have a list of sequences: CAGGTAGCC CCGGTCAGA AGGGTTTGA TTGGTGAGG CAAGTATGA ACTGTATGC CTGGTAACC Each sequence is nine nucleotides long. I want to calculate ...
user avatar
0 votes
1 answer
57 views

Time complexity of the Neighbors function

I implemented the following find_neighbors_with_expected_hamming_distance function that generates all k-mers of Hamming distance at most d from the given Pattern. ...
user avatar
2 votes
2 answers
226 views

Construct the Overlap Graph of a Collection of k-mers

I am doing a course on graph algorithms in genome sequencing and the current assignment involves building an overlap graph from a bunch of k-mers. Formally the problem is as follows: Input: A ...
user avatar
  • 21
3 votes
1 answer
38 views

Finding 2000 bp sequences that occur more than once in the genome

I am looking for a software that can identify long sequences (1500-2000 bp) that occur more than once in my genome of interest. A k-mer counter like KMC could have worked, but KMC has a max limit of ...
user avatar
  • 33
1 vote
3 answers
304 views

How to count the kmer occurrence in FASTA file considering overlapping and reverse complement?

I am using count_overlap() for counting the kmers from Biopython . Does it take the reverse complement of kmer into account? I need to count reverse complement too
user avatar
  • 21
3 votes
1 answer
90 views

Truble to run a multiprocessing kmer count script

Hi there I have this code: ...
user avatar
1 vote
1 answer
81 views

Significance of k-mer length in COVID-19 sequence analysis?

I'm getting started in biology and bioinformatics with sequencing the SARS-Cov-2 or Coronavirus genome. I'm interested in this code which identifies k-mers in the genome: ...
user avatar
0 votes
1 answer
97 views

Will using smaller kmers help get larger contigs? If not, then what?

I've been using MEGAHIT to assemble metagenomes, with particular focus on specific genomic areas. Sometimes all I get is gene fragments or pathway fragments (eg. if I know that genes A, B, C, D and E ...
user avatar
  • 595
1 vote
3 answers
99 views

K means clustering, would PCA be a better option?

I have the data below. I need to use a clustering method to classify them and into categories of "Heterozygotote, Allele 1, Allele 2 and No Call. The values in RFU1 and RFU2 are used to determine the ...
user avatar
4 votes
1 answer
101 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 ...
user avatar
  • 595
3 votes
2 answers
391 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: ...
user avatar
  • 5,287
3 votes
1 answer
498 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 ...
user avatar
  • 5,287
13 votes
1 answer
726 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 ...
user avatar
  • 3,071
3 votes
1 answer
163 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] ...
user avatar
8 votes
2 answers
1k 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. ...
user avatar
  • 2,644
8 votes
1 answer
396 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. ...
user avatar
  • 173
6 votes
1 answer
94 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 ...
user avatar
  • 69
9 votes
1 answer
348 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 ...
user avatar
  • 173
7 votes
2 answers
1k 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 ...
user avatar
9 votes
3 answers
578 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-...
user avatar
  • 3,071
7 votes
2 answers
730 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 ...
user avatar
  • 3,071
8 votes
1 answer
2k 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 ...
user avatar
  • 3,071
7 votes
1 answer
236 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 ...
user avatar
  • 2,234
8 votes
2 answers
3k 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 ...
user avatar
  • 163
14 votes
2 answers
269 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.
user avatar
3 votes
1 answer
185 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 ....
user avatar
4 votes
1 answer
187 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 (...
user avatar
8 votes
2 answers
10k 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 ...
user avatar
  • 2,649
8 votes
3 answers
159 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 ...
user avatar
34 votes
2 answers
2k 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?
user avatar
  • 5,287
14 votes
3 answers
440 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 ...
user avatar
23 votes
4 answers
2k 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 ...
user avatar