{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T04:10:59Z","timestamp":1772165459547,"version":"3.50.1"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,2,16]],"date-time":"2021-02-16T00:00:00Z","timestamp":1613433600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"},{"start":{"date-parts":[[2021,2,16]],"date-time":"2021-02-16T00:00:00Z","timestamp":1613433600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2021,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Background<\/jats:title>\n                    <jats:p>Specialized data structures are required for online algorithms to efficiently handle large sequencing datasets. The counting quotient filter (CQF), a compact hashtable, can efficiently store k-mers with a skewed distribution.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Result<\/jats:title>\n                    <jats:p>Here, we present the mixed-counters quotient filter (MQF) as a new variant of the CQF with novel counting and labeling systems. The new counting system adapts to a wider range of data distributions for increased space efficiency and is faster than the CQF for insertions and queries in most of the tested scenarios. A buffered version of the MQF can offload storage to disk, trading speed of insertions and queries for a significant memory reduction. The labeling system provides a flexible framework for assigning labels to member items while maintaining good data locality and a concise memory representation. These labels serve as a minimal perfect hash function but are\u2009~\u2009tenfold faster than BBhash, with no need to re-analyze the original data for further insertions or deletions.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Conclusions<\/jats:title>\n                    <jats:p>The MQF is a flexible and efficient data structure that extends our ability to work with high throughput sequencing data.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1186\/s12859-021-03996-x","type":"journal-article","created":{"date-parts":[[2021,2,17]],"date-time":"2021-02-17T12:17:14Z","timestamp":1613564234000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["MQF and buffered MQF: quotient filters for efficient storage of k-mers with their counts and metadata"],"prefix":"10.1186","volume":"22","author":[{"given":"Moustafa","family":"Shokrof","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"C. Titus","family":"Brown","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4747-4241","authenticated-orcid":false,"given":"Tamer A.","family":"Mansour","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,2,16]]},"reference":[{"key":"3996_CR1","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1186\/s40537-019-0210-7","volume":"6","author":"T Kolajo","year":"2019","unstructured":"Kolajo T, Daramola O, Adebiyi A. Big data stream analysis: a systematic literature review. J Big Data. 2019;6:47.","journal-title":"J Big Data"},{"key":"3996_CR2","unstructured":"Matias Y, Vitter JS, Young NE. Approximate data structures with applications. In: Proceedings of the fifth annual ACM-SIAM symposium on discrete algorithms. Arlington: Society for Industrial and Applied Mathematics; 1994. p. 187\u2013194."},{"key":"3996_CR3","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1145\/362686.362692","volume":"13","author":"BH Bloom","year":"1970","unstructured":"Bloom BH. Space\/time trade-offs in hash coding with allowable errors. Commun ACM. 1970;13:422\u20136.","journal-title":"Commun ACM"},{"key":"3996_CR4","doi-asserted-by":"crossref","unstructured":"Pandey P, Bender MA, Johnson R, Patro R. A general-purpose counting filter: making every bit count. In: Proceedings of the 2017 ACM international conference on management of data. Chicago: Association for Computing Machinery; 2017. p. 775\u201387.","DOI":"10.1145\/3035918.3035963"},{"key":"3996_CR5","first-page":"giy125","volume":"7","author":"SC Manekar","year":"2018","unstructured":"Manekar SC, Sathe SR. A benchmark study of k-mer counting methods for high-throughput sequencing. Gigascience. 2018;7:giy125.","journal-title":"Gigascience"},{"key":"3996_CR6","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1186\/s13059-018-1535-9","volume":"19","author":"Y Yu","year":"2018","unstructured":"Yu Y, et al. SeqOthello: querying RNA-seq experiments at scale. Genome Biol. 2018;19:167.","journal-title":"Genome Biol"},{"key":"3996_CR7","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1016\/j.jalgor.2003.12.001","volume":"55","author":"G Cormode","year":"2005","unstructured":"Cormode G, Muthukrishnan S. An improved data stream summary: the count-min sketch and its applications. J Algorithms. 2005;55:58\u201375.","journal-title":"J Algorithms"},{"key":"3996_CR8","doi-asserted-by":"publisher","first-page":"3181","DOI":"10.1093\/bioinformatics\/btx067","volume":"33","author":"MD Muggli","year":"2017","unstructured":"Muggli MD, et al. Succinct colored de Bruijn graphs. Bioinformatics. 2017;33:3181\u20137.","journal-title":"Bioinformatics"},{"key":"3996_CR9","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1038\/nbt.3519","volume":"34","author":"NL Bray","year":"2016","unstructured":"Bray NL, Pimentel H, Melsted P, Pachter L. Near-optimal probabilistic RNA-seq quantification. Nat Biotechnol. 2016;34:525\u20137.","journal-title":"Nat Biotechnol"},{"key":"3996_CR10","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1038\/ng.1028","volume":"44","author":"Z Iqbal","year":"2012","unstructured":"Iqbal Z, Caccamo M, Turner I, Flicek P, McVean G. De novo assembly and genotyping of variants using colored de Bruijn graphs. Nat Genet. 2012;44:226\u201332.","journal-title":"Nat Genet"},{"key":"3996_CR11","volume-title":"Introduction to algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen TH, Leiserson CE, Rivest RL, Stein CS. Introduction to algorithms. Cambridge: MIT Press; 2009."},{"key":"3996_CR12","doi-asserted-by":"publisher","first-page":"764","DOI":"10.1093\/bioinformatics\/btr011","volume":"27","author":"G Marcais","year":"2011","unstructured":"Marcais G, Kingsford C. A fast, lock-free approach for efficient parallel counting of occurrences of k-mers. Bioinformatics. 2011;27:764\u201370.","journal-title":"Bioinformatics"},{"key":"3996_CR13","doi-asserted-by":"publisher","unstructured":"Wang J, Chen S, Dong L, Wang G. CHTKC: a robust and efficient k-mer counting algorithm based on a lock-free chaining hash table. Brief Bioinform. 2020. https:\/\/doi.org\/10.1093\/bib\/bbaa063.","DOI":"10.1093\/bib\/bbaa063"},{"key":"3996_CR14","doi-asserted-by":"publisher","first-page":"682","DOI":"10.1007\/978-3-642-04128-0_61","volume-title":"Algorithms\u2014ESA 2009","author":"D Belazzougui","year":"2009","unstructured":"Belazzougui D, Botelho FC, Dietzfelbinger M. Hash, displace, and compress. In: Fiat A, Sanders P, editors. Algorithms\u2014ESA 2009. Berlin: Springer; 2009. p. 682\u201393."},{"key":"3996_CR15","unstructured":"Limasset A, Rizk G, Chikhi R, Peterlongo P. Fast and scalable minimal perfect hashing for massive key sets. In: 16th International Symposium on Experimental Algorithms. Vol. 11. London, United Kingdom; 2017; p. 1\u201311. \u00a0"},{"key":"3996_CR16","doi-asserted-by":"publisher","first-page":"900","DOI":"10.12688\/f1000research.6924.1","volume":"4","author":"MR Crusoe","year":"2015","unstructured":"Crusoe MR, et al. The khmer software package: enabling efficient nucleotide sequence analysis. F1000 Res. 2015;4:900.","journal-title":"F1000 Res"},{"key":"3996_CR17","doi-asserted-by":"publisher","first-page":"P31","DOI":"10.1186\/gb-2011-12-s1-p31","volume":"12","author":"JM Zook","year":"2011","unstructured":"Zook JM, Salit M. Genomes in a bottle: creating standard reference materials for genomic variation\u2014why, what and how? Genome Biol. 2011;12:P31\u2013P31.","journal-title":"Genome Biol"},{"key":"3996_CR18","doi-asserted-by":"crossref","unstructured":"Flajolet P, Fusy R, Gandouet O, Meunier F. HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm. In: Discrete mathematics & theoretical computer science; 2007. p. 137\u201356.","DOI":"10.46298\/dmtcs.3545"},{"key":"3996_CR19","doi-asserted-by":"crossref","first-page":"1324","DOI":"10.1093\/bioinformatics\/btw832","volume":"33","author":"H Mohamadi","year":"2017","unstructured":"Mohamadi H, Khan H, Birol I. ntCard: a streaming algorithm for cardinality estimation in genomics data. Bioinformatics. 2017;33:1324\u201330.","journal-title":"Bioinformatics"},{"key":"3996_CR20","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/j.cels.2018.05.021","volume":"7","author":"P Pandey","year":"2018","unstructured":"Pandey P, et al. Mantis: a fast, small, and exact large-scale sequence-search index. Cell Syst. 2018;7:201-207 e4.","journal-title":"Cell Syst"},{"key":"3996_CR21","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1016\/j.ymeth.2018.03.009","volume":"143","author":"T Schlick","year":"2018","unstructured":"Schlick T. Adventures with RNA graphs. Methods. 2018;143:16\u201333.","journal-title":"Methods"},{"key":"3996_CR22","first-page":"23","volume":"19","author":"JI Sohn","year":"2018","unstructured":"Sohn JI, Nam JW. The present and future of de novo whole-genome assembly. Brief Bioinform. 2018;19:23\u201340.","journal-title":"Brief Bioinform"},{"key":"3996_CR23","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1561\/0400000002","volume":"1","author":"S Muthukrishnan","year":"2003","unstructured":"Muthukrishnan S. Data streams: algorithms and applications. Found Trends Theor Comput Sci. 2003;1:117\u2013236.","journal-title":"Found Trends Theor Comput Sci"},{"key":"3996_CR24","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1002\/spe.844","volume":"38","author":"R Dementiev","year":"2008","unstructured":"Dementiev R, Kettner L, Sanders P. STXXL: standard template library for XXL data sets. Softw Prac Exp. 2008;38:589\u2013637.","journal-title":"Softw Prac Exp"},{"key":"3996_CR25","doi-asserted-by":"crossref","unstructured":"Powers D. Applications and explanations of Zipf's Law. In: CoNLL; 1998.","DOI":"10.3115\/1603899.1603924"},{"key":"3996_CR26","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1093\/bioinformatics\/btr708","volume":"28","author":"W Huang","year":"2012","unstructured":"Huang W, Li L, Myers JR, Marth GT. ART: a next-generation sequencing read simulator. Bioinformatics. 2012;28:593\u20134.","journal-title":"Bioinformatics"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-021-03996-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/s12859-021-03996-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-021-03996-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,21]],"date-time":"2023-10-21T06:10:15Z","timestamp":1697868615000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/s12859-021-03996-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,16]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["3996"],"URL":"https:\/\/doi.org\/10.1186\/s12859-021-03996-x","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/2020.08.23.263061","asserted-by":"object"}]},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,2,16]]},"assertion":[{"value":"15 September 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 February 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 February 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Not applicable.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors declare that they have no competing interests.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"71"}}