{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,23]],"date-time":"2026-10-23T20:36:07Z","timestamp":1792787767736,"version":"4.5.0"},"reference-count":30,"publisher":"SAGE Publications","license":[{"start":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T00:00:00Z","timestamp":1791417600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"funder":[{"name":"Univerzita Karlova v Praze","award":["UNCE 24\/SCI\/008"],"award-info":[{"award-number":["UNCE 24\/SCI\/008"]}],"id":[{"id":"https:\/\/ror.org\/024d6js02","id-type":"ROR","asserted-by":"crossref"}]},{"name":"Minist\u00e8re de l'Europe et des Affaires \u00c9trang\u00e8res","award":["PHC BARRANDE 2025 grant no. 52374TC"],"award-info":[{"award-number":["PHC BARRANDE 2025 grant no. 52374TC"]}],"id":[{"id":"https:\/\/ror.org\/00dfd1509","id-type":"ROR","asserted-by":"crossref"}]},{"name":"French Ministry for Higher Education and Research","award":["PHC BARRANDE 2025 grant no. 52374TC"],"award-info":[{"award-number":["PHC BARRANDE 2025 grant no. 52374TC"]}]},{"name":"Agence Nationale de la Recherche","award":["ANR-24-CE45-1226"],"award-info":[{"award-number":["ANR-24-CE45-1226"]}],"id":[{"id":"https:\/\/ror.org\/00rbzpz17","id-type":"ROR","asserted-by":"crossref"}]},{"name":"Grantov\u00e1 Agentura \u010cesk\u00e9 Republiky","award":["24-10306S"],"award-info":[{"award-number":["24-10306S"]}],"id":[{"id":"https:\/\/ror.org\/01pv73b02","id-type":"ROR","asserted-by":"crossref"}]},{"name":"Czech Ministry of Education, Youth and Sports","award":["ERC-CZ LL2406"],"award-info":[{"award-number":["ERC-CZ LL2406"]}],"id":[{"id":"https:\/\/ror.org\/037n8p820","id-type":"ROR","asserted-by":"crossref"}]},{"name":"Czech Ministry of Education, Youth and Sports","award":["PHC BARRANDE 2025 grant no. 52374TC"],"award-info":[{"award-number":["PHC BARRANDE 2025 grant no. 52374TC"]}],"id":[{"id":"https:\/\/ror.org\/037n8p820","id-type":"ROR","asserted-by":"crossref"}]}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Journal of Computational Biology"],"abstract":"<jats:p>\n                    The growing interest in\n                    <jats:inline-formula>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\" overflow=\"scroll\">\n                        <mml:mi>k<\/mml:mi>\n                      <\/mml:math>\n                    <\/jats:inline-formula>\n                    -mer-based methods across bioinformatics calls for compact\n                    <jats:inline-formula>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\" overflow=\"scroll\">\n                        <mml:mi>k<\/mml:mi>\n                      <\/mml:math>\n                    <\/jats:inline-formula>\n                    -mer set representations that can be optimized for specific downstream applications. Recently, masked superstrings (MS) have provided such flexibility by moving beyond de Bruijn graph paths to general\n                    <jats:inline-formula>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\" overflow=\"scroll\">\n                        <mml:mi>k<\/mml:mi>\n                      <\/mml:math>\n                    <\/jats:inline-formula>\n                    -mer superstrings equipped with a binary mask, thereby subsuming Spectrum-Preserving String Sets and achieving compactness on arbitrary\n                    <jats:inline-formula>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\" overflow=\"scroll\">\n                        <mml:mi>k<\/mml:mi>\n                      <\/mml:math>\n                    <\/jats:inline-formula>\n                    -mer sets. However, existing methods optimize superstring length and mask properties in two separate steps, possibly missing solutions where a small increase in superstring length yields a substantial reduction in mask complexity. Here, we introduce the first method for Pareto optimization of\n                    <jats:inline-formula>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\" overflow=\"scroll\">\n                        <mml:mi>k<\/mml:mi>\n                      <\/mml:math>\n                    <\/jats:inline-formula>\n                    -mer superstrings and masks, and apply it to the problem of compressing pan-genome\n                    <jats:inline-formula>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\" overflow=\"scroll\">\n                        <mml:mi>k<\/mml:mi>\n                      <\/mml:math>\n                    <\/jats:inline-formula>\n                    -mer sets. We model the compressibility of MS using an objective that combines superstring length and the number of runs in the mask. We prove that the resulting optimization problem is NP-hard and develop a heuristic based on iterative deepening search in the Aho\u2013Corasick automaton. Using microbial pan-genome datasets, we characterize the Pareto front in the superstring-length\/mask-run space and show that the front contains points that Pareto-dominate simplitigs and matchtigs. Finally, we demonstrate that Pareto-optimized MS improve pan-genome\n                    <jats:inline-formula>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\" overflow=\"scroll\">\n                        <mml:mi>k<\/mml:mi>\n                      <\/mml:math>\n                    <\/jats:inline-formula>\n                    -mer set compressibility by 12%\u201319% when combined with neural-network compressors, achieving less than 1.2 bits per\n                    <jats:inline-formula>\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\" overflow=\"scroll\">\n                        <mml:mi>k<\/mml:mi>\n                      <\/mml:math>\n                    <\/jats:inline-formula>\n                    -mer in common scenarios.\n                  <\/jats:p>","DOI":"10.1177\/15578666261491601","type":"journal-article","created":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T12:11:50Z","timestamp":1791461510000},"update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":0,"title":["Pareto Optimization of Masked Superstrings Improves Compression of Pan-Genome\n                    <i>k<\/i>\n                    -Mer Sets"],"prefix":"10.1177","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-5990-421X","authenticated-orcid":false,"given":"J\u00e1n","family":"Plach\u00fd","sequence":"first","affiliation":[{"name":"Computer Science Institute of Charles University, Prague, Czechia."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ond\u0159ej","family":"Sladk\u00fd","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Karel","family":"B\u0159inda","sequence":"additional","affiliation":[{"name":"INRIA, IRISA, Univ. Rennes, Rennes, France."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1169-7934","authenticated-orcid":false,"given":"Pavel","family":"Vesel\u00fd","sequence":"additional","affiliation":[{"name":"Computer Science Institute of Charles University, Prague, Czechia."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"179","published-online":{"date-parts":[[2026,10,8]]},"reference":[{"key":"e_1_3_2_2_1","doi-asserted-by":"crossref","unstructured":"Alanko JN et al. Small Searchable \u03ba-Spectra via Subset Rank Queries on the Spectral Burrows-Wheeler Transform. In: SIAM Conference on Applied and Computational Discrete Algorithms (ACDA23). Society for Industrial and Applied Mathematics; 2023 pp. 225\u2013236","DOI":"10.1137\/1.9781611977714.20"},{"key":"e_1_3_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13509-5_9"},{"key":"e_1_3_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/179812.179818"},{"key":"e_1_3_2_5_1","doi-asserted-by":"publisher","DOI":"10.1038\/ncomms10063"},{"key":"e_1_3_2_6_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41587-018-0010-1"},{"key":"e_1_3_2_7_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41592-025-02625-2"},{"key":"e_1_3_2_8_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41564-019-0656-6"},{"key":"e_1_3_2_9_1","doi-asserted-by":"publisher","DOI":"10.1186\/s13059-021-02297-z"},{"key":"e_1_3_2_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2019.105862"},{"key":"e_1_3_2_11_1","doi-asserted-by":"publisher","DOI":"10.1101\/2024.07.30.605881"},{"key":"e_1_3_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321820"},{"key":"e_1_3_2_13_1","volume-title":"On the number of bits required to implement an associative memory","author":"Fano RM","year":"1971","unstructured":"Fano RM. On the number of bits required to implement an associative memory. Massachusetts Institute of Technology, Project MAC; 1971."},{"issue":"4","key":"e_1_3_2_14_1","first-page":"701","article-title":"Note on Dilworth\u2019s decomposition theorem for partially ordered sets","volume":"7","author":"Fulkerson DR","year":"1956","unstructured":"Fulkerson DR. Note on Dilworth\u2019s decomposition theorem for partially ordered sets. Proc. Am. Math. Soc 1956;7(4):701\u2013702.","journal-title":"Proc. Am. Math. Soc"},{"key":"e_1_3_2_15_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-025-09603-w"},{"key":"e_1_3_2_16_1","doi-asserted-by":"publisher","DOI":"10.1038\/nbt.2241"},{"key":"e_1_3_2_17_1","doi-asserted-by":"publisher","unstructured":"Park S Park S Cazaux B et al. A linear time algorithm for constructing hierarchical overlap graphs. In: 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021). Leibniz International Proceedings in Informatics (LIPIcs) Vol. 191. Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik; 2021 pp. 22:1\u201322:9; doi: 10.4230\/lipics.cpm.2021.22","DOI":"10.4230\/lipics.cpm.2021.22"},{"key":"e_1_3_2_18_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btac245"},{"key":"e_1_3_2_19_1","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2020.0431"},{"key":"e_1_3_2_20_1","doi-asserted-by":"publisher","DOI":"10.1186\/s13015-021-00192-7"},{"key":"e_1_3_2_21_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-15-S9-S5"},{"key":"e_1_3_2_22_1","doi-asserted-by":"publisher","DOI":"10.1186\/s13015-023-00227-1"},{"key":"e_1_3_2_23_1","doi-asserted-by":"publisher","DOI":"10.1186\/s13059-023-02968-z"},{"key":"e_1_3_2_24_1","doi-asserted-by":"publisher","DOI":"10.1093\/gigascience\/giaa119"},{"key":"e_1_3_2_25_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioadv\/vbaf290"},{"key":"e_1_3_2_26_1","doi-asserted-by":"publisher","DOI":"10.1101\/2023.02.01.526717"},{"key":"e_1_3_2_27_1","first-page":"26","volume-title":"Proceedings of the Prague Stringology Conference 2025","author":"Sladk\u00fd O","year":"2025","unstructured":"Sladk\u00fd O, Vesel\u00fd P, B\u0159inda K. Towards Efficient k-Mer Set Operations via Function-Assigned Masked Superstrings. In: Proceedings of the Prague Stringology Conference 2025. (Holub J, , \u017d\u010f\u00e1rek J, eds.) Czech Technical University in Prague; 2025, pp. 26\u201340."},{"key":"e_1_3_2_28_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pbio.1002195"},{"key":"e_1_3_2_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840391"},{"key":"e_1_3_2_30_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.14722244"},{"key":"e_1_3_2_31_1","doi-asserted-by":"publisher","DOI":"10.1186\/gb-2014-15-3-r46"}],"container-title":["Journal of Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/15578666261491601","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/15578666261491601","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/15578666261491601","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,21]],"date-time":"2026-10-21T11:50:50Z","timestamp":1792583450000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/15578666261491601"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,10,8]]},"references-count":30,"alternative-id":["10.1177\/15578666261491601"],"URL":"https:\/\/doi.org\/10.1177\/15578666261491601","relation":{},"ISSN":["1066-5277","1557-8666"],"issn-type":[{"value":"1066-5277","type":"print"},{"value":"1557-8666","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,10,8]]},"article-number":"15578666261491601"}}