{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T01:11:53Z","timestamp":1775697113220,"version":"3.50.1"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,2,8]],"date-time":"2025-02-08T00:00:00Z","timestamp":1738972800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,2,8]],"date-time":"2025-02-08T00:00:00Z","timestamp":1738972800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["IndexThePlanet, 101088572"],"award-info":[{"award-number":["IndexThePlanet, 101088572"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["AGATE ANR-21-CE45-0012"],"award-info":[{"award-number":["AGATE ANR-21-CE45-0012"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    The exponential increase in publicly available sequencing data and genomic resources necessitates the development of highly efficient methods for data processing and analysis. Locality-sensitive hashing techniques have successfully transformed large datasets into smaller, more manageable sketches while maintaining comparability using metrics such as Jaccard and containment indices. However, fixed-size sketches encounter difficulties when applied to divergent datasets. Scalable sketching methods, such as , provide valuable solutions but still lack resource-efficient, tailored indexing. Our objective is to create lighter sketches with comparable results while enhancing efficiency. We introduce the concept of Fractional Hitting Sets, a generalization of Universal Hitting Sets, which cover a specified fraction of the\n                    <jats:italic>k<\/jats:italic>\n                    -mer space. In theory and practice, we demonstrate the feasibility of achieving such coverage with simple but highly efficient schemes. By encoding the covered\n                    <jats:italic>k<\/jats:italic>\n                    -mers as super-\n                    <jats:italic>k<\/jats:italic>\n                    -mers, we provide a space-efficient exact representation that also enables optimized comparisons. Our novel tool, , implements this scheme, and experimental results with real bacterial collections closely match our theoretical findings. In comparison to ,  achieves similar outcomes while utilizing an order of magnitude less space and memory and operating several times faster. This highlights the potential of our approach in addressing the challenges presented by the ever-expanding landscape of genomic data.  is an open-source software and can be accessed at\n                    <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"https:\/\/github.com\/TimRouze\/supersampler\" ext-link-type=\"uri\">https:\/\/github.com\/TimRouze\/supersampler<\/jats:ext-link>\n                    . The data required to reproduce the results presented in this manuscript is available at\n                    <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"https:\/\/github.com\/TimRouze\/supersampler\/experiments\" ext-link-type=\"uri\">https:\/\/github.com\/TimRouze\/supersampler\/experiments<\/jats:ext-link>\n                    .\n                  <\/jats:p>","DOI":"10.1186\/s13015-024-00268-0","type":"journal-article","created":{"date-parts":[[2025,2,8]],"date-time":"2025-02-08T10:41:16Z","timestamp":1739011276000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Fractional hitting sets for efficient multiset sketching"],"prefix":"10.1186","volume":"20","author":[{"given":"Timoth\u00e9","family":"Rouz\u00e9","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Igor","family":"Martayan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Camille","family":"Marchet","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antoine","family":"Limasset","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,2,8]]},"reference":[{"issue":"1","key":"268_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s13059-020-02135-8","volume":"21","author":"G Holley","year":"2020","unstructured":"Holley G, Melsted P. Bifrost: highly parallel construction and indexing of colored and compacted de bruijn graphs. Genom Biol. 2020;21(1):1\u201320.","journal-title":"Genom Biol"},{"issue":"18","key":"268_CR2","doi-asserted-by":"publisher","first-page":"2858","DOI":"10.1093\/bioinformatics\/btab217","volume":"37","author":"C Marchet","year":"2021","unstructured":"Marchet C, Kerbiriou M, Limasset A. Blight: efficient exact associative structure for k-mers. Bioinformatics. 2021;37(18):2858\u201365.","journal-title":"Bioinformatics"},{"issue":"Supplementary\u20131","key":"268_CR3","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1093\/bioinformatics\/btac245","volume":"38","author":"GE Pibiri","year":"2022","unstructured":"Pibiri GE. Sparse and skew hashing of K-mers. Bioinformatics. 2022;38(Supplementary\u20131):185\u201394.","journal-title":"Bioinformatics"},{"key":"268_CR4","doi-asserted-by":"crossref","unstructured":"Marchet C, Limasset A. Scalable sequence database search using partitioned aggregated bloom comb-trees. In: ISMB. 2023.","DOI":"10.1101\/2022.02.11.480089"},{"issue":"11","key":"268_CR5","doi-asserted-by":"publisher","first-page":"3001421","DOI":"10.1371\/journal.pbio.3001421","volume":"19","author":"GA Blackwell","year":"2021","unstructured":"Blackwell GA, Hunt M, Malone KM, Lima L, Horesh G, Alako BT, Thomson NR, Iqbal Z. Exploring bacterial diversity via a curated and searchable snapshot of archived DNA sequences. PLoS Biol. 2021;19(11):3001421.","journal-title":"PLoS Biol"},{"key":"268_CR6","unstructured":"Broder AZ. On the resemblance and containment of documents. In: Proceedings. Compression and Complexity of SEQUENCES 1997 (Cat. No. 97TB100171). IEEE. 1997;pp. 21\u201329."},{"key":"268_CR7","unstructured":"Meunier F, Gandouet O, Fusy \u00c9, Flajolet P. Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm. Discrete Mathematics & Theoretical Computer Science. 2007."},{"issue":"1","key":"268_CR8","first-page":"328","volume":"34","author":"YW Yu","year":"2020","unstructured":"Yu YW, Weber GM. Hyperminhash: Minhash in loglog space. IEEE Trans Knowl Data Eng. 2020;34(1):328\u201339.","journal-title":"IEEE Trans Knowl Data Eng"},{"issue":"1","key":"268_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s13059-016-0997-x","volume":"17","author":"BD Ondov","year":"2016","unstructured":"Ondov BD, Treangen TJ, Melsted P, Mallonee AB, Bergman NH, Koren S, Phillippy AM. Mash: fast genome and metagenome distance estimation using minhash. Genome Biol. 2016;17(1):1\u201314.","journal-title":"Genome Biol"},{"issue":"1","key":"268_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s13059-019-1875-0","volume":"20","author":"DN Baker","year":"2019","unstructured":"Baker DN, Langmead B. Dashing: fast and accurate genomic distances with hyperloglog. Genome Biol. 2019;20(1):1\u201312.","journal-title":"Genome Biol"},{"key":"268_CR11","doi-asserted-by":"crossref","unstructured":"Baker DN, Langmead B. Dashing 2: genomic sketching with multiplicities and locality-sensitive hashing. In: RECOMB. 2023.","DOI":"10.1101\/2022.10.16.512384"},{"issue":"4","key":"268_CR12","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1093\/bioinformatics\/bty651","volume":"35","author":"X Zhao","year":"2019","unstructured":"Zhao X. Bindash, software for fast genome distance estimation on a typical personal laptop. Bioinformatics. 2019;35(4):671\u20133.","journal-title":"Bioinformatics"},{"key":"268_CR13","doi-asserted-by":"crossref","unstructured":"Agret C, Cazaux B, Limasset A. Toward optimal fingerprint indexing for large scale genomics. In: 22nd International Workshop on Algorithms in Bioinformatics. 2022.","DOI":"10.1101\/2021.11.04.467355"},{"key":"268_CR14","doi-asserted-by":"publisher","first-page":"1006","DOI":"10.12688\/f1000research.19675.1","volume":"8","author":"NT Pierce","year":"2019","unstructured":"Pierce NT, Irber L, Reiter T, Brooks P, Brown CT. Large-scale sequence comparisons with sourmash. F1000Research. 2019;8:1006.","journal-title":"F1000Research"},{"key":"268_CR15","doi-asserted-by":"crossref","unstructured":"Irber LC, Brooks PT, Reiter TE, Pierce-Ward NT, Hera MR, Koslicki D, Brown CT. Lightweight compositional analysis of metagenomes with fracminhash and minimum metagenome covers. bioRxiv. 2022.","DOI":"10.1101\/2022.01.11.475838"},{"key":"268_CR16","doi-asserted-by":"crossref","unstructured":"Rahman A, Medvedev P. Representation of k-mer sets using spectrum-preserving string sets. In: International Conference on Research in Computational Molecular Biology, 2020;pp. 152\u2013168. Springer.","DOI":"10.1007\/978-3-030-45257-5_10"},{"key":"268_CR17","unstructured":"Li Y, et al. Mspkmercounter: a fast and memory efficient approach for k-mer counting. 2015;arXiv preprint arXiv:1505.06550."},{"issue":"18","key":"268_CR18","doi-asserted-by":"publisher","first-page":"3363","DOI":"10.1093\/bioinformatics\/bth408","volume":"20","author":"M Roberts","year":"2004","unstructured":"Roberts M, Hayes W, Hunt BR, Mount SM, Yorke JA. Reducing storage requirements for biological sequence comparison. Bioinformatics. 2004;20(18):3363\u20139.","journal-title":"Bioinformatics"},{"issue":"10","key":"268_CR19","doi-asserted-by":"publisher","first-page":"1005777","DOI":"10.1371\/journal.pcbi.1005777","volume":"13","author":"Y Orenstein","year":"2017","unstructured":"Orenstein Y, Pellow D, Mar\u00e7ais G, Shamir R, Kingsford C. Designing small universal k-mer hitting sets for improved analysis of high-throughput sequencing. PLoS Comput Biol. 2017;13(10):1005777.","journal-title":"PLoS Comput Biol"},{"issue":"Supplement\u20131","key":"268_CR20","doi-asserted-by":"publisher","first-page":"534","DOI":"10.1093\/bioinformatics\/btad219","volume":"39","author":"GE Pibiri","year":"2023","unstructured":"Pibiri GE, Shibuya Y, Limasset A. Locality-preserving minimal perfect hashing of k-mers. Bioinformatics. 2023;39(Supplement\u20131):534\u201343.","journal-title":"Bioinformatics"},{"key":"268_CR21","doi-asserted-by":"crossref","unstructured":"Schleimer S, Wilkerson DS, Aiken A. Winnowing: local algorithms for document fingerprinting. In: Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, 2003;pp. 76\u201385.","DOI":"10.1145\/872757.872770"},{"issue":"Supplement\u20131","key":"268_CR22","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1093\/bioinformatics\/btaa472","volume":"36","author":"H Zheng","year":"2020","unstructured":"Zheng H, Kingsford C, Mar\u00e7ais G. Improved design and analysis of practical minimizers. Bioinformatics. 2020;36(Supplement\u20131):119\u201327.","journal-title":"Bioinformatics"},{"issue":"7","key":"268_CR23","first-page":"1154","volume":"33","author":"D Pellow","year":"2023","unstructured":"Pellow D, Pu L, Ekim B, Kotlar L, Berger B, Shamir R, Orenstein Y. Efficient minimizer orders for large values of k using minimum decycling sets. Genom Res. 2023;33(7):1154\u201361.","journal-title":"Genom Res"},{"issue":"1","key":"268_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s13059-021-02297-z","volume":"22","author":"K B\u0159inda","year":"2021","unstructured":"B\u0159inda K, Baym M, Kucherov G. Simplitigs as an efficient and scalable representation of de bruijn graphs. Genome Biol. 2021;22(1):1\u201324.","journal-title":"Genome Biol"},{"key":"268_CR25","doi-asserted-by":"publisher","first-page":"94","DOI":"10.7717\/peerj-cs.94","volume":"2","author":"G Benoit","year":"2016","unstructured":"Benoit G, Peterlongo P, Mariadassou M, Drezen E, Schbath S, Lavenier D, Lemaitre C. Multiple comparative metagenomics using multiset k-mer counting. PeerJ Comput Sci. 2016;2:94.","journal-title":"PeerJ Comput Sci"},{"key":"268_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s13059-021-02303-4","volume":"22","author":"H Yi","year":"2021","unstructured":"Yi H, Lin Y, Lin C, Jin W. Kssd: sequence dimensionality reduction by k-mer substring space sampling enables real-time large-scale datasets analysis. Genome Biol. 2021;22:1\u201320.","journal-title":"Genome Biol"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-024-00268-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13015-024-00268-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-024-00268-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,8]],"date-time":"2025-02-08T10:41:26Z","timestamp":1739011286000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-024-00268-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,8]]},"references-count":26,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,12]]}},"alternative-id":["268"],"URL":"https:\/\/doi.org\/10.1186\/s13015-024-00268-0","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-3526312\/v1","asserted-by":"object"}]},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,8]]},"assertion":[{"value":"31 October 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 December 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 February 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no Competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"1"}}