{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T05:35:31Z","timestamp":1791437731567,"version":"4.3.3"},"reference-count":25,"publisher":"Oxford University Press (OUP)","issue":"5","license":[{"start":{"date-parts":[[2023,5,17]],"date-time":"2023-05-17T00:00:00Z","timestamp":1684281600000},"content-version":"vor","delay-in-days":16,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"ANR SeqDigger","award":["ANR-19-CE45-0008"],"award-info":[{"award-number":["ANR-19-CE45-0008"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,5,4]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>High throughput sequencing technologies generate massive amounts of biological sequence datasets as costs fall. One of the current algorithmic challenges for exploiting these data on a global scale consists in providing efficient query engines on these petabyte-scale datasets. Most methods indexing those datasets rely on indexing words of fixed length k, called k-mers. Many applications, such as metagenomics, require the abundance of indexed k-mers as well as their simple presence or absence, but no method scales up to petabyte-scaled datasets. This deficiency is primarily because storing abundance requires explicit storage of the k-mers in order to associate them with their counts. Using counting Approximate Membership Queries (cAMQ) data structures, such as counting Bloom filters, provides a way to index large amounts of k-mers with their abundance, but at the expense of a sensible false positive rate.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>We propose a novel algorithm, called fimpera, that enables the improvement of any cAMQ performance. Applied to counting Bloom filters, our proposed algorithm reduces the false positive rate by two orders of magnitude and it improves the precision of the reported abundances. Alternatively, fimpera allows for the reduction of the size of a counting Bloom filter by two orders of magnitude while maintaining the same precision. fimpera does not introduce any memory overhead and may even reduces the query time.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>https:\/\/github.com\/lrobidou\/fimpera.<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btad305","type":"journal-article","created":{"date-parts":[[2023,5,17]],"date-time":"2023-05-17T15:06:31Z","timestamp":1684335991000},"source":"Crossref","is-referenced-by-count":7,"title":["<tt>fimpera<\/tt>: drastic improvement of Approximate Membership Query data-structures with counts"],"prefix":"10.1093","volume":"39","author":[{"given":"Lucas","family":"Robidou","sequence":"first","affiliation":[{"name":"Univ. Rennes, Inria, CNRS, IRISA , Rennes, F-35000, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0776-6407","authenticated-orcid":false,"given":"Pierre","family":"Peterlongo","sequence":"additional","affiliation":[{"name":"Univ. Rennes, Inria, CNRS, IRISA , Rennes, F-35000, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2023,5,17]]},"reference":[{"key":"2023052519475605700_btad305-B1","author":"Alanko","year":"2022"},{"key":"2023052519475605700_btad305-B2","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","article-title":"Basic local alignment search tool","volume":"215","author":"Altschul","year":"1990","journal-title":"J Mol Biol"},{"key":"2023052519475605700_btad305-B3","first-page":"285","author":"Bingmann"},{"key":"2023052519475605700_btad305-B4","first-page":"225","author":"Bowe","year":"2012"},{"key":"2023052519475605700_btad305-B5","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1038\/s41587-018-0010-1","article-title":"Ultrafast search of all deposited bacterial and viral genomic data","volume":"37","author":"Bradley","year":"2019","journal-title":"Nat Biotechnol"},{"key":"2023052519475605700_btad305-B6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3445967","article-title":"Data structures to represent a set of k-long DNA sequences","volume":"54","author":"Chikhi","year":"2022","journal-title":"ACM Comput Surv"},{"key":"2023052519475605700_btad305-B7","doi-asserted-by":"crossref","first-page":"D106","DOI":"10.1093\/nar\/gkab1051","article-title":"The European nucleotide archive in 2021","volume":"50","author":"Cummins","year":"2022","journal-title":"Nucleic Acids Res"},{"key":"2023052519475605700_btad305-B8","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/j.tcs.2018.10.019","article-title":"A simple linear-space data structure for constant-time range minimum query","volume":"770","author":"Durocher","year":"2019","journal-title":"Theor Comput Sci"},{"key":"2023052519475605700_btad305-B9","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1109\/90.851975","article-title":"Summary cache: a scalable wide-area web cache sharing protocol","volume":"8","author":"Fan","year":"2000","journal-title":"IEEE\/ACM Trans Network"},{"key":"2023052519475605700_btad305-B10","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1093\/bioinformatics\/btz662","article-title":"Improved representation of sequence bloom trees","volume":"36","author":"Harris","year":"2020","journal-title":"Bioinformatics"},{"key":"2023052519475605700_btad305-B11","doi-asserted-by":"crossref","first-page":"2759","DOI":"10.1093\/bioinformatics\/btx304","article-title":"KMC 3: counting and manipulating k-mer statistics","volume":"33","author":"Kokot","year":"2017","journal-title":"Bioinformatics"},{"key":"2023052519475605700_btad305-B12","first-page":"25:1","author":"Limasset","year":"2017"},{"key":"2023052519475605700_btad305-B13","volume-title":"Recomb-Seq 2019-9th RECOMB Satellite Workshop on Massively Parallel Sequencing","author":"Marchet"},{"key":"2023052519475605700_btad305-B14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1101\/gr.260604.119","article-title":"Data structures based on k-mers for querying large collections of sequencing data sets","volume":"31","author":"Marchet","year":"2021","journal-title":"Genome Res"},{"key":"2023052519475605700_btad305-B15","first-page":"775","author":"Pandey","year":"2017"},{"key":"2023052519475605700_btad305-B16","first-page":"9:1","author":"Pibiri","year":"2022"},{"key":"2023052519475605700_btad305-B17","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":"2023052519475605700_btad305-B18","first-page":"1339","author":"Pibiri","year":"2021"},{"key":"2023052519475605700_btad305-B19","author":"Rahman","year":"2020"},{"key":"2023052519475605700_btad305-B20","first-page":"151","author":"Robidou","year":"2021"},{"key":"2023052519475605700_btad305-B21","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1089\/cmb.2021.0429","article-title":"Set-min sketch: a probabilistic map for power-law distributions with application to k-mer annotation","volume":"29","author":"Shibuya","year":"2022","journal-title":"J Comput Biol"},{"key":"2023052519475605700_btad305-B22","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":"2023052519475605700_btad305-B23","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":"2023052519475605700_btad305-B24","doi-asserted-by":"crossref","first-page":"428","DOI":"10.1038\/s41579-020-0364-5","article-title":"Tara oceans: towards global ocean ecosystems biology","volume":"18","author":"Sunagawa","year":"2020","journal-title":"Nat Rev Microbiol"},{"key":"2023052519475605700_btad305-B25","first-page":"68","article-title":"The cancer genome atlas (TCGA): an immeasurable source of knowledge","volume":"1A","author":"Tomczak","year":"2015","journal-title":"Contemp Oncol"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btad305\/50374113\/btad305.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/39\/5\/btad305\/50453937\/btad305.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/39\/5\/btad305\/50453937\/btad305.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,25]],"date-time":"2023-05-25T19:48:24Z","timestamp":1685044104000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/doi\/10.1093\/bioinformatics\/btad305\/7169157"}},"subtitle":[],"editor":[{"given":"Jonathan","family":"Wren","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]}],"short-title":[],"issued":{"date-parts":[[2023,5,1]]},"references-count":25,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2023,5,4]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btad305","relation":{},"ISSN":["1367-4811"],"issn-type":[{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2023,5,1]]},"published":{"date-parts":[[2023,5,1]]},"article-number":"btad305"}}