{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,8]],"date-time":"2026-07-08T04:07:33Z","timestamp":1783483653970,"version":"3.55.0"},"reference-count":34,"publisher":"Oxford University Press (OUP)","issue":"18","license":[{"start":{"date-parts":[[2021,4,3]],"date-time":"2021-04-03T00:00:00Z","timestamp":1617408000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/501100001665","name":"ANR","doi-asserted-by":"publisher","award":["ANR-18-CE45-0020"],"award-info":[{"award-number":["ANR-18-CE45-0020"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,9,29]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>A plethora of methods and applications share the fundamental need to associate information to words for high-throughput sequence analysis. Doing so for billions of k-mers is commonly a scalability problem, as exact associative indexes can be memory expensive. Recent works take advantage of overlaps between k-mers to leverage this challenge. Yet, existing data structures are either unable to associate information to k-mers or are not lightweight enough.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>We present BLight, a static and exact data structure able to associate unique identifiers to k-mers and determine their membership in a set without false positive that scales to huge k-mer sets with a low memory cost. This index combines an extremely compact representation along with very fast queries. Besides, its construction is efficient and needs no additional memory. Our implementation achieves to index the k-mers from the human genome using 8 GB of RAM (23\u2009bits per k-mer) within 10\u2009min and the k-mers from the large axolotl genome using 63 GB of memory (27\u2009bits per k-mer) within 76\u2009min. Furthermore, while being memory efficient, the index provides a very high throughput: 1.4 million queries per second on a single CPU or 16.1 million using 12 cores. Finally, we also present how BLight can practically represent metagenomic and transcriptomic sequencing data to highlight its wide applicative range.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>We wrote the BLight index as an open source C++ library under the AGPL3 license available at github.com\/Malfoy\/BLight. It is designed as a user-friendly library and comes along with code usage samples.<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btab217","type":"journal-article","created":{"date-parts":[[2021,4,2]],"date-time":"2021-04-02T11:11:18Z","timestamp":1617361878000},"page":"2858-2865","source":"Crossref","is-referenced-by-count":39,"title":["BLight: efficient exact associative structure for k-mers"],"prefix":"10.1093","volume":"37","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7235-7346","authenticated-orcid":false,"given":"Camille","family":"Marchet","sequence":"first","affiliation":[{"name":"University of Lille , CRIStAL CNRS, UMR 9189 - F-59000 Lille, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mael","family":"Kerbiriou","sequence":"additional","affiliation":[{"name":"University of Lille , CRIStAL CNRS, UMR 9189 - F-59000 Lille, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Antoine","family":"Limasset","sequence":"additional","affiliation":[{"name":"University of Lille , CRIStAL CNRS, UMR 9189 - F-59000 Lille, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2021,4,3]]},"reference":[{"key":"2023061311064223600_btab217-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":"2023061311064223600_btab217-B4","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1089\/cmb.2012.0021","article-title":"Spades: a new genome assembly algorithm and its applications to single-cell sequencing","volume":"19","author":"Bankevich","year":"2012","journal-title":"J. Comput. Biol"},{"key":"2023061311064223600_btab217-B5","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1145\/362686.362692","article-title":"Space\/time trade-offs in hash coding with allowable errors","volume":"13","author":"Bloom","year":"1970","journal-title":"Commun. ACM"},{"key":"2023061311064223600_btab217-B6","first-page":"383","author":"Boucher","year":"2015"},{"key":"2023061311064223600_btab217-B19","first-page":"1","author":"B\u0159inda","year":"2021"},{"key":"2023061311064223600_btab217-B7","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1038\/nbt.3519","article-title":"Near-optimal probabilistic RNA-seq quantification","volume":"34","author":"Bray","year":"2016","journal-title":"Nat. Biotechnol"},{"key":"2023061311064223600_btab217-B9","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1089\/cmb.2014.0160","article-title":"On the representation of de Bruijn graphs","volume":"22","author":"Chikhi","year":"2015","journal-title":"J. Comput. Biol"},{"key":"2023061311064223600_btab217-B10","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":"2023061311064223600_btab217-B11","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1186\/1748-7188-8-22","article-title":"Space-efficient and exact de bruijn graph representation based on a bloom filter","volume":"8","author":"Chikhi","year":"2013","journal-title":"Algorithms Mol. Biol"},{"key":"2023061311064223600_btab217-B12","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1093\/bioinformatics\/btq697","article-title":"Succinct data structures for assembling large genomes","volume":"27","author":"Conway","year":"2011","journal-title":"Bioinformatics"},{"key":"2023061311064223600_btab217-B13","doi-asserted-by":"crossref","first-page":"1569","DOI":"10.1093\/bioinformatics\/btv022","article-title":"Kmc 2: fast and resource-frugal k-mer counting","volume":"31","author":"Deorowicz","year":"2015","journal-title":"Bioinformatics"},{"key":"2023061311064223600_btab217-B14","doi-asserted-by":"crossref","first-page":"552","DOI":"10.1145\/1082036.1082039","article-title":"Indexing compressed text","volume":"52","author":"Ferragina","year":"2005","journal-title":"J. ACM"},{"key":"2023061311064223600_btab217-B16","author":"Guo","year":"2019"},{"key":"2023061311064223600_btab217-B15","first-page":"1","year":"2020"},{"key":"2023061311064223600_btab217-B17","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1038\/ng.1028","article-title":"De novo assembly and genotyping of variants using colored de bruijn graphs","volume":"44","author":"Iqbal","year":"2012","journal-title":"Nat. Genet"},{"key":"2023061311064223600_btab217-B18","doi-asserted-by":"crossref","first-page":"768","DOI":"10.1101\/gr.214346.116","article-title":"Abyss 2.0: resource-efficient assembly of large genomes using a bloom filter","volume":"27","author":"Jackman","year":"2017","journal-title":"Genome Res"},{"key":"2023061311064223600_btab217-B20","doi-asserted-by":"crossref","first-page":"e1001177","DOI":"10.1371\/journal.pbio.1001177","article-title":"A holistic approach to marine eco-systems biology","volume":"9","author":"Karsenti","year":"2011","journal-title":"PLoS Biol"},{"key":"2023061311064223600_btab217-B21","doi-asserted-by":"crossref","first-page":"D19","DOI":"10.1093\/nar\/gkq1019","article-title":"The sequence read archive","volume":"39","author":"Leinonen","year":"2011","journal-title":"Nucleic Acids Res"},{"key":"2023061311064223600_btab217-B22","doi-asserted-by":"crossref","first-page":"1674","DOI":"10.1093\/bioinformatics\/btv033","article-title":"Megahit: an ultra-fast single-node solution for large and complex metagenomics assembly via succinct de Bruijn graph","volume":"31","author":"Li","year":"2015","journal-title":"Bioinformatics"},{"key":"2023061311064223600_btab217-B23","doi-asserted-by":"crossref","first-page":"2103","DOI":"10.1093\/bioinformatics\/btw152","article-title":"Minimap and miniasm: fast mapping and de novo assembly for noisy long sequences","volume":"32","author":"Li","year":"2016","journal-title":"Bioinformatics"},{"key":"2023061311064223600_btab217-B33","author":"Li","year":"2015"},{"key":"2023061311064223600_btab217-B3","author":"Limasset","year":"2017"},{"key":"2023061311064223600_btab217-B24","doi-asserted-by":"crossref","first-page":"i110","DOI":"10.1093\/bioinformatics\/btx235","article-title":"Improving the performance of minimizers and winnowing schemes","volume":"33","author":"Mar\u00e7ais","year":"2017","journal-title":"Bioinformatics"},{"key":"2023061311064223600_btab217-B8","article-title":"A resource-frugal probabilistic dictionary and applications in bioinformatics","author":"Marchet","year":"2018","journal-title":"Discrete Appl. Math"},{"key":"2023061311064223600_btab217-B25","doi-asserted-by":"crossref","first-page":"i177","DOI":"10.1093\/bioinformatics\/btaa487","article-title":"REINDEER: efficient indexing of k-mer presence and abundance in sequencing datasets","volume":"36","author":"Marchet","year":"2020","journal-title":"Bioinformatics"},{"key":"2023061311064223600_btab217-B26","doi-asserted-by":"crossref","first-page":"4024","DOI":"10.1093\/bioinformatics\/btw609","article-title":"Twopaco: an efficient algorithm to build the compacted de Bruijn graph from many complete genomes","volume":"33","author":"Minkin","year":"2016","journal-title":"Bioinformatics"},{"key":"2023061311064223600_btab217-B27","doi-asserted-by":"crossref","first-page":"3181","DOI":"10.1093\/bioinformatics\/btx067","article-title":"Succinct colored de Bruijn graphs","volume":"33","author":"Muggli","year":"2017","journal-title":"Bioinformatics"},{"key":"2023061311064223600_btab217-B28","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1038\/nature25458","article-title":"The axolotl genome and the evolution of key tissue formation regulators","volume":"554","author":"Nowoshilow","year":"2018","journal-title":"Nature"},{"key":"2023061311064223600_btab217-B30","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1093\/bioinformatics\/btx636","article-title":"Squeakr: an exact and approximate k-mer counting system","volume":"34","author":"Pandey","year":"2017","journal-title":"Bioinformatics"},{"key":"2023061311064223600_btab217-B29","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/j.cels.2018.05.021","article-title":"Mantis: a fast, small, and exact large-scale sequence-search index","volume":"7","author":"Pandey","year":"2018","journal-title":"Cell Syst"},{"key":"2023061311064223600_btab217-B2","author":"Rahman","year":"2020"},{"key":"2023061311064223600_btab217-B31","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":"2023061311064223600_btab217-B32","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1038\/nbt.3442","article-title":"Fast search of thousands of short-read sequencing experiments","volume":"34","author":"Solomon","year":"2016","journal-title":"Nat. Biotechnol"},{"key":"2023061311064223600_btab217-B34","first-page":"1","article-title":"An improved assembly of the loblolly pine mega-genome using long-read single-molecule sequencing","volume":"6","author":"Zimin","year":"2017","journal-title":"Gigascience"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btab217\/38710591\/btab217.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/37\/18\/2858\/50579086\/btab217.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/37\/18\/2858\/50579086\/btab217.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,13]],"date-time":"2023-06-13T11:07:20Z","timestamp":1686654440000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/37\/18\/2858\/6209734"}},"subtitle":[],"editor":[{"given":"Alfonso","family":"Valencia","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]}],"short-title":[],"issued":{"date-parts":[[2021,4,3]]},"references-count":34,"journal-issue":{"issue":"18","published-print":{"date-parts":[[2021,9,29]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btab217","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2021,9,15]]},"published":{"date-parts":[[2021,4,3]]}}}