{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,21]],"date-time":"2026-01-21T10:10:23Z","timestamp":1768990223730,"version":"3.49.0"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,3,8]],"date-time":"2019-03-08T00:00:00Z","timestamp":1552003200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001807","name":"Funda\u00e7\u00e3o de Amparo \u00e0 Pesquisa do Estado de S\u00e3o Paulo","doi-asserted-by":"publisher","award":["2017\/09105-0"],"award-info":[{"award-number":["2017\/09105-0"]}],"id":[{"id":"10.13039\/501100001807","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003407","name":"Ministero dell\u2019Istruzione, dell\u2019Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["PRIN 201534HNXC"],"award-info":[{"award-number":["PRIN 201534HNXC"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"published-print":{"date-parts":[[2019,12]]},"DOI":"10.1186\/s13015-019-0140-0","type":"journal-article","created":{"date-parts":[[2019,3,8]],"date-time":"2019-03-08T18:07:33Z","timestamp":1552068453000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":28,"title":["External memory BWT and LCP computation for sequence collections with applications"],"prefix":"10.1186","volume":"14","author":[{"given":"Lavinia","family":"Egidi","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2931-1470","authenticated-orcid":false,"given":"Felipe A.","family":"Louza","sequence":"additional","affiliation":[]},{"given":"Giovanni","family":"Manzini","sequence":"additional","affiliation":[]},{"given":"Guilherme P.","family":"Telles","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,3,8]]},"reference":[{"key":"140_CR1","unstructured":"Burrows M, Wheeler DJ. A block-sorting lossless data compression algorithm. Technical report, Digital SRC Research Report; 1994."},{"key":"140_CR2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139940023","volume-title":"Genome-Scale Algorithm Design: biological sequence analysis in the era of high-throughput sequencing","author":"V M\u00e4kinen","year":"2015","unstructured":"M\u00e4kinen V, Belazzougui D, Cunial F, Tomescu AI. Genome-Scale Algorithm Design: biological sequence analysis in the era of high-throughput sequencing. Cambridge: Cambridge University Press; 2015."},{"issue":"5","key":"140_CR3","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U Manber","year":"1993","unstructured":"Manber U, Myers G. Suffix arrays: a new method for on-line string searches. SIAM J Comput. 1993;22(5):935\u201348.","journal-title":"SIAM J Comput"},{"key":"140_CR4","first-page":"2","volume":"18","author":"S Gog","year":"2013","unstructured":"Gog S, Ohlebusch E. Compressed suffix trees: efficient computation and storage of LCP-values. ACM J Exp Algorith. 2013;18:2.","journal-title":"ACM J Exp Algorith"},{"key":"140_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1216370.1216372","volume":"39","author":"G Navarro","year":"2007","unstructured":"Navarro G, M\u00e4kinen V. Compressed full-text indexes. ACM Comput Surv. 2007;39:1.","journal-title":"ACM Comput Surv"},{"key":"140_CR6","doi-asserted-by":"crossref","unstructured":"Burkhardt S, K\u00e4rkk\u00e4inen J. Fast lightweight suffix array construction and checking. In: Proc. 14th symposium on combinatorial pattern matching (CPM \u201903). Springer, Morelia, Michoc\u00e4n, Mexico; 2003. p. 55\u201369.","DOI":"10.1007\/3-540-44888-8_5"},{"key":"140_CR7","doi-asserted-by":"crossref","unstructured":"Manzini G. Two space saving tricks for linear time LCP computation. In: Proc. of 9th Scandinavian workshop on algorithm theory (SWAT \u201904). Humleb\u00e6k: Springer; 2004. p. 372\u201383.","DOI":"10.1007\/978-3-540-27810-8_32"},{"key":"140_CR8","doi-asserted-by":"crossref","unstructured":"Manzini G, Ferragina P. Engineering a lightweight suffix array construction algorithm. In: Proc. 10th European symposium on algorithms (ESA). Rome: Springer; 2002. p. 698\u2013710.","DOI":"10.1007\/3-540-45749-6_61"},{"key":"140_CR9","unstructured":"Ferragina P, Gagie T, Manzini G. Lightweight data indexing and compression in external memory. In: Proc. 9th Latin American theoretical informatics symposium (LATIN \u201910). Lecture Notes in Computer Science vol. 6034; 2010. p. 698\u2013711."},{"key":"140_CR10","doi-asserted-by":"crossref","unstructured":"Ferragina P, Gagie T, Manzini G. Lightweight data indexing and compression in external memory. Algorithmica. 2011.","DOI":"10.1007\/s00453-011-9535-0"},{"issue":"1","key":"140_CR11","first-page":"1","volume":"21","author":"J K\u00e4rkk\u00e4inen","year":"2016","unstructured":"K\u00e4rkk\u00e4inen J, Kempa D. LCP array construction in external memory. ACM J Exp Algorith. 2016;21(1):1\u2013711722.","journal-title":"ACM J Exp Algorith"},{"key":"140_CR12","doi-asserted-by":"crossref","unstructured":"Beller T, Zwerger M, Gog S, Ohlebusch E. Space-efficient construction of the Burrows\u2013Wheeler transform. In: SPIRE. Lecture Notes in Computer Science, vol. 8214. Jerusalem: Springer; 2013. p. 5\u201316.","DOI":"10.1007\/978-3-319-02432-5_5"},{"issue":"2","key":"140_CR13","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/s11786-016-0281-1","volume":"11","author":"J K\u00e4rkk\u00e4inen","year":"2017","unstructured":"K\u00e4rkk\u00e4inen J, Kempa D. Engineering a lightweight external memory suffix array construction algorithm. Math Comput Sci. 2017;11(2):137\u201349.","journal-title":"Math Comput Sci"},{"issue":"1","key":"140_CR14","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1186\/s13015-017-0117-9","volume":"12","author":"FA Louza","year":"2017","unstructured":"Louza FA, Telles GP, Hoffmann S, Ciferri CDA. Generalized Enhanced Suffix array construction in external memory. Algorith Mol Biol. 2017;12(1):26\u201312616.","journal-title":"Algorith Mol Biol"},{"issue":"2","key":"140_CR15","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. 2001;33(2):209\u201371.","journal-title":"ACM Comput Surv"},{"key":"140_CR16","doi-asserted-by":"crossref","unstructured":"Belazzougui D. Linear time construction of compressed text indices in compact space. In: STOC. New York: ACM; 2014. p. 148\u201393.","DOI":"10.1145\/2591796.2591885"},{"key":"140_CR17","doi-asserted-by":"crossref","unstructured":"Munro JI, Navarro G, Nekrich Y. Space-efficient construction of compressed indexes in deterministic linear time. In: SODA. Barcelona: SIAM; 2017. p. 408\u201324.","DOI":"10.1137\/1.9781611974782.26"},{"key":"140_CR18","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/j.tcs.2012.02.002","volume":"483","author":"MJ Bauer","year":"2013","unstructured":"Bauer MJ, Cox AJ, Rosone G. Lightweight algorithms for constructing and inverting the BWT of string collections. Theor Comput Sci. 2013;483:134\u201348.","journal-title":"Theor Comput Sci"},{"key":"140_CR19","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/j.jda.2016.03.003","volume":"37","author":"AX Cox","year":"2016","unstructured":"Cox AX, Garofalo F, Rosone G, Sciortino M. Lightweight LCP construction for very large collections of strings. J Discrete Algorith. 2016;37:17\u201333.","journal-title":"J Discrete Algorith"},{"key":"140_CR20","unstructured":"Bonizzoni P, Della Vedova G, Pirola Y, Previtali M, Rizzi R. Computing the BWT and LCP array of a set of strings in external memory. CoRR: \n                    arXiv:1705.07756\n                    \n                  . 2017."},{"issue":"2","key":"140_CR21","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1109\/TCBB.2011.127","volume":"9","author":"MO K\u00fclekci","year":"2012","unstructured":"K\u00fclekci MO, Vitter JS, Xu B. Efficient maximal repeat finding using the Burrows\u2013Wheeler transform and wavelet tree. IEEE\/ACM Trans Comput Biol Bioinform. 2012;9(2):421\u20139.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinform"},{"key":"140_CR22","doi-asserted-by":"crossref","unstructured":"Ohlebusch E, Gog S, K\u00fcgel A. Computing matching statistics and maximal exact matches on compressed full-text indexes. In: SPIRE. Lecture Notes in Computer Science, vol. 6393. Los Cabos: Springer; 2010. p. 347\u201358.","DOI":"10.1007\/978-3-642-16321-0_36"},{"issue":"4","key":"140_CR23","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/0020-0190(92)90176-V","volume":"41","author":"D Gusfield","year":"1992","unstructured":"Gusfield D, Landau GM, Schieber B. An efficient algorithm for the all pairs suffix\u2013prefix problem. Inform Process Lett. 1992;41(4):181\u20135.","journal-title":"Inform Process Lett"},{"issue":"3","key":"140_CR24","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/j.ipl.2009.10.015","volume":"110","author":"E Ohlebusch","year":"2010","unstructured":"Ohlebusch E, Gog S. Efficient algorithms for the all-pairs suffix\u2013prefix problem and the all-pairs substring-prefix problem. Inform Process Lett. 2010;110(3):123\u20138.","journal-title":"Inform Process Lett"},{"key":"140_CR25","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1016\/j.jda.2016.04.002","volume":"37","author":"WHA Tustumi","year":"2016","unstructured":"Tustumi WHA, Gog S, Telles GP, Louza FA. An improved algorithm for the all-pairs suffix\u2013prefix problem. J Discrete Algorith. 2016;37:34\u201343.","journal-title":"J Discrete Algorith"},{"key":"140_CR26","doi-asserted-by":"crossref","unstructured":"Belazzougui D, Gagie T, M\u00e4kinen V, Previtali M, Puglisi SJ. Bidirectional variable-order de Bruijn graphs. In: LATIN. Lecture Notes in Computer Science, vol. 9644. Ensenada: Springer; 2016. p. 164\u201378.","DOI":"10.1007\/978-3-662-49529-2_13"},{"key":"140_CR27","doi-asserted-by":"crossref","unstructured":"Boucher C, Bowe A, Gagie T, Puglisi SJ, Sadakane K. Variable-order de Bruijn graphs. In: DCC. IEEE, Snowbird, Utah, USA; 2015. p. 383\u2013392","DOI":"10.1109\/DCC.2015.70"},{"key":"140_CR28","doi-asserted-by":"crossref","unstructured":"Bowe A, Onodera T, Sadakane K, Shibuya T. Succinct de Bruijn graphs. In: WABI. Lecture Notes in Computer Science, vol. 7534. Ljubljana: Springer; 2012. p. 225\u201335.","DOI":"10.1007\/978-3-642-33122-0_18"},{"key":"140_CR29","doi-asserted-by":"crossref","unstructured":"Bonizzoni P, Della Vedova G, Pirola Y, Previtali M, Rizzi R. Constructing string graphs in external memory. In: WABI. Lecture Notes in Computer Science, vol. 8701. Berlin: Springer; 2014. p. 311\u201325.","DOI":"10.1007\/978-3-662-44753-6_23"},{"issue":"2","key":"140_CR30","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1007\/s00453-016-0165-4","volume":"78","author":"P Bonizzoni","year":"2017","unstructured":"Bonizzoni P, Della Vedova G, Pirola Y, Previtali M, Rizzi R. An external-memory algorithm for string graph construction. Algorithmica. 2017;78(2):394\u2013424. \n                    https:\/\/doi.org\/10.1007\/s00453-016-0165-4\n                    \n                  .","journal-title":"Algorithmica"},{"issue":"3","key":"140_CR31","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1016\/j.tcs.2007.07.014","volume":"387","author":"S Mantaci","year":"2007","unstructured":"Mantaci S, Restivo A, Rosone G, Sciortino M. An extension of the Burrows\u2013Wheeler transform. Theor Comput Sci. 2007;387(3):298\u2013312.","journal-title":"Theor Comput Sci"},{"key":"140_CR32","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/j.tcs.2017.03.039","volume":"678","author":"FA Louza","year":"2017","unstructured":"Louza FA, Gog S, Telles GP. Inducing enhanced suffix arrays for string collections. Theor Comput Sci. 2017;678:22\u201339.","journal-title":"Theor Comput Sci"},{"issue":"3","key":"140_CR33","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1145\/2493175.2493180","volume":"31","author":"G Nong","year":"2013","unstructured":"Nong G. Practical linear-time O(1)-workspace suffix sorting for constant alphabets. ACM Trans Inform Syst. 2013;31(3):15.","journal-title":"ACM Trans Inform Syst"},{"key":"140_CR34","doi-asserted-by":"crossref","unstructured":"Egidi L, Manzini G. Lightweight BWT and LCP merging via the Gap algorithm. In: SPIRE. Lecture Notes in Computer Science, vol. 10508. Palermo: Springer; 2017. p. 176\u201390.","DOI":"10.1007\/978-3-319-67428-5_15"},{"issue":"24","key":"140_CR35","doi-asserted-by":"publisher","first-page":"3524","DOI":"10.1093\/bioinformatics\/btu584","volume":"30","author":"J Holt","year":"2014","unstructured":"Holt J, McMillan L. Merging of multi-string BWTs with applications. Bioinformatics. 2014;30(24):3524\u201331.","journal-title":"Bioinformatics"},{"key":"140_CR36","doi-asserted-by":"crossref","unstructured":"Holt J, McMillan L. Constructing Burrows\u2013Wheeler transforms of large string collections via merging. In: BCB. New York: ACM; 2014. p. 464\u201371.","DOI":"10.1145\/2649387.2649431"},{"key":"140_CR37","unstructured":"Knuth DE. Sorting and searching, 2nd edn. In: The art of computer programming, vol. 3. Reading: Addison-Wesley; 1998. p. 780."},{"key":"140_CR38","unstructured":"Cox AJ, Garofalo F, Rosone G, Sciortino M. Multi-string eBWT\/LCP\/GSA computation (commit no. 6c6a1b38bc084d35330295800f9d4a6882052c51). GitHub; 2018. \n                    https:\/\/github.com\/giovannarosone\/BCR_LCP_GSA\n                    \n                  ."},{"key":"140_CR39","unstructured":"Bonizzoni P, Della Vedova G, Nicosia S, Previtali M, Rizzi R. bwt-lcp-em (commit no. a6f0144b203e5bda7af8480e9ea3a1d781ad7ba0). GitHub; 2018. \n                    https:\/\/github.com\/AlgoLab\/bwt-lcp-em\n                    \n                  ."},{"key":"140_CR40","unstructured":"Louza FA, Telles GP, Hoffmann S, Ciferri CDA. egsa (commit no. 1790094e010040bef3be11e393a4f1d5408debb0). GitHub; 2018. \n                    https:\/\/github.com\/felipelouza\/egsa\n                    \n                  ."},{"key":"140_CR41","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on strings, trees, and sequences: computer science and computational biology","author":"D Gusfield","year":"1997","unstructured":"Gusfield D. Algorithms on strings, trees, and sequences: computer science and computational biology. Cambridge: Cambridge University Press; 1997."},{"issue":"6","key":"140_CR42","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1002\/spe.844","volume":"38","author":"R Dementiev","year":"2008","unstructured":"Dementiev R, Kettner L, Sanders P. STXXL: standard template library for XXL data sets. Softw Pract Exper. 2008;38(6):589\u2013637. \n                    https:\/\/doi.org\/10.1002\/spe.844\n                    \n                  .","journal-title":"Softw Pract Exper"},{"issue":"1","key":"140_CR43","doi-asserted-by":"publisher","first-page":"e1005944","DOI":"10.1371\/journal.pcbi.1005944","volume":"14","author":"G Mar\u00e7ais","year":"2018","unstructured":"Mar\u00e7ais G, Delcher AL, Phillippy AM, Coston R, Salzberg SL, Zimin AV. Mummer4: a fast and versatile genome alignment system. PLoS Comput Biol. 2018;14(1):e1005944.","journal-title":"PLoS Comput Biol"},{"issue":"20","key":"140_CR44","doi-asserted-by":"publisher","first-page":"3181","DOI":"10.1093\/bioinformatics\/btx067","volume":"33","author":"MD Muggli","year":"2017","unstructured":"Muggli MD, Bowe A, Noyes NR, Morley PS, Belk KE, Raymond R, Gagie T, Puglisi SJ, Boucher C. Succinct colored de Bruijn graphs. Bioinformatics. 2017;33(20):3181\u20137.","journal-title":"Bioinformatics"},{"key":"140_CR45","doi-asserted-by":"crossref","unstructured":"Louza FA, Telles GP, Gog S, Zhao L. Computing Burrows\u2013Wheeler similarity distributions for string collections. SPIRE. Lecture Notes in Computer Science, vol. 11147. Lima: Springer; 2018. p. 285\u201396.","DOI":"10.1007\/978-3-030-00479-8_23"},{"key":"140_CR46","unstructured":"Prezza N, Pisanti N, Sciortino M, Rosone G. Detecting mutations by ebwt. In: WABI. LIPIcs, vol. 113. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Helsinki, Finland; 2018. p. 3\u20131315."},{"key":"140_CR47","doi-asserted-by":"crossref","unstructured":"Garofalo F, Rosone G, Sciortino M, Verzotto D. The colored longest common prefix array computed via sequential scans. SPIRE. Lecture Notes in Computer Science, vol. 11147. Lima: Springer; 2018. p. 153\u201367.","DOI":"10.1007\/978-3-030-00479-8_13"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-019-0140-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/s13015-019-0140-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-019-0140-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,3,7]],"date-time":"2020-03-07T00:10:24Z","timestamp":1583539824000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-019-0140-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,8]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,12]]}},"alternative-id":["140"],"URL":"https:\/\/doi.org\/10.1186\/s13015-019-0140-0","relation":{},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,3,8]]},"assertion":[{"value":"6 November 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 February 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 March 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"6"}}