kWIP

The \(k\)-mer Weighted Inner Product

Overview

kWIP is a method for calculating genetic similarity between samples. Unlike similar alternatives, e.g. SNP-based distance calculation, kWIP operates directly upon next-gen sequencing reads. kWIP works by decomposing sequencing reads to short \(k\)-mers, hashing these \(k\)-mers and performing pairwise distance calculation between these sample \(k\)-mer hashes. We use khmer from the DIB lab, UC Davis to hash sequencing reads. kWIP calculates the distance between samples in a computationally efficient manner, and generates a distance matrix which may be used by downstream tools. The power of kWIP comes from the weighting applied across different hash values, which decreases the effect of erroneous, rare or over-abundant \(k\)-mers while focusing on \(k\)-mers which give the most insight into the similarity of samples.

kWIP CLI Usage

USAGE: kwip [options] sample1 sample2 ... sampleN

OPTIONS:
-t, --threads       Number of threads to utilise. [default N_CPUS]
-k, --kernel        Output file for the kernel matrix. [default None]
-d, --distance      Output file for the distance matrix. [default stdout]
-U, --unweighted    Use the unweighted inner proudct kernel. [default off]
-w, --weights       Bin weight vector file (input, or output w/ -C).
-C, --calc-weights  Calculate only the bin weight vector, not kernel matrix.
-h, --help          Print this help message.
-V, --version       Print the version string.
-v, --verbose       Increase verbosity. May or may not acutally do anything.
-q, --quiet         Execute silently but for errors.

The kwip executable is the core of kWIP; its help statement is reproduced above. This program operates on the saved Countgraphs of khmer. One can run with or without the entropy weighting, using the -U parameter to disable weighting.

An example command could be:

kwip \
    -t 4 \                        # Use 4 threads
    -k rice.kern \                # Output kernel matrix to ./rice.kern
    -d rice.dist \                # Output distance matrix to ./rice.dist
    ./hashes/rice_sample_*.ct.gz  # Path to sample hashes, with wildcard

Note that this is purely illustrative and won’t run as-is due to the in-line comments. Were it to run, it would calculate the Weighted Innner Product (WIP) kernel pairwise between all samples given as arguments, utilising four threads and saving the raw kernel matrix to rice.kern and the normalised distance matrix to rice.dist.

The Concepts Behind kWIP

The inner product between two vectors is directly related to the distance between the vectors in Euclidean space. This has been utilised several times in bioinformatics to implement measures of genetic similarity between two sequences, including the \(D2\) statistic. Traditionally, the software which implement these and similar algorithms operate on known genetic sequences, e.g. those taken from a reference genome. kWIP‘s innovation is to weight the inner product operation by a weight vector, and to derive weights in a way which minimises the noise inherent in next-gen sequencing datasets while maximising the signal of genetic distance between samples.