{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T09:04:08Z","timestamp":1778144648777,"version":"3.51.4"},"reference-count":34,"publisher":"Oxford University Press (OUP)","issue":"Supplement_1","license":[{"start":{"date-parts":[[2023,6,30]],"date-time":"2023-06-30T00:00:00Z","timestamp":1688083200000},"content-version":"vor","delay-in-days":29,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"European Union's Horizon Europe","award":["101093026"],"award-info":[{"award-number":["101093026"]}]},{"name":"French ANR AGATE","award":["ANR-21-CE45-0012"],"award-info":[{"award-number":["ANR-21-CE45-0012"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,6,30]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>Minimal perfect hashing is the problem of mapping a static set of n distinct keys into the address space {1,\u2026,n} bijectively. It is well-known that n\u2009log\u20092(e) bits are necessary to specify a minimal perfect hash function (MPHF) f, when no additional knowledge of the input keys is to be used. However, it is often the case in practice that the input keys have intrinsic relationships that we can exploit to lower the bit complexity of f. For example, consider a string and the set of all its distinct k-mers as input keys: since two consecutive k-mers share an overlap of k\u22121 symbols, it seems possible to beat the classic \u2009log\u20092(e) bits\/key barrier in this case. Moreover, we would like f to map consecutive k-mers to consecutive addresses, as to also preserve as much as possible their relationship in the codomain. This is a useful feature in practice as it guarantees a certain degree of locality of reference for f, resulting in a better evaluation time when querying consecutive k-mers.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>Motivated by these premises, we initiate the study of a new type of locality-preserving MPHF designed for k-mers extracted consecutively from a collection of strings. We design a construction whose space usage decreases for growing k and discuss experiments with a practical implementation of the method: in practice, the functions built with our method can be several times smaller and even faster to query than the most efficient MPHFs in the literature.<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btad219","type":"journal-article","created":{"date-parts":[[2023,5,24]],"date-time":"2023-05-24T21:11:48Z","timestamp":1684962708000},"page":"i534-i543","source":"Crossref","is-referenced-by-count":20,"title":["Locality-preserving minimal perfect hashing of <i>k<\/i>-mers"],"prefix":"10.1093","volume":"39","author":[{"given":"Giulio Ermanno","family":"Pibiri","sequence":"first","affiliation":[{"name":"Ca\u2019 Foscari University of Venice , Venice 30172, Italy"},{"name":"ISTI-CNR , Pisa 56124, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yoshihiro","family":"Shibuya","sequence":"additional","affiliation":[{"name":"University Gustave Eiffel , Marne-la-Vall\u00e9e 77454, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antoine","family":"Limasset","sequence":"additional","affiliation":[{"name":"University of Lille, CRIStAL CNRS, UMR 9189 , Lille F-59000, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2023,6,30]]},"reference":[{"key":"2023063008143446000_btad219-B1","doi-asserted-by":"crossref","first-page":"i169","DOI":"10.1093\/bioinformatics\/bty292","article-title":"A space and time-efficient index for the compacted colored de Bruijn graph","volume":"34","author":"Almodaresi","year":"2018","journal-title":"Bioinformatics"},{"key":"2023063008143446000_btad219-B2","first-page":"285","author":"Bingmann","year":"2019"},{"key":"2023063008143446000_btad219-B3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/s13059-021-02297-z","article-title":"Simplitigs as an efficient and scalable representation of de Bruijn graphs","volume":"22","author":"B\u0159inda","year":"2021","journal-title":"Genome Biol"},{"key":"2023063008143446000_btad219-B4","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1093\/comjnl\/bxh074","article-title":"Perfect hashing schemes for mining association rules","volume":"48","author":"Chang","year":"2005","journal-title":"Comput J"},{"key":"2023063008143446000_btad219-B5","first-page":"35","author":"Chikhi","year":"2014"},{"key":"2023063008143446000_btad219-B6","doi-asserted-by":"crossref","first-page":"i201","DOI":"10.1093\/bioinformatics\/btw279","article-title":"Compacting de Bruijn graphs from sequencing data quickly and in low memory","volume":"32","author":"Chikhi","year":"2016","journal-title":"Bioinformatics"},{"key":"2023063008143446000_btad219-B7","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1145\/321812.321820","article-title":"Efficient storage and retrieval by content and address of static files","volume":"21","author":"Elias","year":"1974","journal-title":"J ACM"},{"key":"2023063008143446000_btad219-B8","author":"Fano","year":"1971"},{"key":"2023063008143446000_btad219-B9","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1145\/125187.125200","article-title":"Order-preserving minimal perfect hash functions and information retrieval","volume":"9","author":"Fox","year":"1991","journal-title":"ACM Trans Inf Syst"},{"key":"2023063008143446000_btad219-B10","author":"Frith","year":"2022"},{"key":"2023063008143446000_btad219-B11","first-page":"841","author":"Grossi","year":"2003"},{"key":"2023063008143446000_btad219-B12","first-page":"549","author":"Jacobson","year":"1989"},{"key":"2023063008143446000_btad219-B13","doi-asserted-by":"crossref","first-page":"i111","DOI":"10.1093\/bioinformatics\/btaa435","article-title":"Weighted minimizer sampling improves long read mapping","volume":"36","author":"Jain","year":"2020","journal-title":"Bioinformatics"},{"key":"2023063008143446000_btad219-B14","doi-asserted-by":"crossref","first-page":"i177","DOI":"10.1093\/bioinformatics\/btab309","article-title":"Cuttlefish: fast, parallel and low-memory compaction of de Bruijn graphs from large-scale genome collections","volume":"37","author":"Khan","year":"2021","journal-title":"Bioinformatics"},{"key":"2023063008143446000_btad219-B15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/s13059-022-02743-6","article-title":"Scalable, ultra-fast, and low-memory construction of compacted de bruijn graphs with cuttlefish 2","volume":"23","author":"Khan","year":"2022","journal-title":"Genome Biol"},{"key":"2023063008143446000_btad219-B16","first-page":"1","author":"Limasset","year":"2017"},{"key":"2023063008143446000_btad219-B17","first-page":"2774","author":"Lu","year":"2006"},{"key":"2023063008143446000_btad219-B18","doi-asserted-by":"crossref","first-page":"2858","DOI":"10.1093\/bioinformatics\/btab217","article-title":"Blight: efficient exact associative structure for k-mers","volume":"37","author":"Marchet","year":"2021","journal-title":"Bioinformatics"},{"key":"2023063008143446000_btad219-B19","first-page":"170","author":"Mehlhorn","year":"1982"},{"key":"2023063008143446000_btad219-B20","first-page":"1","author":"Pibiri","year":"2022"},{"key":"2023063008143446000_btad219-B21","doi-asserted-by":"crossref","first-page":"i185","DOI":"10.1093\/bioinformatics\/btac245","article-title":"Sparse and skew hashing of k-mers","volume":"38","author":"Pibiri","year":"2022","journal-title":"Bioinformatics"},{"key":"2023063008143446000_btad219-B22","doi-asserted-by":"crossref","first-page":"101756","DOI":"10.1016\/j.is.2021.101756","article-title":"Rank\/select queries over mutable bitmaps","volume":"99","author":"Pibiri","year":"2021","journal-title":"Inf Syst"},{"key":"2023063008143446000_btad219-B23","first-page":"1339","author":"Pibiri","year":"2021"},{"key":"2023063008143446000_btad219-B24","article-title":"Parallel and external-memory construction of minimal perfect hash functions with PTHash","author":"Pibiri","year":"2021","journal-title":"CoRR"},{"key":"2023063008143446000_btad219-B25","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3302913","article-title":"Handling massive N-gram datasets efficiently","volume":"37","author":"Pibiri","year":"2019","journal-title":"ACM Trans Inf Syst"},{"key":"2023063008143446000_btad219-B26","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3415148","article-title":"Techniques for inverted index compression","volume":"53","author":"Pibiri","year":"2021","journal-title":"ACM Comput Surv"},{"key":"2023063008143446000_btad219-B27","first-page":"152","author":"Rahman","year":"2020"},{"key":"2023063008143446000_btad219-B28","doi-asserted-by":"crossref","first-page":"3363","DOI":"10.1093\/bioinformatics\/bth408","article-title":"Reducing storage requirements for biological sequence comparison","volume":"20","author":"Roberts","year":"2004","journal-title":"Bioinformatics"},{"key":"2023063008143446000_btad219-B29","first-page":"151","author":"Robidou","year":"2021"},{"key":"2023063008143446000_btad219-B30","first-page":"76","author":"Schleimer","year":"2003"},{"key":"2023063008143446000_btad219-B31","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1186\/s13015-022-00212-0","article-title":"Space-efficient representation of genomic k-mer count tables","volume":"17","author":"Shibuya","year":"2022","journal-title":"Algorithms Mol Biol"},{"key":"2023063008143446000_btad219-B32","first-page":"3386","author":"Strimel","year":"2020"},{"key":"2023063008143446000_btad219-B33","first-page":"154","author":"Vigna","year":"2008"},{"key":"2023063008143446000_btad219-B34","doi-asserted-by":"crossref","first-page":"i119","DOI":"10.1093\/bioinformatics\/btaa472","article-title":"Improved design and analysis of practical minimizers","volume":"36","author":"Zheng","year":"2020","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/39\/Supplement_1\/i534\/50741423\/btad219.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/39\/Supplement_1\/i534\/50741423\/btad219.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,30]],"date-time":"2023-06-30T08:15:19Z","timestamp":1688112919000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/39\/Supplement_1\/i534\/7210438"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,1]]},"references-count":34,"journal-issue":{"issue":"Supplement_1","published-print":{"date-parts":[[2023,6,30]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btad219","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2023,6,1]]},"published":{"date-parts":[[2023,6,1]]}}}