KmerAperture: Retainingk-mer synteny for alignment-free extraction of core and accessory differences between bacterial genomes

ABSTRACT By decomposing genome sequences into k -mers, it is possible to estimate genome differences without alignment. Techniques such as k- mer minimisers (MinHash), have been developed and are often accurate approximations of distances based on full k -mer sets. These and other alignment-free methods avoid the large temporal and computational expense of alignment or mapping. However, these k -mer set comparisons are not entirely accurate within-species and can be completely inaccurate within-lineage. This is due, in part, to their inability to distinguish core polymorphism from accessory differences. Here we present a new approach, KmerAperture , which uses information on the k -mer relative genomic positions to determine the type of polymorphism causing differences in k -mer presence and absence between pairs of genomes. Single SNPs are expected to result in contiguous series of relative unique k -mers of length L = k . On the other hand, series of length L > k may be caused by accessory differences of length L - k +1; when the start and end of the sequence are contiguous with homologous sequence. Alternatively, they may be caused by multiple SNPs within k bp from each other and KmerAperture can determine whether that is the case. To demonstrate use cases KmerAperture was benchmarked using datasets including a very low diversity simulated population with accessory content independent from the number of SNPs, a simulated population were SNPs are spatially dense, a moderately diverse real cluster of genomes ( Escherichia coli ST1193) with a large accessory genome and a low diversity real genome cluster ( Salmonella Typhimurium ST34). We show that KmerAperture can accurately distinguish both core and accessory sequence diversity without alignment, outperforming other k -mer based tools.