{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:35:20Z","timestamp":1759638920765,"version":"3.37.3"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,5,31]],"date-time":"2016-05-31T00:00:00Z","timestamp":1464652800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003407","name":"Ministero dell\u2019Istruzione, dell\u2019Universit\u00e0e della Ricerca","doi-asserted-by":"publisher","award":["2010LYA9RH"],"award-info":[{"award-number":["2010LYA9RH"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002954","name":"Universit\u00e0 degli Studi di Milano-Bicocca","doi-asserted-by":"crossref","award":["2013-ATE-0281","2014-ATE-0382"],"award-info":[{"award-number":["2013-ATE-0281","2014-ATE-0382"]}],"id":[{"id":"10.13039\/501100002954","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,6]]},"DOI":"10.1007\/s00453-016-0165-4","type":"journal-article","created":{"date-parts":[[2016,5,31]],"date-time":"2016-05-31T15:17:44Z","timestamp":1464707864000},"page":"394-424","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["An External-Memory Algorithm for String Graph Construction"],"prefix":"10.1007","volume":"78","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7289-4988","authenticated-orcid":false,"given":"Paola","family":"Bonizzoni","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4032-8177","authenticated-orcid":false,"given":"Gianluca","family":"Della Vedova","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8479-7592","authenticated-orcid":false,"given":"Yuri","family":"Pirola","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3040-9539","authenticated-orcid":false,"given":"Marco","family":"Previtali","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9730-7516","authenticated-orcid":false,"given":"Raffaella","family":"Rizzi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,5,31]]},"reference":[{"issue":"1","key":"165_CR1","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/S1570-8667(03)00065-0","volume":"2","author":"M Abouelhoda","year":"2004","unstructured":"Abouelhoda, M., Kurtz, S., Ohlebusch, E.: Replacing suffix trees with enhanced suffix arrays. J. Discrete Algorithms 2(1), 53\u201386 (2004)","journal-title":"J. Discrete Algorithms"},{"issue":"9","key":"165_CR2","doi-asserted-by":"publisher","first-page":"1116","DOI":"10.1145\/48529.48535","volume":"31","author":"A Aggarwal","year":"1988","unstructured":"Aggarwal, A., Vitter, J.: The Input\/Output complexity of sorting and related problems. Commun. ACM 31(9), 1116\u20131127 (1988)","journal-title":"Commun. ACM"},{"key":"165_CR3","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1007\/BF01188581","volume":"13","author":"F Alizadeh","year":"1995","unstructured":"Alizadeh, F., Karp, R., Newberg, L., Weisser, D.: Physical mapping of chromosomes: a combinatorial problem in molecular biology. Algorithmica 13, 52\u201376 (1995)","journal-title":"Algorithmica"},{"key":"165_CR4","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1089\/cmb.1995.2.159","volume":"2","author":"F Alizadeh","year":"1995","unstructured":"Alizadeh, F., Karp, R., Weisser, D., Zweig, G.: Physical mapping of chromosomes using unique probes. J. Comput. Biol. 2, 159\u2013184 (1995)","journal-title":"J. Comput. Biol."},{"issue":"5","key":"165_CR5","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., et al.: SPAdes: a new genome assembly algorithm and its applications to single-cell sequencing. J. Comput. Biol. 19(5), 455\u2013477 (2012)","journal-title":"J. Comput. Biol."},{"key":"165_CR6","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/j.tcs.2012.02.002","volume":"483","author":"M Bauer","year":"2013","unstructured":"Bauer, M., Cox, A., Rosone, G.: Lightweight algorithms for constructing and inverting the BWT of string collections. Theor. Comput. Sci. 483, 134\u2013148 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"165_CR7","doi-asserted-by":"publisher","unstructured":"Bauer, M., Cox, A., Rosone, G., Sciortino, M.: Lightweight LCP construction for next-generation sequencing datasets. In: Algorithms in Bioinformatics, LNCS, vol. 7534, pp. 326\u2013337. Springer, Berlin, Germany (2012)","DOI":"10.1007\/978-3-642-33122-0_26"},{"issue":"7","key":"165_CR8","doi-asserted-by":"publisher","first-page":"1673","DOI":"10.1093\/comjnl\/bxu116","volume":"58","author":"N Beerenwinkel","year":"2015","unstructured":"Beerenwinkel, N., Beretta, S., Bonizzoni, P., Dondi, R., Pirola, Y.: Covering pairs in directed acyclic graphs. Comput. J. 58(7), 1673\u20131686 (2015)","journal-title":"Comput. J."},{"issue":"D1","key":"165_CR9","doi-asserted-by":"publisher","first-page":"D32","DOI":"10.1093\/nar\/gkt1030","volume":"42","author":"D Benson","year":"2014","unstructured":"Benson, D., Clark, K., Karsch-Mizrachi, I., et al.: GenBank. Nucleic Acids Research 42(D1), D32\u2013D37 (2014)","journal-title":"Nucleic Acids Research"},{"issue":"1","key":"165_CR10","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1089\/cmb.2013.0112","volume":"16","author":"S Beretta","year":"2014","unstructured":"Beretta, S., Bonizzoni, P., Della\u00a0Vedova, G., Pirola, Y., Rizzi, R.: Modeling alternative splicing variants from RNA-Seq data with isoform graphs. J. Comput Biol 16(1), 16\u201340 (2014)","journal-title":"J. Comput Biol"},{"key":"165_CR11","doi-asserted-by":"publisher","first-page":"630","DOI":"10.1145\/179812.179818","volume":"41","author":"A Blum","year":"1994","unstructured":"Blum, A., Jiang, T., Li, M., Tromp, J., Yannakakis, M.: Linear approximation of shortest superstrings. J. ACM 41, 630\u2013647 (1994)","journal-title":"J. ACM"},{"key":"165_CR12","doi-asserted-by":"publisher","unstructured":"Bonizzoni, P., Della\u00a0Vedova, G., Pirola, Y., Previtali, M., Rizzi, R.: Constructing string graphs in external memory. In: Algorithms in Bioinformatics, LNCS, vol. 8701, pp. 311\u2013325. Springer, Berlin, Germany (2014)","DOI":"10.1007\/978-3-662-44753-6_23"},{"issue":"3","key":"165_CR13","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1089\/cmb.2015.0172","volume":"23","author":"P Bonizzoni","year":"2016","unstructured":"Bonizzoni, P., Della Vedova, G., Pirola, Y., Previtali, M., Rizzi, R.: LSG: An external-memory tool to compute string graphs for NGS data assembly. J. Comput. Biol. 23(3), 137\u2013149 (2016). doi: 10.1089\/cmb.2015.0172","journal-title":"J. Comput. Biol."},{"key":"165_CR14","unstructured":"Burrows, M., Wheeler, D.J.: A block-sorting lossless data compression algorithm. Technical report, Digital Systems Research Center (1994)"},{"key":"165_CR15","doi-asserted-by":"publisher","unstructured":"Chen, Y., Dong, G., Han, J., Wah, B., Wang, J.: Multi-dimensional regression analysis of time-series data streams. In: Proceedings of the 28th International Conference on Very Large Data Bases, pp. 323\u2013334. VLDB Endowment (2002)","DOI":"10.1016\/B978-155860869-6\/50036-6"},{"key":"165_CR16","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1186\/1748-7188-8-22","volume":"8","author":"R Chikhi","year":"2013","unstructured":"Chikhi, R., Rizk, G.: Space-efficient and exact de Bruijn graph representation based on a Bloom filter. Algorithms Mol. Biol. 8, 22 (2013)","journal-title":"Algorithms Mol. Biol."},{"issue":"11","key":"165_CR17","doi-asserted-by":"publisher","first-page":"1415","DOI":"10.1093\/bioinformatics\/bts173","volume":"28","author":"A Cox","year":"2012","unstructured":"Cox, A., Bauer, M., Jakobi, T., Rosone, G.: Large-scale compression of genomic sequence databases with the Burrows\u2013Wheeler transform. Bioinformatics 28(11), 1415\u20131419 (2012)","journal-title":"Bioinformatics"},{"key":"165_CR18","doi-asserted-by":"publisher","unstructured":"Cox, A., Jakobi, T., Rosone, G., Schulz-Trieglaff, O.: Comparing DNA sequence collections by direct comparison of compressed text indexes. In: Algorithms in Bioinformatics, LNCS, vol. 7534, pp. 214\u2013224. Springer, Berlin, Germany (2012)","DOI":"10.1007\/978-3-642-33122-0_17"},{"issue":"1","key":"165_CR19","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1145\/1644015.1644021","volume":"6","author":"C Demetrescu","year":"2009","unstructured":"Demetrescu, C., Finocchi, I., Ribichini, A.: Trading off space for passes in graph streaming problems. ACM Trans. Algorithms 6(1), 6 (2009)","journal-title":"ACM Trans. Algorithms"},{"key":"165_CR20","volume-title":"Graph Theory. Graduate Texts in Mathematics","author":"R Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory. Graduate Texts in Mathematics, 3rd edn. Springer, Heidelberg (2005)","edition":"3"},{"issue":"4","key":"165_CR21","doi-asserted-by":"publisher","first-page":"552","DOI":"10.1145\/1082036.1082039","volume":"52","author":"P Ferragina","year":"2005","unstructured":"Ferragina, P., Manzini, G.: Indexing compressed text. J. ACM 52(4), 552\u2013581 (2005)","journal-title":"J. ACM"},{"key":"165_CR22","doi-asserted-by":"publisher","unstructured":"Henzinger, M., Raghavan, P., Rajagopalan, S.: Computing on data streams. In: External Memory Algorithms, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.\u00a050, pp. 107\u2013118. AMS, Boston, MA, USA (1999)","DOI":"10.1090\/dimacs\/050\/05"},{"key":"165_CR23","doi-asserted-by":"publisher","unstructured":"Lacroix, V., Sammeth, M., Guigo, R., Bergeron, A.: Exact transcriptome reconstruction from short sequence reads. In: Algorithms in Bioinformatics, LNCS, vol. 5251, pp. 50\u201363. Springer, Berlin, Heidelberg (2008)","DOI":"10.1007\/978-3-540-87361-7_5"},{"key":"165_CR24","doi-asserted-by":"publisher","unstructured":"Lam, T., Li, R., Tam, A., Wong, S., Wu, E., Yiu, S.: High throughput short read alignment via bi-directional BWT. In: Bioinformatics and Biomedicine (BIBM \u201909), pp. 31\u201336. IEEE Computer Society, Washington, DC, USA (2009)","DOI":"10.1109\/BIBM.2009.42"},{"issue":"9","key":"165_CR25","doi-asserted-by":"publisher","first-page":"1297","DOI":"10.1101\/gr.107524.110","volume":"20","author":"A McKenna","year":"2010","unstructured":"McKenna, A., Hanna, M., Banks, E., et al.: The Genome Analysis Toolkit: a MapReduce framework for analyzing next-generation DNA sequencing data. Genome Res. 20(9), 1297\u20131303 (2010)","journal-title":"Genome Res."},{"issue":"suppl.\u00a02","key":"165_CR26","doi-asserted-by":"crossref","first-page":"ii79","DOI":"10.1093\/bioinformatics\/bti1114","volume":"21","author":"E Myers","year":"2005","unstructured":"Myers, E.: The fragment assembly string graph. Bioinformatics 21(suppl.\u00a02), ii79\u2013ii85 (2005)","journal-title":"Bioinformatics"},{"issue":"33","key":"165_CR27","doi-asserted-by":"publisher","first-page":"13272","DOI":"10.1073\/pnas.1121464109","volume":"109","author":"J Pell","year":"2012","unstructured":"Pell, J., Hintze, A., Canino-Koning, R., Howe, A., Tiedje, J., Brown, C.: Scaling metagenome sequence assembly with probabilistic de Bruijn graphs. PNAS 109(33), 13272\u201313277 (2012)","journal-title":"PNAS"},{"issue":"11","key":"165_CR28","doi-asserted-by":"publisher","first-page":"1420","DOI":"10.1093\/bioinformatics\/bts174","volume":"28","author":"Y Peng","year":"2012","unstructured":"Peng, Y., Leung, H.C., Yiu, S.-M., Chin, F.: IDBA-UD: a de novo assembler for single-cell and metagenomic sequencing data with highly uneven depth. Bioinformatics 28(11), 1420\u20131428 (2012)","journal-title":"Bioinformatics"},{"key":"165_CR29","doi-asserted-by":"publisher","unstructured":"Rosone, G., Sciortino, M.: The Burrows\u2013Wheeler transform between data compression and combinatorics on words. In: The Nature of Computation. Logic, Algorithms, Applications, LNCS, vol. 7921, pp. 353\u2013364. Springer, Berlin, Heidelberg (2013)","DOI":"10.1007\/978-3-642-39053-1_42"},{"key":"165_CR30","volume-title":"Algorithms in Java","author":"R Sedgewick","year":"2002","unstructured":"Sedgewick, R.: Algorithms in Java. Addison-Wesley Professional, Reading (2002)"},{"key":"165_CR31","doi-asserted-by":"publisher","unstructured":"Shi, F.: Suffix arrays for multiple strings: a method for on-line multiple string searches. In: Concurrency and Parallelism, Programming, Networking, and Security, LNCS, vol. 1179, pp. 11\u201322. Springer Berlin, Heidelberg (1996)","DOI":"10.1007\/BFb0027775"},{"issue":"12","key":"165_CR32","doi-asserted-by":"publisher","first-page":"i367","DOI":"10.1093\/bioinformatics\/btq217","volume":"26","author":"J Simpson","year":"2010","unstructured":"Simpson, J., Durbin, R.: Efficient construction of an assembly string graph using the FM-index. Bioinformatics 26(12), i367\u2013i373 (2010)","journal-title":"Bioinformatics"},{"key":"165_CR33","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1101\/gr.126953.111","volume":"22","author":"J Simpson","year":"2012","unstructured":"Simpson, J., Durbin, R.: Efficient de novo assembly of large genomes using compressed data structures. Genome Res. 22, 549\u2013556 (2012)","journal-title":"Genome Res."},{"issue":"6","key":"165_CR34","doi-asserted-by":"publisher","first-page":"1117","DOI":"10.1101\/gr.089532.108","volume":"19","author":"J Simpson","year":"2009","unstructured":"Simpson, J., Wong, K., Jackman, S., et al.: ABySS: a parallel assembler for short read sequence data. Genome Res. 19(6), 1117\u20131123 (2009)","journal-title":"Genome Res."},{"key":"165_CR35","doi-asserted-by":"publisher","unstructured":"Valiant, L.: General purpose parallel architectures. In: Handbook of Theoretical Computer Science, vol. A, pp. 943\u2013973. MIT Press, Cambridge, MA, USA (1990)","DOI":"10.1016\/B978-0-444-88071-0.50023-0"},{"issue":"2","key":"165_CR36","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1145\/384192.384193","volume":"33","author":"J Vitter","year":"2001","unstructured":"Vitter, J.: External memory algorithms and data structures: dealing with massive data. ACM Comput. Surv. 33(2), 209\u2013271 (2001)","journal-title":"ACM Comput. Surv."},{"issue":"2","key":"165_CR37","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1007\/BF01185207","volume":"12","author":"J Vitter","year":"1994","unstructured":"Vitter, J., Shriver, E.: Algorithms for parallel memory, I: two-level memories. Algorithmica 12(2), 110\u2013147 (1994)","journal-title":"Algorithmica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0165-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0165-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0165-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0165-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,17]],"date-time":"2024-06-17T07:19:20Z","timestamp":1718608760000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0165-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,5,31]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,6]]}},"alternative-id":["165"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0165-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2016,5,31]]}}}