Questions tagged [k-mer]
for questions related to k-mer based algorithms, data structures, or concepts
42
questions
2
votes
0
answers
38
views
Custom-made kraken2 catalogue
I am looking for instructions on creating a custom-made kraken2 catalogue from the sequences of my choice and the corresponding phylogenetic tree in newick notation.
I will appreciate an input on ...
- 381
1
vote
1
answer
77
views
Remove files after process is terminated
In my pipeline nextflow, I create a channel with channel.fromSRA and the channel contains lots of heavy files.fastq.gz. Then I have a first process to unzip files and transform them in files.fasta and ...
- 21
3
votes
2
answers
56
views
hierarchical clustering of kmers and their counts
I have a list of kmers and their frequencies broken down like this:
...
- 494
2
votes
2
answers
63
views
Sort dictionary in descending order
Hi I am looking to sort a list of kmers into descending order. I used KMC to obtain a list of kmers from a fastq file separated by tab (e.g.; kmer count). From there I have written this python script ...
- 494
1
vote
1
answer
253
views
DNA genome string reconstruction from k-mer
I have the following quiz question, but the Pattern1 for both (ACC|ATA) and (CGA|ACT) are unique (just grep for ...
- 143
1
vote
1
answer
313
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 ...
- 127
1
vote
1
answer
102
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 ...
0
votes
1
answer
195
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 ...
1
vote
1
answer
80
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 ...
- 127
1
vote
1
answer
57
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 "...
- 1,568
0
votes
1
answer
163
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 ...
- 103
0
votes
1
answer
123
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.
...
2
votes
2
answers
397
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 ...
- 21
3
votes
1
answer
40
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 ...
- 33
1
vote
3
answers
532
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
- 21
3
votes
1
answer
110
views
Truble to run a multiprocessing kmer count script
Hi there I have this code:
...
1
vote
1
answer
91
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:
...
- 13
0
votes
1
answer
143
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 ...
- 777
1
vote
3
answers
123
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 ...
4
votes
1
answer
111
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 ...
- 595
3
votes
2
answers
446
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:
...
- 5,467
3
votes
1
answer
565
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 ...
- 5,467
13
votes
1
answer
800
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,111
3
votes
1
answer
185
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] ...
- 5,010
8
votes
2
answers
2k
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. ...
- 2,656
8
votes
1
answer
456
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.
...
- 173
6
votes
1
answer
99
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 ...
- 69
9
votes
1
answer
382
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 ...
- 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 ...
- 309
9
votes
3
answers
612
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-...
- 3,111
7
votes
2
answers
827
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 ...
- 3,111
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 ...
- 3,111
7
votes
1
answer
259
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 ...
- 2,274
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 ...
- 263
14
votes
2
answers
292
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.
- 399
3
votes
1
answer
192
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 ....
- 193
4
votes
1
answer
197
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 (...
- 193
8
votes
2
answers
11k
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 ...
- 2,719
8
votes
3
answers
164
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 ...
- 133
35
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?
- 5,467
14
votes
3
answers
469
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 ...
- 669
24
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 ...
- 5,010