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

A bstract Motivation In 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. Results We 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. Availability https://github.com/yhhshb/fress