{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,20]],"date-time":"2026-06-20T16:12:40Z","timestamp":1781971960153,"version":"3.54.5"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,6,21]],"date-time":"2021-06-21T00:00:00Z","timestamp":1624233600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,6,21]],"date-time":"2021-06-21T00:00:00Z","timestamp":1624233600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1453527"],"award-info":[{"award-number":["1453527"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1439057"],"award-info":[{"award-number":["1439057"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1453527"],"award-info":[{"award-number":["1453527"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1439057"],"award-info":[{"award-number":["1439057"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"publisher","award":["CBIOS training grant"],"award-info":[{"award-number":["CBIOS training grant"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]},{"name":"INCEPTION project"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"published-print":{"date-parts":[[2021,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>K-mer based methods have become prevalent in many areas of bioinformatics. In applications such as database search, they often work with large multi-terabyte-sized datasets. Storing such large datasets is a detriment to tool developers, tool users, and reproducibility efforts. General purpose compressors like gzip, or those designed for read data, are sub-optimal because they do not take into account the specific redundancy pattern in k-mer sets. In our earlier work (Rahman and Medvedev, RECOMB 2020), we presented an algorithm UST-Compress that uses a spectrum-preserving string set representation to compress a set of k-mers to disk. In this paper, we present two improved methods for disk compression of k-mer sets, called ESS-Compress and ESS-Tip-Compress. They use a more relaxed notion of string set representation to further remove redundancy from the representation of UST-Compress. We explore their behavior both theoretically and on real data. We show that they improve the compression sizes achieved by UST-Compress by up to 27 percent, across a breadth of datasets. We also derive lower bounds on how well this type of compression strategy can hope to do.<\/jats:p>","DOI":"10.1186\/s13015-021-00192-7","type":"journal-article","created":{"date-parts":[[2021,6,21]],"date-time":"2021-06-21T16:04:00Z","timestamp":1624291440000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Disk compression of k-mer sets"],"prefix":"10.1186","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9166-1220","authenticated-orcid":false,"given":"Amatur","family":"Rahman","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rayan","family":"Chikhi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paul","family":"Medvedev","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,6,21]]},"reference":[{"issue":"5","key":"192_CR1","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1089\/cmb.2012.0021","volume":"19","author":"A Bankevich","year":"2012","unstructured":"Bankevich A, Nurk S, Antipov D, Gurevich AA, Dvorkin M, Kulikov AS, Lesin VM, Nikolenko SI, Pham S, Prjibelski AD, et al. SPAdes: a new genome assembly algorithm and its applications to single-cell sequencing. J Comput Biol. 2012;19(5):455\u201377.","journal-title":"J Comput Biol."},{"issue":"3","key":"192_CR2","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1186\/gb-2014-15-3-r46","volume":"15","author":"DE Wood","year":"2014","unstructured":"Wood DE, Salzberg SL. Kraken: ultrafast metagenomic sequence classification using exact alignments. Genome Biol. 2014;15(3):46.","journal-title":"Genome Biol."},{"issue":"3","key":"192_CR3","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1093\/bioinformatics\/bty641","volume":"35","author":"C Sun","year":"2018","unstructured":"Sun C, Medvedev P. Toward fast and accurate snp genotyping from whole genome sequencing data for bedside diagnostics. Bioinformatics. 2018;35(3):415\u201320.","journal-title":"Bioinformatics"},{"key":"192_CR4","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/j.isci.2019.07.011","volume":"18","author":"L. Denti","year":"2019","unstructured":"Denti L., Previtali M., Bernardini G., Sch\u00f6nhuth A., Bonizzoni P. MALVA: genotyping by Mapping-free ALlele detection of known VAriants. iScience. 2019;18:20\u20137.","journal-title":"iScience"},{"key":"192_CR5","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1016\/j.isci.2019.07.032","volume":"18","author":"D.S. Standage","year":"2019","unstructured":"Standage D.S., Brown C.T., Hormozdiari F. Kevlar: a mapping-free framework for accurate discovery of de novo variants. iScience. 2019;18:28\u201336.","journal-title":"iScience"},{"issue":"1","key":"192_CR6","doi-asserted-by":"publisher","first-page":"132","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):132.","journal-title":"Genome Biol."},{"issue":"3","key":"192_CR7","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1038\/nbt.3442","volume":"34","author":"B Solomon","year":"2016","unstructured":"Solomon B, Kingsford C. Fast search of thousands of short-read sequencing experiments. Nat Biotechnol. 2016;34(3):300\u20132.","journal-title":"Nat Biotechnol."},{"issue":"7","key":"192_CR8","doi-asserted-by":"publisher","first-page":"755","DOI":"10.1089\/cmb.2017.0265","volume":"25","author":"B Solomon","year":"2018","unstructured":"Solomon B, Kingsford C. Improved search of large transcriptomic sequencing databases using split sequence bloom trees. J Comput Biol. 2018;25(7):755\u201365.","journal-title":"J Comput Biol."},{"key":"192_CR9","doi-asserted-by":"crossref","unstructured":"Sun C, Harris RS, Chikhi R, Medvedev P. AllSome Sequence Bloom Trees. In: 21st Annual International Conference. Research in Computational Molecular Biology. RECOMB 2017, Hong Kong, China, May 3\u20137, 2017, Proceedings. Lecture Notes in Computer Science, vol. 10229, 2017;pp. 272\u2013286.","DOI":"10.1007\/978-3-319-56970-3_17"},{"issue":"3","key":"192_CR10","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1093\/bioinformatics\/btz662","volume":"36","author":"RS Harris","year":"2020","unstructured":"Harris RS, Medvedev P. Improved representation of sequence bloom trees. Bioinformatics. 2020;36(3):721\u20137.","journal-title":"Bioinformatics"},{"issue":"2","key":"192_CR11","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1038\/s41587-018-0010-1","volume":"37","author":"P Bradley","year":"2019","unstructured":"Bradley P, den Bakker HC, Rocha EP, McVean G, Iqbal Z. Ultrafast search of all deposited bacterial and viral genomic data. Nat Biotechnol. 2019;37(2):152.","journal-title":"Nat Biotechnol."},{"key":"192_CR12","doi-asserted-by":"crossref","unstructured":"Bingmann T, Bradley P, Gauger F, Iqbal Z. COBS: a compact bit-sliced signature index. arXiv preprint arXiv:1905.09624 2019.","DOI":"10.1007\/978-3-030-32686-9_21"},{"issue":"2","key":"192_CR13","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, Almodaresi F, Bender MA, Ferdman M, Johnson R, Patro R. Mantis: a fast, small, and exact large-scale sequence-search index. Cell Syst. 2018;7(2):201\u20137.","journal-title":"Cell Syst."},{"issue":"17","key":"192_CR14","doi-asserted-by":"publisher","first-page":"766","DOI":"10.1093\/bioinformatics\/bty567","volume":"34","author":"TH Dadi","year":"2018","unstructured":"Dadi TH, Siragusa E, Piro VC, Andrusch A, Seiler E, Renard BY, Reinert K. DREAM-Yara: an exact read mapper for very large databases with short update time. Bioinformatics. 2018;34(17):766\u201372.","journal-title":"Bioinformatics"},{"key":"192_CR15","doi-asserted-by":"crossref","unstructured":"Marchet C, Iqbal Z, Gautheret D, Salson M, Chikhi R. Reindeer: efficient indexing of k-mer presence and abundance in sequencing datasets. bioRxiv 2020.","DOI":"10.1101\/2020.03.29.014159"},{"key":"192_CR16","doi-asserted-by":"crossref","unstructured":"Marchet C, Boucher C, Puglisi SJ, Medvedev P, Salson M, Chikhi R. Data structures based on k-mers for querying large collections of sequencing datasets. bioRxiv, 866756 2019.","DOI":"10.1101\/866756"},{"key":"192_CR17","unstructured":"Chikhi R, Holub J, Medvedev P. Data structures to represent sets of k-long DNA sequences. arXiv:1903.12312 [cs, q-bio] 2019."},{"issue":"4","key":"192_CR18","doi-asserted-by":"publisher","first-page":"56","DOI":"10.3390\/info7040056","volume":"7","author":"M Hosseini","year":"2016","unstructured":"Hosseini M, Pratas D, Pinho A. A survey on data compression methods for biological sequences. Information. 2016;7(4):56.","journal-title":"Information"},{"key":"192_CR19","doi-asserted-by":"crossref","unstructured":"Hernaez M, Pavlichin D, Weissman T, Ochoa I. Genomic data compression. Ann Rev Biomed Data Sci. 2019;2.","DOI":"10.1146\/annurev-biodatasci-072018-021229"},{"issue":"12","key":"192_CR20","doi-asserted-by":"publisher","first-page":"1005","DOI":"10.1038\/nmeth.4037","volume":"13","author":"I Numanagi\u0107","year":"2016","unstructured":"Numanagi\u0107 I, Bonfield JK, Hach F, Voges J, Ostermann J, Alberti C, Mattavelli M, Sahinalp SC. Comparison of high-throughput sequencing data compression tools. Nat Methods. 2016;13(12):1005.","journal-title":"Nat Methods"},{"issue":"17","key":"192_CR21","doi-asserted-by":"publisher","first-page":"2759","DOI":"10.1093\/bioinformatics\/btx304","volume":"33","author":"M Kokot","year":"2017","unstructured":"Kokot M, D\u0142ugosz M, Deorowicz S. KMC 3: counting and manipulating k-mer statistics. Bioinformatics. 2017;33(17):2759\u201361.","journal-title":"Bioinformatics"},{"issue":"5","key":"192_CR22","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1093\/bioinformatics\/btt020","volume":"29","author":"G Rizk","year":"2013","unstructured":"Rizk G, Lavenier D, Chikhi R. DSK: k-mer counting with very low memory usage. Bioinformatics. 2013;29(5):652\u20133.","journal-title":"Bioinformatics"},{"issue":"6","key":"192_CR23","doi-asserted-by":"publisher","first-page":"764","DOI":"10.1093\/bioinformatics\/btr011","volume":"27","author":"G Mar\u00e7ais","year":"2011","unstructured":"Mar\u00e7ais G, Kingsford C. A fast, lock-free approach for efficient parallel counting of occurrences of k-mers. Bioinformatics. 2011;27(6):764\u201370.","journal-title":"Bioinformatics"},{"issue":"4","key":"192_CR24","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1093\/bioinformatics\/btx636","volume":"34","author":"P Pandey","year":"2017","unstructured":"Pandey P, Bender MA, Johnson R, Patro R. Squeakr: an exact and approximate k-mer counting system. Bioinformatics. 2017;34(4):568\u201375.","journal-title":"Bioinformatics"},{"issue":"15","key":"192_CR25","doi-asserted-by":"publisher","first-page":"2556","DOI":"10.1093\/bioinformatics\/bty157","volume":"34","author":"I Turner","year":"2018","unstructured":"Turner I, Garimella KV, Iqbal Z, McVean G. Integrating long-range connectivity information into de bruijn graphs. Bioinformatics. 2018;34(15):2556\u201365.","journal-title":"Bioinformatics"},{"key":"192_CR26","doi-asserted-by":"crossref","unstructured":"Rahman A, Medvedev P. Representation of $$k$$-mer sets using spectrum-preserving string sets. In: 24th Annual International Conference. Research in Computational Molecular Biology. RECOMB 2020, Padua, Italy, May 10-13, 2020, Proceedings. Lecture Notes in Computer Science, vol. 12074, pp. 152\u2013168. Springer, 2020.","DOI":"10.1007\/978-3-030-45257-5_10"},{"key":"192_CR27","doi-asserted-by":"publisher","unstructured":"B\u0159inda K. Novel computational techniques for mapping and classifying Next-Generation Sequencing data. PhD thesis, Universit\u00e9 Paris-Est (November 2016). https:\/\/doi.org\/10.5281\/zenodo.1045317.","DOI":"10.5281\/zenodo.1045317"},{"key":"192_CR28","doi-asserted-by":"publisher","unstructured":"B\u0159inda K, Baym M, Kucherov G. Simplitigs as an efficient and scalable representation of de Bruijn graphs. bioRxiv 2020. https:\/\/doi.org\/10.1101\/2020.01.12.903443.","DOI":"10.1101\/2020.01.12.903443"},{"issue":"1","key":"192_CR29","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1093\/bioinformatics\/btt594","volume":"30","author":"AJ Pinho","year":"2013","unstructured":"Pinho AJ, Pratas D. MFCompress: a compression tool for FASTA and multi-FASTA data. Bioinformatics. 2013;30(1):117\u20138.","journal-title":"Bioinformatics"},{"key":"192_CR30","doi-asserted-by":"crossref","unstructured":"Iliopoulos CS, Kundu R, Pissis SP. Efficient pattern matching in elastic-degenerate texts. In: International Conference on Language and Automata Theory and Applications, 2017;pp. 131\u2013142. Springer.","DOI":"10.1007\/978-3-319-53733-7_9"},{"issue":"12","key":"192_CR31","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1093\/bioinformatics\/btw279","volume":"32","author":"R Chikhi","year":"2016","unstructured":"Chikhi R, Limasset A, Medvedev P. Compacting de Bruijn graphs from sequencing data quickly and in low memory. Bioinformatics. 2016;32(12):201\u20138.","journal-title":"Bioinformatics"},{"key":"192_CR32","doi-asserted-by":"crossref","unstructured":"Chikhi R, Limasset A, Jackman S, Simpson JT, Medvedev P. On the representation of de Bruijn graphs. In: Research in Computational Molecular Biology, RECOMB 2014. Lecture Notes in Computer Science, 2014; vol. 8394: pp. 35\u201355. Springer.","DOI":"10.1007\/978-3-319-05269-4_4"},{"key":"192_CR33","volume-title":"Digraphs: theory. Algorithms and applications","author":"J Bang-Jensen","year":"2008","unstructured":"Bang-Jensen J, Gutin GZ. Digraphs: theory. Algorithms and applications. Berlin: Springer; 2008."},{"key":"192_CR34","unstructured":"https:\/\/github.com\/cosmo-team\/cosmo\/tree\/VARI."},{"key":"192_CR35","doi-asserted-by":"crossref","unstructured":"Bowe A, Onodera T, Sadakane K, Shibuya T. Succinct de bruijn graphs. In: Proceedings of the 12th International Conference on Algorithms in Bioinformatics. LNCS, 2012; vol. 7534: pp. 225\u2013235. Springer.","DOI":"10.1007\/978-3-642-33122-0_18"},{"key":"192_CR36","unstructured":"https:\/\/github.com\/prophyle\/prophasm."},{"issue":"3","key":"192_CR37","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1101\/gr.131383.111","volume":"22","author":"SL Salzberg","year":"2012","unstructured":"Salzberg SL, Phillippy AM, Zimin A, Puiu D, Magoc T, Koren S, Treangen TJ, Schatz MC, Delcher AL, Roberts M, et al. GAGE: a critical evaluation of genome assemblies and assembly algorithms. Genome Res. 2012;22(3):557\u201367.","journal-title":"Genome Res."},{"key":"192_CR38","doi-asserted-by":"crossref","unstructured":"Kryukov K, Ueda MT, Nakagawa S, Imanishi T. Nucleotide Archival Format (NAF) enables efficient lossless reference-free compression of DNA sequences. bioRxiv, 501130 2018.","DOI":"10.1101\/501130"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-021-00192-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13015-021-00192-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-021-00192-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,7]],"date-time":"2021-08-07T16:03:25Z","timestamp":1628352205000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-021-00192-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,21]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["192"],"URL":"https:\/\/doi.org\/10.1186\/s13015-021-00192-7","relation":{},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6,21]]},"assertion":[{"value":"5 February 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 June 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 June 2021","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":"10"}}