Kssd: sequence dimensionality reduction by k-mer substring space sampling enables real-time large-scale datasets analysis

Abstract

Abstract Here, we develop k -mer substring space decomposition (Kssd), a sketching technique which is significantly faster and more accurate than current sketching methods. We show that it is the only method that can be used for large-scale dataset comparisons at population resolution on simulated and real data. Using Kssd, we prioritize references for all 1,019,179 bacteria whole genome sequencing (WGS) runs from NCBI Sequence Read Archive and find misidentification or contamination in 6164 of these. Additionally, we analyze WGS and exome runs of samples from the 1000 Genomes Project.

Keywords

• Sketching method
• Distance estimation
• Sequence comparison
• K-mer
• Mislabeling detection