{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T08:58:43Z","timestamp":1764925123672,"version":"3.46.0"},"reference-count":13,"publisher":"EDP Sciences","license":[{"start":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T00:00:00Z","timestamp":1764892800000},"content-version":"vor","delay-in-days":338,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Theor. Inf. Appl."],"accepted":{"date-parts":[[2025,10,25]]},"published-print":{"date-parts":[[2025]]},"abstract":"<jats:p>\n                    Transforming an input sequence into its constituent\n                    <jats:italic>k<\/jats:italic>\n                    -mers is a fundamental operation in computational genomics. To reduce storage costs associated with\n                    <jats:italic>k<\/jats:italic>\n                    -mer datasets, we introduce and formally analyze MCTR, a novel two-stage algorithm for lossless compression of the\n                    <jats:italic>k<\/jats:italic>\n                    -mer multiset. Our core method achieves a minimal text representation (\ud835\udd4e) by computing an optimal Eulerian cover (minimum string count) of the dataset's de Bruijn graph, enabled by an efficient local Eulerization technique. The resulting strings are then further compressed losslessly using the Burrows-Wheeler Transform (BWT). Leveraging de Bruijn graph properties, MCTR is proven to achieve linear time and space complexity and guarantees complete reconstruction of the original\n                    <jats:italic>k<\/jats:italic>\n                    -mer multiset, including frequencies. Using simulated and real genomic data, we evaluated MCTR's performance (list and frequency representations) against the state-of-the-art lossy unitigging tool\n                    <jats:monospace>greedytigs<\/jats:monospace>\n                    (from\n                    <jats:monospace>matchtigs<\/jats:monospace>\n                    ). We measured core execution time and the raw compression ratio (cr = weight(\ud835\udd44)\/ weight(\ud835\udd4e), where \ud835\udd44 is the input sequence data). Benchmarks confirmed MCTR's data fidelity but revealed performance trade-offs inherent to lossless representation.\n                    <jats:monospace>GreedyTigs<\/jats:monospace>\n                    was significantly faster. Regarding raw compression,\n                    <jats:monospace>GreedyTigs<\/jats:monospace>\n                    achieved high ratios (cr \u2248 14) on noisy real data for its lossy sequence output. MCTR methods exhibited cr \u2248 1 (list) or even cr &lt; 1 (frequency, due to count overhead) on clean simulated data, indicating minimal raw text reduction or even expansion. On real data, MCTR (frequency) showed moderate raw compression (cr \u2248 1.5\u20132.7), while MCTR (list) showed none (cr \u2248 1). Importantly, the full MCTR+BWT pipeline significantly outperforms BWT alone for enhanced\n                    <jats:italic>lossless<\/jats:italic>\n                    compression. Our results establish MCTR as a valuable, theoretically grounded tool for applications demanding efficient, lossless storage and analysis of\n                    <jats:italic>k<\/jats:italic>\n                    -mer multisets, complementing lossy methods optimized for sequence summarization.\n                  <\/jats:p>","DOI":"10.1051\/ita\/2025020","type":"journal-article","created":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T08:55:27Z","timestamp":1764924927000},"page":"20","source":"Crossref","is-referenced-by-count":0,"title":["Efficient\n                    <i>k<\/i>\n                    -mer dataset compression using Eulerian covers of de Bruijn graphs and BWT"],"prefix":"10.1051","volume":"59","author":[{"given":"Herman Z. Q.","family":"Chen","sequence":"first","affiliation":[{"name":"School of Mathematical Sciences; Chongqing Key Lab of Cognitive Intelligence and Intelligent Finance, Chongqing Normal University","place":["PR China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sergey","family":"Kitaev","sequence":"first","affiliation":[{"name":"Department of Mathematics and Statistics, University of Strathclyde","place":["UK"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaoyu","family":"Lang","sequence":"first","affiliation":[{"name":"School of Mathematical Sciences, Chongqing Normal University","place":["PR China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Artem","family":"Pyatkin","sequence":"first","affiliation":[{"name":"Sobolev Institute of Mathematics, Koptyug ave, 4, Novosibirsk 630090, Russia; Novosibirsk State University","place":["Russia"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Runbin","family":"Tang","sequence":"first","affiliation":[{"name":"School of Mathematical Sciences, Chongqing Normal University","place":["PR China"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2025,12,5]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Brinda K., Baym M. and Kucherov G., Simplitigs as an efficient and scalable representation of de Bruijn graphs. Genome Biol. 22 (2021).","DOI":"10.1186\/s13059-021-02297-z"},{"key":"R2","first-page":"1198","volume":"33","author":"Cracco","year":"2023","journal-title":"Genome Res."},{"key":"R3","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1186\/s13059-023-02968-z","volume":"24","author":"Schmidt","year":"2023","journal-title":"Genome Biol."},{"key":"R4","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1186\/s13015-023-00227-1","volume":"18","author":"Schmidt","year":"2023","journal-title":"Algorithms Mol. Biol."},{"key":"R5","doi-asserted-by":"crossref","unstructured":"Rossignolo E. and Comin M., Ustar: improved compression of k-mer sets with counters using de Bruijn graphs, in International Symposium on Bioinformatics Research and Applications (ISBRA) (2023) 202-213.","DOI":"10.1007\/978-981-99-7074-2_16"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"Rahman A., Chikhi R. and Medvedev P., Disk compression of k-mer sets. Algorithms Mol. Biol. 16 (2021).","DOI":"10.1186\/s13015-021-00192-7"},{"key":"R7","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/j.endm.2007.01.004","volume":"28","author":"Panyukova","year":"2007","journal-title":"Electron. Notes Discrete Math."},{"key":"R8","doi-asserted-by":"crossref","first-page":"707","DOI":"10.1007\/s00453-011-9535-0","volume":"63","author":"Ferragina","year":"2012","journal-title":"Algorithmica"},{"key":"R9","unstructured":"da F Costa L., An introduction to multisets. arXiv preprint arXiv:2110.12902 (2021)."},{"key":"R10","doi-asserted-by":"crossref","unstructured":"Rahman Md.S., et al., Basic Graph Theory, vol. 9. Springer (2017).","DOI":"10.1007\/978-3-319-49475-3"},{"key":"R11","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1145\/3531445","volume":"65","author":"Kempa","year":"2022","journal-title":"Commun. ACM"},{"key":"R12","unstructured":"Bannai H., Karkkainen J., K\u00f6ppl D. and Piatkowski M., Constructing the bijective and the extended Burrows-Wheeler transform in linear time, in 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021), vol. 191 of Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik 7 (2021) 1-77:13."},{"key":"R13","unstructured":"Bentley J.W, Gibney D. and Thankachan S.V., On the complexity of BWT-Runs minimization via alphabet reordering, in 28th Annual European Symposium on Algorithms (ESA 2020), Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik (2020) 15:1-15:13."}],"container-title":["RAIRO - Theoretical Informatics and Applications"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ita.org\/10.1051\/ita\/2025020\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T08:55:29Z","timestamp":1764924929000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ita.org\/10.1051\/ita\/2025020"}},"subtitle":[],"editor":[{"given":"Vincent","family":"Vajnovszki","sequence":"first","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"Antonio","family":"Bernini","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2025]]},"references-count":13,"alternative-id":["ita250010"],"URL":"https:\/\/doi.org\/10.1051\/ita\/2025020","relation":{},"ISSN":["0988-3754","2804-7346"],"issn-type":[{"value":"0988-3754","type":"print"},{"value":"2804-7346","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]}}}