{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:29:20Z","timestamp":1759638560628,"version":"3.37.3"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"1","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\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["162338\/2015-5"],"award-info":[{"award-number":["162338\/2015-5"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002322","name":"Coordena\u00e7\u00e3o de Aperfei\u00e7oamento de Pessoal de N\u00edvel Superior","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002322","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001807","name":"Funda\u00e7\u00e3o de Amparo \u00e0 Pesquisa do Estado de S\u00e3o Paulo","doi-asserted-by":"publisher","award":["2011\/15423-9","2011\/23904-7"],"award-info":[{"award-number":["2011\/15423-9","2011\/23904-7"]}],"id":[{"id":"10.13039\/501100001807","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":[[2017,12]]},"DOI":"10.1186\/s13015-017-0117-9","type":"journal-article","created":{"date-parts":[[2017,12,7]],"date-time":"2017-12-07T04:17:42Z","timestamp":1512620262000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Generalized enhanced suffix array construction in external memory"],"prefix":"10.1186","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2931-1470","authenticated-orcid":false,"given":"Felipe A.","family":"Louza","sequence":"first","affiliation":[]},{"given":"Guilherme P.","family":"Telles","sequence":"additional","affiliation":[]},{"given":"Steve","family":"Hoffmann","sequence":"additional","affiliation":[]},{"given":"Cristina D. A.","family":"Ciferri","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,12,7]]},"reference":[{"issue":"4","key":"117_CR1","doi-asserted-by":"crossref","first-page":"806","DOI":"10.1007\/s00453-009-9369-1","volume":"60","author":"M Arnold","year":"2011","unstructured":"Arnold M, Ohlebusch E. Linear time algorithms for generalizations of the longest common substring problem. Algorithmica. 2011;60(4):806\u201318.","journal-title":"Algorithmica"},{"issue":"1","key":"117_CR2","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/S1570-8667(03)00065-0","volume":"2","author":"MI Abouelhoda","year":"2004","unstructured":"Abouelhoda MI, Kurtz S, Ohlebusch E. Replacing suffix trees with enhanced suffix arrays. J Discret Algorithms. 2004;2(1):53\u201386.","journal-title":"J Discret Algorithms"},{"doi-asserted-by":"crossref","unstructured":"Babenko MA, Starikovskaya T. Computing longest common substrings via suffix arrays. In: Proceedings of computer science in Russia symposium. 2008. p. 64\u201375.","key":"117_CR3","DOI":"10.1007\/978-3-540-79709-8_10"},{"issue":"3","key":"117_CR4","doi-asserted-by":"crossref","first-page":"644","DOI":"10.1016\/j.is.2010.11.001","volume":"36","author":"M Barsky","year":"2011","unstructured":"Barsky M, Stege U, Thomo A. Suffix trees for inputs larger than main memory. Inform Syst J. 2011;36(3):644\u201354.","journal-title":"Inform Syst J"},{"key":"117_CR5","doi-asserted-by":"crossref","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"},{"doi-asserted-by":"crossref","unstructured":"Bauer MJ, Cox AJ, Rosone G, Sciortino M. Lightweight LCP construction for next-generation sequencing datasets. In: Proceedings of WABI. Berlin: Springer; 2012. p. 326\u201337.","key":"117_CR6","DOI":"10.1007\/978-3-642-33122-0_26"},{"key":"117_CR7","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1016\/j.jda.2012.07.007","volume":"18","author":"T Beller","year":"2013","unstructured":"Beller T, Gog S, Ohlebusch E, Schnattinger T. Computing the longest common prefix array based on the Burrows\u2013Wheeler transform. J Discret Algorithms. 2013;18:22\u201331.","journal-title":"J Discret Algorithms"},{"key":"117_CR8","first-page":"5","volume":"8214","author":"T Beller","year":"2013","unstructured":"Beller T, Zwerger M, Gog S, Ohlebusch E. Space-efficient construction of the Burrows\u2013Wheeler transform. Proc SPIRE. 2013;8214:5\u201316.","journal-title":"Proc SPIRE"},{"key":"117_CR9","first-page":"1","volume":"77","author":"T Bingmann","year":"2015","unstructured":"Bingmann T, Eberle A, Sanders P. Engineering parallel string sorting. Algorithmica. 2015;77:1\u201352.","journal-title":"Algorithmica"},{"issue":"2","key":"117_CR10","first-page":"2.3:1","volume":"21","author":"T Bingmann","year":"2016","unstructured":"Bingmann T, Fischer J, Osipov V. Inducing suffix and LCP arrays in external memory. ACM J Exp Algorithmics. 2016;21(2):2.3:1\u201327.","journal-title":"ACM J Exp Algorithmics"},{"unstructured":"Bingmann T. eSAIS. https:\/\/tbingmann.de\/2012\/esais . Accessed Jun 2017.","key":"117_CR11"},{"unstructured":"Burrows M, Wheeler DJ. A block-sorting lossless data compression algorithm. Digital SRC Research Report. 1994. http:\/\/citeseerx.ist.psu.edu\/viewdoc\/summary?doi=10.1.1.121.6177","key":"117_CR12"},{"key":"117_CR13","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/j.jda.2016.03.003","volume":"37","author":"AJ Cox","year":"2016","unstructured":"Cox AJ, Garofalo F, Rosone G, Sciortino M. Lightweight LCP construction for very large collections of strings. J Discret Algorithms. 2016;37:17\u201333.","journal-title":"J Discret Algorithms"},{"issue":"1","key":"117_CR14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00453-001-0051-5","volume":"32","author":"A Crauser","year":"2002","unstructured":"Crauser A, Ferragina P. A theoretical and experimental study on the construction of suffix arrays in external memory. Algorithmica. 2002;32(1):1\u201335.","journal-title":"Algorithmica"},{"doi-asserted-by":"crossref","unstructured":"Crochemore M, Grossi R, K\u00e4rkk\u00e4inen J, Landau GM. A constant-space comparison-based algorithm for computing the Burrows\u2013Wheeler transform. In: Proceedings of CPM. Berlin: Springer; 2013. p. 74\u201382.","key":"117_CR15","DOI":"10.1007\/978-3-642-38905-4_9"},{"key":"117_CR16","doi-asserted-by":"crossref","first-page":"3.4:1","DOI":"10.1145\/1227161.1402296","volume":"12","author":"R Dementiev","year":"2008","unstructured":"Dementiev R, K\u00e4rkk\u00e4inen J, Mehnert J, Sanders P. Better external memory suffix array construction. ACM J Exp Algorithmics. 2008;12:3.4:1\u201324.","journal-title":"ACM J Exp Algorithmics"},{"unstructured":"Dhaliwal J, Puglisi SJ, Turpin A. Trends in suffix sorting: a survey of low memory algorithms. In: Proceedings of ACSC. Canberra: ACSC; 2012. p. 91\u20138.","key":"117_CR17"},{"issue":"3","key":"117_CR18","doi-asserted-by":"crossref","first-page":"707","DOI":"10.1007\/s00453-011-9535-0","volume":"63","author":"P Ferragina","year":"2012","unstructured":"Ferragina P, Gagie T, Manzini G. Lightweight data indexing and compression in external memory. Algorithmica. 2012;63(3):707\u201330.","journal-title":"Algorithmica"},{"doi-asserted-by":"crossref","unstructured":"Fischer J. Inducing the LCP-array. In: Proceedings of WADS. Ansonia: WADS; 2011. p. 374\u201385.","key":"117_CR19","DOI":"10.1007\/978-3-642-22300-6_32"},{"doi-asserted-by":"crossref","unstructured":"Flick P, Aluru S. Parallel distributed memory construction of suffix and longest common prefix arrays. In: Proceedings of SC. Carolina: SC; 2015. p. 16:1\u201310.","key":"117_CR20","DOI":"10.1145\/2807591.2807609"},{"issue":"8","key":"117_CR21","doi-asserted-by":"crossref","first-page":"1918","DOI":"10.1109\/TKDE.2013.129","volume":"26","author":"S Gog","year":"2014","unstructured":"Gog S, Moffat A, Culpepper JS, Turpin A, Wirth A. Large-scale pattern search using reduced-space on-disk suffix arrays. IEEE Trans Knowl Data Eng. 2014;26(8):1918\u201331.","journal-title":"IEEE Trans Knowl Data Eng"},{"doi-asserted-by":"crossref","unstructured":"Gog S, Ohlebusch E. Fast and lightweight LCP-array construction algorithms. In: Proceedings of ALENEX. Barcelona: ALENEX; 2011. p. 25\u201334.","key":"117_CR22","DOI":"10.1137\/1.9781611972917.3"},{"key":"117_CR23","first-page":"66","volume-title":"New indices for text: pat trees and pat arrays. In: information retrieval","author":"GH Gonnet","year":"1992","unstructured":"Gonnet GH, Baeza-Yates RA, Snider T. New indices for text: pat trees and pat arrays. In: information retrieval. Upper Saddle River: Prentice-Hall, Inc.; 1992. p. 66\u201382."},{"key":"117_CR24","doi-asserted-by":"crossref","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. New York: Cambridge University Press; 1997."},{"unstructured":"K\u00e4rkk\u00e4inen J, Kempa D. Engineering a lightweight external memory suffix array construction algorithm. In: Proceedings of ICABD. 2014. p. 53\u201360.","key":"117_CR25"},{"key":"117_CR26","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 Algorithmics. 2016;21:1\u201322.","journal-title":"ACM J Exp Algorithmics"},{"doi-asserted-by":"crossref","unstructured":"K\u00e4rkk\u00e4inen J, Kempa D, Puglisi SJ. Parallel external memory suffix sorting. In: Proceedings of CPM. 2015. p. 329\u201342.","key":"117_CR27","DOI":"10.1007\/978-3-319-19929-0_28"},{"unstructured":"K\u00e4rkk\u00e4inen J, Kempa D. SAscan. https:\/\/www.cs.helsinki.fi\/group\/pads\/SAscan.html . Accessed Jun 2017.","key":"117_CR28"},{"doi-asserted-by":"crossref","unstructured":"K\u00e4rkk\u00e4inen, J., Manzini, G., Puglisi, S.J.: Permuted longest-common-prefix array. In: Proceedings of CPM. 2009. p. 181\u201392.","key":"117_CR29","DOI":"10.1007\/978-3-642-02441-2_17"},{"issue":"6","key":"117_CR30","doi-asserted-by":"crossref","first-page":"918","DOI":"10.1145\/1217856.1217858","volume":"53","author":"J K\u00e4rkk\u00e4inen","year":"2006","unstructured":"K\u00e4rkk\u00e4inen J, Sanders P, Burkhardt S. Linear work suffix array construction. ACM J. 2006;53(6):918\u201336.","journal-title":"ACM J"},{"doi-asserted-by":"crossref","unstructured":"Kasai T, Lee G, Arimura H, Arikawa S, Park K. Linear-time longest-common-prefix computation in suffix arrays and its applications. In: Proceedings of CPM. 2001. p. 181\u201392.","key":"117_CR31","DOI":"10.1007\/3-540-48194-X_17"},{"key":"117_CR32","volume-title":"The art of computer programming. Sorting and searching","author":"DE Knuth","year":"1998","unstructured":"Knuth DE. The art of computer programming. Sorting and searching, vol. 3. 2nd ed. Redwood City: Addison Wesley Longman Publishing Co.; 1998.","edition":"2"},{"issue":"2\u20134","key":"117_CR33","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/j.jda.2004.08.002","volume":"3","author":"P Ko","year":"2005","unstructured":"Ko P, Aluru S. Space efficient linear time construction of suffix arrays. J Discret Algorithms. 2005;3(2\u20134):143\u201356.","journal-title":"J Discret Algorithms"},{"doi-asserted-by":"crossref","unstructured":"Liu WJ, Nong G, Chan WH, Wu Y. Induced sorting suffixes in external memory with better design and less space. In: Proceedings of SPIRE. Bengaluru: SPIRE; 2015. p. 83\u201394.","key":"117_CR34","DOI":"10.1007\/978-3-319-23826-5_9"},{"key":"117_CR35","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1016\/j.ipl.2016.09.010","volume":"118","author":"FA Louza","year":"2017","unstructured":"Louza FA, Gog S, Telles GP. Optimal suffix sorting and LCP array construction for constant alphabets. Inf Process Lett. 2017;118:30\u20134.","journal-title":"Inf Process Lett"},{"key":"117_CR36","doi-asserted-by":"crossref","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"},{"key":"117_CR37","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/j.jda.2016.11.003","volume":"42","author":"FA Louza","year":"2017","unstructured":"Louza FA, Gagie G, Telles GP. Burrows\u2013Wheeler transform and LCP array construction in constant space. J Discret Algorithms. 2017;42:12\u201322.","journal-title":"J Discret Algorithms"},{"doi-asserted-by":"crossref","unstructured":"Louza FA, Telles GP, Ciferri CDA. External memory generalized suffix and LCP arrays construction. In: Proceedings of CPM. 2013. p. 201\u201310.","key":"117_CR38","DOI":"10.1007\/978-3-642-38905-4_20"},{"key":"117_CR39","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139940023","volume-title":"Genome-scale algorithm design","author":"V M\u00e4kinen","year":"2015","unstructured":"M\u00e4kinen V, Belazzougui D, Cunial F. Genome-scale algorithm design. New York: Cambridge University Press; 2015."},{"issue":"5","key":"117_CR40","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U Manber","year":"1993","unstructured":"Manber U, Myers EW. Suffix arrays: a new method for on-line string searches. SIAM J Comput. 1993;22(5):935\u201348.","journal-title":"SIAM J Comput"},{"doi-asserted-by":"crossref","unstructured":"Manzini G. Two space saving tricks for linear time LCP array computation. In: Proceedings of SWAT. 2004. p. 372\u201383.","key":"117_CR41","DOI":"10.1007\/978-3-540-27810-8_32"},{"doi-asserted-by":"crossref","unstructured":"Munro JI, Navarro G, Nekrich Y. Space-efficient construction of compressed indexes in deterministic linear time. In: Proceedings of SODA. 2017. p. 408\u201324.","key":"117_CR42","DOI":"10.1137\/1.9781611974782.26"},{"key":"117_CR43","first-page":"69","volume":"4","author":"W Ng","year":"2008","unstructured":"Ng W, Kakehi K. Merging string sequences by longest common prefixes. Inf Process Soc Jpn Digit Cour. 2008;4:69\u201378.","journal-title":"Inf Process Soc Jpn Digit Cour"},{"issue":"3","key":"117_CR44","doi-asserted-by":"crossref","first-page":"12:1","DOI":"10.1145\/2699665","volume":"33","author":"G Nong","year":"2015","unstructured":"Nong G, Chan WH, Hu SQ, Wu Y. Induced sorting suffixes in external memory. ACM Trans Inf Syst. 2015;33(3):12:1\u201315.","journal-title":"ACM Trans Inf Syst"},{"key":"117_CR45","doi-asserted-by":"crossref","first-page":"1:1","DOI":"10.1145\/2518175","volume":"32","author":"G Nong","year":"2014","unstructured":"Nong G, Chan WH, Zhang S, Guan XF. Suffix array construction in external memory using d-critical substrings. ACM Trans Inf Syst. 2014;32:1:1\u201315.","journal-title":"ACM Trans Inf Syst"},{"issue":"10","key":"117_CR46","doi-asserted-by":"crossref","first-page":"1471","DOI":"10.1109\/TC.2010.188","volume":"60","author":"G Nong","year":"2011","unstructured":"Nong G, Zhang S, Chan WH. Two efficient algorithms for linear time suffix array construction. IEEE Trans Comput. 2011;60(10):1471\u201384.","journal-title":"IEEE Trans Comput"},{"key":"117_CR47","volume-title":"Bioinformatics Algorithms: Sequence Analysis, Genome Rearrangements, and Phylogenetic Reconstruction","author":"E Ohlebusch","year":"2013","unstructured":"Ohlebusch E. Bioinformatics Algorithms: Sequence Analysis, Genome Rearrangements, and Phylogenetic Reconstruction. Germany: Oldenbusch Verlag; 2013."},{"doi-asserted-by":"crossref","unstructured":"Okanohara D, Sadakane K. A linear-time Burrows\u2013Wheeler transform using induced sorting. In: Proceedings of SPIRE. 2009. p. 90\u2013101.","key":"117_CR48","DOI":"10.1007\/978-3-642-03784-9_9"},{"issue":"2","key":"117_CR49","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1242471.1242472","volume":"39","author":"SJ Puglisi","year":"2007","unstructured":"Puglisi SJ, Smyth WF, Turpin AH. A taxonomy of suffix array construction algorithms. ACM Comput Surv. 2007;39(2):1\u201331.","journal-title":"ACM Comput Surv"},{"doi-asserted-by":"crossref","unstructured":"Sinha R, Puglisi SJ, Moffat A, Turpin A. Improving suffix array locality for fast pattern matching on disk. In: Proceedings of SIGMOD. 2008. p. 661\u201372.","key":"117_CR50","DOI":"10.1145\/1376616.1376683"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-017-0117-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,23]],"date-time":"2020-10-23T23:08:25Z","timestamp":1603494505000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-017-0117-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12]]},"references-count":50,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,12]]}},"alternative-id":["117"],"URL":"https:\/\/doi.org\/10.1186\/s13015-017-0117-9","relation":{},"ISSN":["1748-7188"],"issn-type":[{"type":"electronic","value":"1748-7188"}],"subject":[],"published":{"date-parts":[[2017,12]]},"article-number":"26"}}