Eric T Dawson
June 2016

rkmh performs identification of individual reads, identity-based read filtering, and alignment-free variant calling using MinHash (as implemented in Mash). It is compatible with Mash and sourmash via JSON exchange.

We're using rkmh to identify which strains are present in infections with multiple strains of the same virus. rkmh could also be used to remove reads from contaminants or call mutations in novel strains relative to a nearby reference. You could even select out only reads from a pathogen sample contaminated with human DNA.

MIT, but please cite the repository if you use it.

The only external dependencies should be zlib and a compiler supporting OpenMP. To download and build:

                git clone --recursive https://github.com/edawson/rkmh.git  
                cd rkmh  
                make  

This should build rkmh and its library dependencies (mkmh and murmur3).

Imagine you have a bunch of reads sequenced from a viral infection and you want to select only those that are from the virus (i.e. remove host reads).

Now you can:

rkmh filter -f reads.fq -r viral_refs.fa -t 4 -k 20 -s 2000

You can also pass the -z param to stream to accomplish the same thing.

rkmh can now stream reads through, using roughly constant memory. This command performs almost identically to classify and performs the same read classification task by default:

rkmh stream -r refs.fa -f reads.fa -k 12 -s 1000

But also permits this:

cat reads.fq | ./rmkmh stream -i -r refs.fa -k 12 -s 1000

which will use 64 * ( (number of refs * sketchsize) + sketchsize ) bits of memory after references are hashed. I'm working on reducing the amount of memory used during the initial hashing as well, though a human genome is feasible in 32ish gigabytes of ram.

The -M flag for stream uses a modified hash table counter which takes up only ~80MB of memory; however, it is prone to collisions if the sketch size and reference genome become very large and the kmer size very small. Its performance on most small genome's is identical to that of classify, but if you cannot tolerate collisions we suggest you use the classify command.

The -I flag is implemented the same way as the -M flag, and again matches the specificity of classify on small genomes while providing a big boost in performance for less memory.

rkmh requires a set of query sequences ("reads") and a set of references in the FASTA/FASTQ format. Reads may be in either FASTQ or FASTA.

To use MinHash sketch of size 1000, and a kmer size of 10:
./rkmh classify -r references.fa -f reads.fq -k 10 -s 1000

There's also now a filter for minimum kmer occurrence in a read set, compatible with the MinHash sketch. To only use kmers that occur more than 10 times in the reads:
./rkmh classify -r references.fa -f reads.fq -k 10 -s 1000 -M 100

There is also a filter that will fail reads with fewer than some number of matches to any reference. It's availble via the -N flag:
./rkmh -r references.fa -f reads.fq -k 10 -s 1000 -M 100 -N 10

A note on optimum kmer size: we've had a lot of success with k <= 15 on data fron ONT's R7 pore. I don't have any R9 flowcells around lab, but I expect we'll do a bit better on R9 given what others have been showing off.

Once you've identified which reference a set of reads most closely matches, you may want to figure out the differences between your set of reads and your reference. rkmh call uses a brute-force approach to produce a list of candidate mutations / sequencing errors present in a readset.

rkmh call -r ref.fa -f reads.fq -k 12 -t 4

We advise using only one reference during call, as it's relatively slow (~10x longer than classification, 10 seconds for 1100 reads). For example, you might first classify your reads using classify, then for the top classification in your set run rkmh call.

You might want to see the hashes generated by rkmh for debugging purposes. To do so, use the hash command.

rkmh hash -r ref.fa -f reads.fq -k 12 -s 1000

The filter command will only output reads which match any of the input references sufficiently well. This is very useful if filtering out contaminants or selecting reads which map to only a single strain.

These are extra options for the classify and hash commands. Some of them are also applicable to call. For full usage, just type ./rkmh or ./rkmh <command> at the command line to get the help message.

-t / --threads <INT> number of OpenMP threads to use (default is 1)
-M / --min-kmer-occurence <INT> minimum number of times a kmer must appear in the set of reads to be included in a read's MinHash sketch.
-N / --min-matches <INT> minimum number of matches a read must have to any reference to be considered classified.
-I / --max-samples <INT> remove kmers that appear in more than <INT> reference genomes.
-D / --min-difference <INT> flag reads that have two matches within <INT> hashes of each other as failing.
-k / --kmer <INT> the kmer size to use for hashing. Multiple kmer sizes may be passed, but they must all use the -k <INT> format (i.e. -k 12 -k 14 -k 16...)
-s / --sketch-size the number of hashes to use when comparing reads / references.
-f / --fasta a FASTA/FASTQ file to use as a read set. Can be passed multiple times (i.e. -f first.fa -f second.fa...) -r / --reference a FASTA/FASTQ file to use as a reference set. Can be passed multiple times (i.e. -r ref.fa -r ref_second.fa...)

On a set of 1000 minION reads from a known HPV strain, rkmh is ~97% accurate (correctly placing the read in the right strain of 182 input reference strains) and runs in <20 seconds. With the kmer depth and minimum match filters we're approaching 100% accuracy for about the same run time. Performance for short reads is slightly decreased because they have fewer kmers, but is still quite high. We're working on ways to improve sensitivity with further filtering and correction.

rkmh is threaded using OpenMP. Hashing can handle more than 400 long reads/second (400 * 7kb means we're running over 2,500,000 basepairs / second), with some room still left for improvement.

We've tested up to 100,000 6.5kb reads + 182 7kb references in a bit over 8GB of RAM, but we're working to scale to larger genomes and more reads. We've run an E. coli run (actually, Nick Loman's R7.3 ONT dataset against 6 E. coli references) on a desktop with 16GB of RAM. We think with a few tweaks we can do a lot better.

Please post to the github for help.