I want to find the number of unique n-mers in the genome, for arbitrary ns (say 30). Is there software that can do this?
If not, how could I do it without requiring excessive ram? I guess a suffix-tree would be the best option, but all the implementations I have found are either inefficient or 10 years old.
1 answer
A suffix array might help. Compute SA and LCP. Then do a linear scan of the LCP array for each entry i with LCP[i] < n && LCP[i+1] < n you have found a unique n-mer (given strlen(S+SA[i]) >= n). For SA construction you might want to use https://github.com/y-256/libdivsufsort
Alternatively you could apply hashing to your kmers. There are a lot of tools out there for that job. See if one fits your needs.
Log in to answer this question.
-
RNA STAR and trimming
written by casio •
-
Sbatch slurm job
written by marco.barr •
-
Open files created with bwa
written by mostafarafiepour
-
Demultiplexing single cell QIAseq UPX 3 Transcriptome Kits fastq files
written by user31888
-
Tool: Script to compute the effective genome size: epic-effective
written by endrebak
-
Finding most frequent k-mers in Fastq file
written by murat •
-
How to extract a fasta sequence row using AWK into new file that has no "_" in it.
written by usamaabid3 •
-
DNA composition - all k-mers and their frequency in some sequencing data
written by John
-
Generate kmer profiles from a bunch of peptide sequences
written by Owen S.
-
Comparing Annotations From Old Ref To New Ref Sequence
written by rob234king
Jellyfish or kmc2? Not sure if they work with chromosome-long sequences.
I want to thank all responders and will upvote on monday when I get to my computer. I'll start with jellyfish since 2.0 accepts full genomes according to the docs ( Section 1.1.2 in the user guide: http://www.genome.umd.edu/docs/JellyfishUserGuide.pdf )
kmercountexact.shfrom BBMap may be worth a try. Some prior discussion: How to find the shortest k-mer length that is unique in a large genome.