{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,24]],"date-time":"2025-04-24T20:40:10Z","timestamp":1745527210572,"version":"3.40.4"},"publisher-location":"Cham","reference-count":40,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031902512","type":"print"},{"value":"9783031902529","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-90252-9_14","type":"book-chapter","created":{"date-parts":[[2025,4,24]],"date-time":"2025-04-24T20:03:48Z","timestamp":1745525028000},"page":"227-249","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Prokrustean Graph: A Substring Index for\u00a0Rapid K-Mer Size Analysis"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-4104-2960","authenticated-orcid":false,"given":"Adam","family":"Park","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0640-954X","authenticated-orcid":false,"given":"David","family":"Koslicki","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,4,25]]},"reference":[{"key":"14_CR1","doi-asserted-by":"crossref","unstructured":"AlEisa, H.N., Hamad, S., Elhadad, A.: K-mer spectrum-based error correction algorithm for next-generation sequencing data. Comput. Intell. Neurosci. 2022 (2022)","DOI":"10.1155\/2022\/8077664"},{"issue":"7","key":"14_CR2","doi-asserted-by":"publisher","first-page":"905","DOI":"10.1093\/bioinformatics\/btaa760","volume":"37","author":"M Balvert","year":"2021","unstructured":"Balvert, M., Luo, X., Hauptfeld, E., Sch\u00f6nhuth, A., Dutilh, B.E.: Ogre: overlap graph-based metagenomic read clustering. Bioinformatics 37(7), 905\u2013912 (2021)","journal-title":"Bioinformatics"},{"issue":"7","key":"14_CR3","doi-asserted-by":"publisher","first-page":"1075","DOI":"10.1038\/s41587-022-01220-6","volume":"40","author":"A Bankevich","year":"2022","unstructured":"Bankevich, A., Bzikadze, A.V., Kolmogorov, M., Antipov, D., Pevzner, P.A.: Multiplex de bruijn graphs enable genome assembly from long, high-fidelity reads. Nat. Biotechnol. 40(7), 1075\u20131081 (2022)","journal-title":"Nat. Biotechnol."},{"key":"14_CR4","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"},{"key":"14_CR5","unstructured":"Benoit, G.: Simka: fast kmer-based method for estimating the similarity between numerous metagenomic datasets. In: RCAM, 2015"},{"key":"14_CR6","doi-asserted-by":"crossref","unstructured":"Besta, M., et al.: Communication-efficient jaccard similarity for high-performance distributed genome comparisons. In: 2020 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 1122\u20131132. IEEE, 2020","DOI":"10.1109\/IPDPS47924.2020.00118"},{"issue":"1","key":"14_CR7","doi-asserted-by":"publisher","first-page":"28840","DOI":"10.1038\/srep28840","volume":"6","author":"V Bonnici","year":"2016","unstructured":"Bonnici, V., Manca, V.: Informational laws of genome structures. Sci. Rep. 6(1), 28840 (2016)","journal-title":"Sci. Rep."},{"key":"14_CR8","doi-asserted-by":"crossref","unstructured":"Bonnie, J.K., Ahmed, O., Langmead, B.: Dandd: efficient measurement of sequence growth and similarity. bioRxiv, pp. 2023\u201302, 2023","DOI":"10.1101\/2023.02.02.526837"},{"key":"14_CR9","doi-asserted-by":"crossref","unstructured":"Boucher, C., Bowe, A., Gagie, T., Puglisi, S.J., Sadakane, K.: Variable-order de bruijn graphs. In: 2015 Data Compression Conference, pp. 383\u2013392. IEEE, 2015","DOI":"10.1109\/DCC.2015.70"},{"key":"14_CR10","doi-asserted-by":"crossref","unstructured":"Bowe, A., Onodera, T., Sadakane, K., Shibuya, T.: Succinct de bruijn graphs. In: International Workshop on Algorithms in Bioinformatics, pp. 225\u2013235. Springer, 2012","DOI":"10.1007\/978-3-642-33122-0_18"},{"key":"14_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s13059-018-1568-0","volume":"19","author":"FP Breitwieser","year":"2018","unstructured":"Breitwieser, F.P., Baker, D.N., Salzberg, S.L.: Krakenuniq: confident and fast metagenomics classification using unique k-mer counts. Genome Biol. 19, 1\u201310 (2018)","journal-title":"Genome Biol."},{"key":"14_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s13059-021-02297-z","volume":"22","author":"K B\u0159inda","year":"2021","unstructured":"B\u0159inda, K., Baym, M., Kucherov, G.: Simplitigs as an efficient and scalable representation of de bruijn graphs. Genome Biol. 22, 1\u201324 (2021)","journal-title":"Genome Biol."},{"issue":"10","key":"14_CR13","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0258693","volume":"16","author":"Y Bussi","year":"2021","unstructured":"Bussi, Y., Kapon, R., Reich, Z.: Large-scale k-mer-based analysis of the informational properties of genomes, comparative genomics and taxonomy. PLoS ONE 16(10), e0258693 (2021)","journal-title":"PLoS ONE"},{"issue":"6","key":"14_CR14","doi-asserted-by":"publisher","first-page":"633","DOI":"10.1089\/cmb.2022.0208","volume":"30","author":"M Cavattoni","year":"2023","unstructured":"Cavattoni, M., Comin, M.: Classgraph: improving metagenomic read classification with overlap graphs. J. Comput. Biol. 30(6), 633\u2013647 (2023)","journal-title":"J. Comput. Biol."},{"issue":"1","key":"14_CR15","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1093\/bioinformatics\/btt310","volume":"30","author":"R Chikhi","year":"2014","unstructured":"Chikhi, R., Medvedev, P.: Informed and automated k-mer size selection for genome assembly. Bioinformatics 30(1), 31\u201337 (2014)","journal-title":"Bioinformatics"},{"key":"14_CR16","doi-asserted-by":"crossref","unstructured":"Cracco, A., Tomescu, A.I.: Extremely fast construction and querying of compacted and colored de bruijn graphs with ggcat. Genome Res. pages gr\u2013277615 (2023)","DOI":"10.1101\/gr.277615.122"},{"key":"14_CR17","doi-asserted-by":"crossref","unstructured":"D\u2019\u0131az-Dom\u2019\u0131nguez, D., Onodera, T., Puglisi, S.J., Salmela, L.: Genome assembly with variable order de bruijn graphs. bioRxiv, pp. 2022\u201309, 2022","DOI":"10.1101\/2022.09.06.506758"},{"key":"14_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s12859-015-0875-7","volume":"17","author":"VB Dubinkina","year":"2016","unstructured":"Dubinkina, V.B., Ischenko, D.S., Ulyantsev, V.I., Tyakht, A.V., Alexeev, D.G.: Assessment of k-mer spectrum applicability for metagenomic dissimilarity analysis. BMC Bioinformatics 17, 1\u201311 (2016)","journal-title":"BMC Bioinformatics"},{"issue":"4","key":"14_CR19","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1145\/270563.571472","volume":"28","author":"D Gusfield","year":"1997","unstructured":"Gusfield, D.: Algorithms on stings, trees, and sequences: computer science and computational biology. ACM SIGACT News 28(4), 41\u201360 (1997)","journal-title":"ACM SIGACT News"},{"key":"14_CR20","doi-asserted-by":"crossref","unstructured":"Irber, L., et al.: Lightweight compositional analysis of metagenomes with fracminhash and minimum metagenome covers. bioRxiv, pp. 2022\u201301, 2022","DOI":"10.1101\/2022.01.11.475838"},{"key":"14_CR21","doi-asserted-by":"crossref","unstructured":"Islam, R., et al.: Choice of assemblers has a critical impact on de novo assembly of sars-cov-2 genome and characterizing variants. Briefings Bioinform. 22(5), bbab102 (2021)","DOI":"10.1093\/bib\/bbab102"},{"issue":"17","key":"14_CR22","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 33(17), 2759\u20132761 (2017)","journal-title":"Bioinformatics"},{"issue":"3","key":"14_CR23","doi-asserted-by":"publisher","first-page":"604","DOI":"10.1093\/bioinformatics\/btab749","volume":"38","author":"T Krannich","year":"2022","unstructured":"Krannich, T., White, W., Niehus, S., Holley, G., Halld\u00f3rsson, B.V., Kehr, B.: Population-scale detection of non-reference sequence variants using colored de bruijn graphs. Bioinformatics 38(3), 604\u2013611 (2022)","journal-title":"Bioinformatics"},{"issue":"1","key":"14_CR24","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1109\/TCBB.2018.2861380","volume":"17","author":"X Liao","year":"2018","unstructured":"Liao, X., et al.: Improving de novo assembly based on read classification. IEEE\/ACM Trans. Comput. Biol. Bioinf. 17(1), 177\u2013188 (2018)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinf."},{"key":"14_CR25","unstructured":"Mallawaarachchi, V.: Metagenomics Binning Using Assembly Graphs. PhD thesis, The Australian National University (Australia), 2022"},{"issue":"5","key":"14_CR26","doi-asserted-by":"publisher","first-page":"824","DOI":"10.1101\/gr.213959.116","volume":"27","author":"S Nurk","year":"2017","unstructured":"Nurk, S., Meleshko, D., Korobeynikov, A., Pevzner, P.A.: metaspades: a new versatile metagenomic assembler. Genome Res. 27(5), 824\u2013834 (2017)","journal-title":"Genome Res."},{"key":"14_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s13059-016-0997-x","volume":"17","author":"BD Ondov","year":"2016","unstructured":"Ondov, B.D., et al.: Mash: fast genome and metagenome distance estimation using minhash. Genome Biol. 17, 1\u201314 (2016)","journal-title":"Genome Biol."},{"issue":"8","key":"14_CR28","doi-asserted-by":"publisher","DOI":"10.1099\/mgen.0.000409","volume":"6","author":"AE P\u00e9rez-Cobas","year":"2020","unstructured":"P\u00e9rez-Cobas, A.E., Gomez-Valero, L., Buchrieser, C.: Metagenomic approaches in microbial ecology: an update on whole-genome and marker gene sequencing analyses. Microbial Genomics 6(8), e000409 (2020)","journal-title":"Microbial Genomics"},{"key":"14_CR29","doi-asserted-by":"crossref","unstructured":"Ponsero, A.J., Miller, M., Hurwitz, B.L.: Comparison of k-mer-based de novo comparative metagenomic tools and approaches. Microbiome Res. Rep. 2(4) (2023)","DOI":"10.20517\/mrr.2023.26"},{"issue":"1","key":"14_CR30","doi-asserted-by":"publisher","DOI":"10.1002\/cpbi.102","volume":"70","author":"A Prjibelski","year":"2020","unstructured":"Prjibelski, A., Antipov, D., Meleshko, D., Lapidus, A., Korobeynikov, A.: Using spades de novo assembler. Curr. Protoc. Bioinform. 70(1), e102 (2020)","journal-title":"Curr. Protoc. Bioinform."},{"key":"14_CR31","doi-asserted-by":"crossref","unstructured":"Ranallo-Benavidez, T.R., Jaron, K.S., Schatz, M.C.: Genomescope 2.0 and smudgeplot for reference-free profiling of polyploid genomes. Nat. Comm. 11(1), 1432 (2020)","DOI":"10.1038\/s41467-020-14998-3"},{"key":"14_CR32","doi-asserted-by":"crossref","unstructured":"Rizzi, R., et al.: Overlap graphs and de bruijn graphs: data structures for de novo genome assembly in the big data era. Quant. Biol. 7, 278\u2013292 (2019)","DOI":"10.1007\/s40484-019-0181-x"},{"issue":"11","key":"14_CR33","doi-asserted-by":"publisher","first-page":"2349","DOI":"10.1038\/ismej.2014.76","volume":"8","author":"LM Rodriguez-r","year":"2014","unstructured":"Rodriguez-r, L.M., Konstantinidis, K.T.: Estimating coverage in metagenomic data sets and why it matters. ISME J. 8(11), 2349\u20132351 (2014)","journal-title":"ISME J."},{"issue":"1","key":"14_CR34","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1186\/s13059-023-02968-z","volume":"24","author":"S Schmidt","year":"2023","unstructured":"Schmidt, S., Khan, S., Alanko, J.N., Pibiri, G.E., Tomescu, A.I.: Matchtigs: minimum plain text representation of k-mer sets. Genome Biol. 24(1), 136 (2023)","journal-title":"Genome Biol."},{"issue":"10","key":"14_CR35","first-page":"1","volume":"15","author":"B Shariat","year":"2014","unstructured":"Shariat, B., Movahedi, N.S., Chitsaz, H., Boucher, C.: Hyda-vista: towards optimal guided selection of k-mer size for sequence assembly. BMC Genomics 15(10), 1\u20138 (2014)","journal-title":"BMC Genomics"},{"issue":"12","key":"14_CR36","doi-asserted-by":"publisher","first-page":"i367","DOI":"10.1093\/bioinformatics\/btq217","volume":"26","author":"JT Simpson","year":"2010","unstructured":"Simpson, J.T., Durbin, R.: Efficient construction of an assembly string graph using the fm-index. Bioinformatics 26(12), i367\u2013i373 (2010)","journal-title":"Bioinformatics"},{"issue":"4","key":"14_CR37","doi-asserted-by":"publisher","first-page":"933","DOI":"10.1093\/bioinformatics\/btab797","volume":"38","author":"D Tang","year":"2022","unstructured":"Tang, D., et al.: KCOSS: an ultra-fast k-mer counter for assembled genome analysis. Bioinformatics 38(4), 933\u2013940 (2022)","journal-title":"Bioinformatics"},{"key":"14_CR38","doi-asserted-by":"crossref","unstructured":"Wickramarachchi, A., Lin, Y.: Metagenomics binning of long reads using read-overlap graphs. In: RECOMB International Workshop on Comparative Genomics, pp. 260\u2013278. Springer, 2022","DOI":"10.1007\/978-3-031-06220-9_15"},{"key":"14_CR39","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s12862-020-01723-3","volume":"20","author":"Z Yang","year":"2020","unstructured":"Yang, Z., et al.: Intrinsic laws of k-mer spectra of genome sequences and evolution mechanism of genomes. BMC Evol. Biol. 20, 1\u201315 (2020)","journal-title":"BMC Evol. Biol."},{"issue":"1","key":"14_CR40","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pcbi.1010821","volume":"19","author":"H Zhai","year":"2023","unstructured":"Zhai, H., Fukuyama, J.: A convenient correspondence between k-mer-based metagenomic distances and phylogenetically-informed $$\\beta $$-diversity measures. PLoS Comput. Biol. 19(1), e1010821 (2023)","journal-title":"PLoS Comput. Biol."}],"container-title":["Lecture Notes in Computer Science","Research in Computational Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-90252-9_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,24]],"date-time":"2025-04-24T20:03:56Z","timestamp":1745525036000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-90252-9_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031902512","9783031902529"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-90252-9_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"25 April 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"RECOMB","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Research in Computational Molecular Biology","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Seoul","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Korea (Republic of)","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 April 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 April 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"recomb2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/recomb.org\/recomb2025\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}