How to find number of unique n-mers in genome?

Question

[endrebak]

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.

[lh3]

Jellyfish or kmc2? Not sure if they work with chromosome-long sequences.

[endrebak]

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 )

[GenoMax]

kmercountexact.sh from BBMap may be worth a try. Some prior discussion: How to find the shortest k-mer length that is unique in a large genome.

Answer 1

[kloetzl]

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.