Set-Min sketch: a probabilistic map for power-law distributions with application to k-mer annotation

Abstract

AO_SCPLOWBSTRACTC_SCPLOWO_ST_ABSMotivationC_ST_ABSIn many bioinformatics pipelines, k-mer counting is often a required step, with existing methods focusing on optimizing time or memory usage. These methods usually produce very large count tables explicitly representing k-mers themselves. Solutions avoiding explicit representation of k-mers include Minimal Perfect Hash Functions (MPHFs) or Count-Min sketches. The former is only applicable to static maps not subject to updates, while the latter suffers from potentially very large point-query errors, making it unsuitable when counters are required to be highly accurate. ResultsWe introduce Set-Min sketch - a sketching technique for representing associative maps inspired by Count-Min sketch - and apply it to the problem of representing k-mer count tables. Set-Min is provably more accurate than both Count-Min and Max-Min - an improved variant of Count-Min for static datasets that we define here. We show that Set-Min sketch provides a very low error rate, both in terms of the probability and the size of errors, at the expense of a very moderate memory increase. On the other hand, Set-Min sketches are shown to take up to an order of magnitude less space than MPHF-based solutions, especially for large values of k. Space-efficiency of Set-Min takes advantage of the power-law distribution of k-mer counts in genomic datasets. Availabilityhttps://github.com/yhhshb/fress