kWIP: The k-Mer Weighted Inner Product, a de novo Estimator of Genetic Similarity

Extracting population genetic variation from todays overwhelming quantities of genomic data demands computationally efficient methods. Ideally, genetic relatedness between individuals, or samples, is determined in an unbiased, de novo manner. Rapid and unbiased estimation of genetic relatedness from raw sequence data has the potential to overcome reference genome bias, to detect mix-ups early, and to verify that biological replicates belong to the same genetic lineage before conclusions are drawn using mislabelled, or misidentified samples.

We present the k-mer Weighted Inner Product (kWIP), an assembly-, and alignment-free estimator of genetic similarity. kWIP operates directly on sequencing reads and combines a probabilistic data structure with a novel metric, the Weighted Inner Product (WIP), to efficiently calculate pairwise similarity between sequencing runs from their k-mer counts. kWIP produces a distance matrix, which can then be further analysed and visualised. Our method does not require prior knowledge of the underlying genomes and applications include detecting sample identity and mix-up, non-obvious genomic variation, and population structure.

We validate kWIP using rigorous simulation experiments and demonstrate high sensitivity and accuracy even where there is modest divergence between genomes, and/or when sequencing coverage is low. By re-analysing several published datasets we show that our results are consistent with marker-based analyses for replicate detection, finding population structure and the stratification of microbiomes.

We provide kWIP as an efficient, open source software package, licensed under the GNU GPL, at https://github.com/kdmurray91/kwip. Our software is well documented and cross platform; tutorial-style workflows are provided for new users.