{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,30]],"date-time":"2026-10-30T12:32:41Z","timestamp":1793363561621,"version":"4.5.0"},"reference-count":46,"publisher":"SAGE Publications","issue":"1","license":[{"start":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T00:00:00Z","timestamp":1767139200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Journal of Computational Biology"],"published-print":{"date-parts":[[2026,1,1]]},"abstract":"<jats:p>\n                    The widespread adoption of\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -mers in computational biology has enabled efficient methods for utilizing genomic sequences in a variety of biological tasks. However, understanding the influence of\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -mer sizes within these methods remains a persistent challenge. Slicing sequences into a fixed size lacks grounding in biological insight, and complex bioinformatics pipelines obscure the effect of the parameter\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    due to various noisy factors. The choice of\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -mer size is typically arbitrary, with justification omitted in both the literature and method tutorials. Furthermore, the lack of theoretical understanding has caused recent multi-\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -mer approaches to face significant computational challenges. Nevertheless, most methods are built on well-defined objects related to\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -mers, such as de Bruijn graphs, Jaccard similarity, Bray-Curtis dissimilarity, and\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -mer spectra. The role of\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -mer sizes within these objects is more intuitive and can be described by numerous quantities and metrics. Therefore, exploring these objects across\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -mer sizes opens opportunities for robust analyses and new applications. However, the evolution of\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -mer objects with respect to\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -mer sizes is surprisingly elusive. We introduce a novel substring index, the Pro\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    rustean graph, that elucidates the transformation of\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -mer sets across\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -mer sizes. Our framework built upon this index rapidly computes\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -mer-based quantities for all\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -mer sizes, with computational complexity independent of the size range and dependent only on maximal repeats. For example, counting unitigs (maximal simple paths) in de Bruijn graphs for\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    = 1, \u2026, 100 is achieved in seconds using our index on a gigabase-scale dataset. We present a variety of algorithms for applications relevant to pangenomics and metagenomics. The Pro\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    rustean graph is directly derived from the affix tree and can be constructed space-efficiently from the Burrows\u2013Wheeler transform. This derivation grounded in modern substring indexes that are all theoretically based on longest common prefixes reveals that such extension-based substring representations inherently struggle to explore\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -mer objects across different sizes, which motivated our data structure. Our implementation is available at:\n                    <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"uri\" xlink:href=\"https:\/\/github.com\/KoslickiLab\/prokrustean\">https:\/\/github.com\/KoslickiLab\/prokrustean<\/jats:ext-link>\n                    .\n                  <\/jats:p>","DOI":"10.1177\/15578666251401600","type":"journal-article","created":{"date-parts":[[2025,12,26]],"date-time":"2025-12-26T14:08:37Z","timestamp":1766758117000},"page":"107-133","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":0,"title":["Elucidating Transitions of\n                    <i>k<\/i>\n                    -mer-Based Objects Across\n                    <i>k<\/i>\n                    -mer Sizes"],"prefix":"10.1177","volume":"33","author":[{"given":"Adam","family":"Park","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, Pennsylvania State University, University Park, Pennsylvania, USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Koslicki","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Pennsylvania State University, University Park, Pennsylvania, USA."},{"name":"Department of Biology, Pennsylvania State University, University Park, Pennsylvania, USA."},{"name":"Huck Institutes of the Life Sciences, Pennsylvania State University, University Park, Pennsylvania, USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"179","published-online":{"date-parts":[[2025,12,31]]},"reference":[{"key":"e_1_3_3_2_1","doi-asserted-by":"publisher","DOI":"10.1155\/2022\/8077664"},{"key":"e_1_3_3_3_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btaa760"},{"key":"e_1_3_3_4_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41587-022-01220-6"},{"key":"e_1_3_3_5_1","doi-asserted-by":"publisher","unstructured":"Belazzougui D Cunial F. Fully-functional bidirectional burrows-wheeler indexes and infinite-order de bruijn graphs. In 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik 2019; doi: 10.4230\/LIPIcs.CPM.2019.10","DOI":"10.4230\/LIPIcs.CPM.2019.10"},{"key":"e_1_3_3_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2012.07.007"},{"key":"e_1_3_3_7_1","doi-asserted-by":"publisher","DOI":"10.7717\/peerj-cs.94"},{"key":"e_1_3_3_8_1","doi-asserted-by":"crossref","unstructured":"Besta M Kanakagiri R Mustafa H et al. Communication-efficient jaccard similarity for high-performance distributed genome comparisons. In 2020 IEEE International Parallel and Distributed Processing Symposium (IPDPS). IEEE 2020 1122\u20131132; doi: 10.48550\/arXiv.1911.04200","DOI":"10.1109\/IPDPS47924.2020.00118"},{"key":"e_1_3_3_9_1","doi-asserted-by":"publisher","DOI":"10.1038\/srep28840"},{"key":"e_1_3_3_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.isci.2024.109054"},{"key":"e_1_3_3_11_1","doi-asserted-by":"publisher","unstructured":"Boucher C Bowe A Gagie T et al. Variable-order de bruijn graphs. In 2015 data compression conference. IEEE 2015 383\u2013392; doi: 10.1109\/DCC.2015.70","DOI":"10.1109\/DCC.2015.70"},{"key":"e_1_3_3_12_1","doi-asserted-by":"publisher","DOI":"10.1186\/s13059-018-1568-0"},{"key":"e_1_3_3_13_1","doi-asserted-by":"publisher","DOI":"10.1186\/s13059-021-02297-z"},{"key":"e_1_3_3_14_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0258693"},{"key":"e_1_3_3_15_1","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2022.0208"},{"key":"e_1_3_3_16_1","doi-asserted-by":"publisher","unstructured":"Cenzato D Guerrini V Lipt\u00e1k Z et al. Computing the optimal BWT of very large string collections. In In Proc. of the 33rd Data Compression Conference DCC 2023 2023. 2023 71\u201380; doi: 10.1109\/DCC55655.2023.00015","DOI":"10.1109\/DCC55655.2023.00015"},{"key":"e_1_3_3_17_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btae333"},{"key":"e_1_3_3_18_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btt310"},{"key":"e_1_3_3_19_1","doi-asserted-by":"publisher","DOI":"10.1101\/gr.277615.122"},{"key":"e_1_3_3_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2023.105088"},{"key":"e_1_3_3_21_1","doi-asserted-by":"publisher","DOI":"10.1101\/2022.09.06.506758"},{"key":"e_1_3_3_22_1","doi-asserted-by":"publisher","DOI":"10.1186\/s12859-015-0875-7"},{"key":"e_1_3_3_23_1","doi-asserted-by":"publisher","unstructured":"Gog S Beller T Moffat A et al. From theory to practice: Plug and play with succinct data structures. In 13th International Symposium on Experimental Algorithms (SEA 2014). 2014 326\u2013337; doi: 10.1007\/978-3-319-07959-2_28","DOI":"10.1007\/978-3-319-07959-2_28"},{"key":"e_1_3_3_24_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931"},{"key":"e_1_3_3_25_1","doi-asserted-by":"publisher","DOI":"10.1101\/2022.01.11.475838"},{"key":"e_1_3_3_26_1","doi-asserted-by":"publisher","DOI":"10.1093\/bib\/bbab102"},{"key":"e_1_3_3_27_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btx304"},{"key":"e_1_3_3_28_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btab749"},{"key":"e_1_3_3_29_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btac557"},{"key":"e_1_3_3_30_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btu541"},{"key":"e_1_3_3_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2018.2861380"},{"key":"e_1_3_3_32_1","doi-asserted-by":"publisher","DOI":"10.1101\/gr.213959.116"},{"key":"e_1_3_3_33_1","doi-asserted-by":"publisher","DOI":"10.1186\/s13059-016-0997-x"},{"key":"e_1_3_3_34_1","doi-asserted-by":"publisher","DOI":"10.1099\/mgen.0.000409"},{"key":"e_1_3_3_35_1","doi-asserted-by":"publisher","DOI":"10.20517\/mrr.2023.26"},{"key":"e_1_3_3_36_1","article-title":"Space-efficient computation of the lcp array from the burrows-wheeler transform","author":"Prezza N","year":"2019","unstructured":"Prezza N, , Rosone G. Space-efficient computation of the lcp array from the burrows-wheeler transform. arXiv Preprint arXiv:1901.05226, 2019; doi: 10.48550\/arXiv.1901.05226","journal-title":"arXiv Preprint arXiv:1901.05226"},{"key":"e_1_3_3_37_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpbi.102"},{"key":"e_1_3_3_38_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41467-020-14998-3"},{"key":"e_1_3_3_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s40484-019-0181-x"},{"key":"e_1_3_3_40_1","doi-asserted-by":"publisher","DOI":"10.1038\/ismej.2014.76"},{"key":"e_1_3_3_41_1","doi-asserted-by":"publisher","DOI":"10.1186\/s13059-023-02968-z"},{"key":"e_1_3_3_42_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2164-15-S10-S9"},{"key":"e_1_3_3_43_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btq217"},{"key":"e_1_3_3_44_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btab797"},{"key":"e_1_3_3_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-06220-9_15"},{"key":"e_1_3_3_46_1","doi-asserted-by":"publisher","DOI":"10.1186\/s12862-020-01723-3"},{"key":"e_1_3_3_47_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pcbi.1010821"}],"container-title":["Journal of Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/15578666251401600","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/15578666251401600","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/15578666251401600","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,30]],"date-time":"2026-10-30T11:48:28Z","timestamp":1793360908000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/15578666251401600"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,31]]},"references-count":46,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,1,1]]}},"alternative-id":["10.1177\/15578666251401600"],"URL":"https:\/\/doi.org\/10.1177\/15578666251401600","relation":{},"ISSN":["1066-5277","1557-8666"],"issn-type":[{"value":"1066-5277","type":"print"},{"value":"1557-8666","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,31]]}}}