krepp: a k-mer-based maximum pseudo-likelihood method for estimating read distances and genome-wide phylogenetic placement

Comparing each sequencing read in a sample to a reference database is a fundamental step in wide-ranging applications. Results of these comparisons can enable phylogenetic characterization. However, phylogenetic placement is currently only possible at scale for marker genes, a small fraction of the genome. We introduce krepp, an alignment-free k-mer-based method that enables placing reads from anywhere on the genome on an ultra-large reference phylogeny (e.g., 123,853 leaves). We show that krepp is scalable and computes accurate distances that approximate those using alignments, leading to accurate placements. These precise phylogenetic identifications improve our ability to compare and characterize metagenomic samples.