`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.