{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:17:29Z","timestamp":1760203049135,"version":"3.40.3"},"publisher-location":"Cham","reference-count":42,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319986531"},{"type":"electronic","value":"9783319986548"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-98654-8_1","type":"book-chapter","created":{"date-parts":[[2018,8,4]],"date-time":"2018-08-04T23:43:57Z","timestamp":1533426237000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Block Sorting-Based Transformations on Words: Beyond the Magic BWT"],"prefix":"10.1007","author":[{"given":"Raffaele","family":"Giancarlo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giovanni","family":"Manzini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antonio","family":"Restivo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giovanna","family":"Rosone","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marinella","family":"Sciortino","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,8,5]]},"reference":[{"key":"1_CR1","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/j.tcs.2012.02.002","volume":"483","author":"MJ Bauer","year":"2013","unstructured":"Bauer, M.J., Cox, A.J., 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":"1_CR2","unstructured":"Burrows, M., Wheeler, D.J.: A block sorting data compression algorithm. Technical report, DIGITAL System Research Center (1994)"},{"key":"1_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1007\/978-3-642-33122-0_17","volume-title":"Algorithms in Bioinformatics","author":"AJ Cox","year":"2012","unstructured":"Cox, A.J., Jakobi, T., Rosone, G., Schulz-Trieglaff, O.B.: Comparing DNA sequence collections by direct comparison of compressed text indexes. In: Raphael, B., Tang, J. (eds.) WABI 2012. LNCS, vol. 7534, pp. 214\u2013224. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-33122-0_17"},{"key":"1_CR4","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1016\/j.tcs.2004.11.014","volume":"332","author":"M Crochemore","year":"2005","unstructured":"Crochemore, M., D\u00e9sarm\u00e9nien, J., Perrin, D.: A note on the Burrows-Wheeler transformation. Theor. Comput. Sci. 332, 567\u2013572 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"1_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/3-540-63246-8_15","volume-title":"Structures in Logic and Computer Science","author":"A Luca de","year":"1997","unstructured":"de Luca, A.: Combinatorics of standard Sturmian words. In: Mycielski, J., Rozenberg, G., Salomaa, A. (eds.) Structures in Logic and Computer Science. LNCS, vol. 1261, pp. 249\u2013267. Springer, Heidelberg (1997). https:\/\/doi.org\/10.1007\/3-540-63246-8_15"},{"issue":"2","key":"1_CR6","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1016\/0304-3975(94)00035-H","volume":"136","author":"A Luca de","year":"1994","unstructured":"de Luca, A., Mignosi, F.: Some combinatorial properties of sturmian words. Theor. Comput. Sci. 136(2), 361\u2013385 (1994)","journal-title":"Theor. Comput. Sci."},{"key":"1_CR7","unstructured":"Dolce, F., Restivo, A., Reutenauer, C.: On generalized Lyndon words, submitted"},{"issue":"9","key":"1_CR8","doi-asserted-by":"publisher","first-page":"731","DOI":"10.1093\/comjnl\/39.9.731","volume":"39","author":"P Fenwick","year":"1996","unstructured":"Fenwick, P.: The Burrows-Wheeler transform for block sorting text compression: principles and improvements. Comput. J. 39(9), 731\u2013740 (1996)","journal-title":"Comput. J."},{"key":"1_CR9","unstructured":"Ferenczi, S., Zamboni, L.Q.: Clustering words and interval exchanges. J. Integer Seq. 16(2), Article ID 13.2.1 (2013)"},{"key":"1_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"697","DOI":"10.1007\/978-3-642-12200-2_60","volume-title":"LATIN 2010: Theoretical Informatics","author":"P Ferragina","year":"2010","unstructured":"Ferragina, P., Gagie, T., Manzini, G.: Lightweight data indexing and compression in external memory. In: L\u00f3pez-Ortiz, A. (ed.) LATIN 2010. LNCS, vol. 6034, pp. 697\u2013710. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-12200-2_60"},{"key":"1_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"756","DOI":"10.1007\/11841036_67","volume-title":"Algorithms \u2013 ESA 2006","author":"P Ferragina","year":"2006","unstructured":"Ferragina, P., Giancarlo, R., Manzini, G.: The engineering of a compression boosting library: theory vs practice in BWT compression. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol. 4168, pp. 756\u2013767. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11841036_67"},{"issue":"4","key":"1_CR12","doi-asserted-by":"publisher","first-page":"688","DOI":"10.1145\/1082036.1082043","volume":"52","author":"P Ferragina","year":"2005","unstructured":"Ferragina, P., Giancarlo, R., Manzini, G., Sciortino, M.: Boosting textual compression in optimal linear time. J. ACM 52(4), 688\u2013713 (2005)","journal-title":"J. ACM"},{"key":"1_CR13","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Manzini, G.: Opportunistic data structures with applications. In: FOCS 2000, pp. 390\u2013398. IEEE Computer Society (2000)","DOI":"10.1109\/SFCS.2000.892127"},{"key":"1_CR14","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, 552\u2013581 (2005)","journal-title":"J. ACM"},{"key":"1_CR15","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/j.tcs.2017.06.016","volume":"698","author":"T Gagie","year":"2017","unstructured":"Gagie, T., Manzini, G., Sir\u00e9n, J.: Wheeler graphs: a framework for BWT-based data structures. Theor. Comput. Sci. 698, 67\u201378 (2017)","journal-title":"Theor. Comput. Sci."},{"issue":"7","key":"1_CR16","doi-asserted-by":"publisher","first-page":"1537","DOI":"10.1016\/j.ejc.2012.03.016","volume":"33","author":"IM Gessel","year":"2012","unstructured":"Gessel, I.M., Restivo, A., Reutenauer, C.: A bijection between words and multisets of necklaces. Eur. J. Combin. 33(7), 1537\u20131546 (2012)","journal-title":"Eur. J. Combin."},{"issue":"2","key":"1_CR17","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0097-3165(93)90095-P","volume":"64","author":"IM Gessel","year":"1993","unstructured":"Gessel, I.M., Reutenauer, C.: Counting permutations with given cycle structure and descent set. J. Comb. Theory A 64(2), 189\u2013215 (1993)","journal-title":"J. Comb. Theory A"},{"key":"1_CR18","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1016\/j.tcs.2007.07.019","volume":"387","author":"R Giancarlo","year":"2007","unstructured":"Giancarlo, R., Restivo, A., Sciortino, M.: From first principles to the Burrows and Wheeler transform and beyond, via combinatorial optimization. Theor. Comput. Sci. 387, 236\u2013248 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"1_CR19","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 University Press, Cambridge (1997)"},{"issue":"10","key":"1_CR20","doi-asserted-by":"publisher","first-page":"1577","DOI":"10.1093\/bioinformatics\/btv024","volume":"31","author":"K Kimura","year":"2015","unstructured":"Kimura, K., Koike, A.: Ultrafast SNP analysis using the Burrows-Wheeler transform of short-read data. Bioinformatics 31(10), 1577\u20131583 (2015)","journal-title":"Bioinformatics"},{"issue":"2","key":"1_CR21","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"D Knuth","year":"1977","unstructured":"Knuth, D., Morris, J., Pratt, V.: Fast pattern matching in strings. SIAM J. Comput. 6(2), 323\u2013350 (1977)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"1_CR22","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1093\/bioinformatics\/btp698","volume":"26","author":"H Li","year":"2010","unstructured":"Li, H., Durbin, R.: Fast and accurate long-read alignment with Burrows-Wheeler transform. Bioinformatics 26(5), 589\u2013595 (2010)","journal-title":"Bioinformatics"},{"key":"1_CR23","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107326019","volume-title":"Algebraic Combinatorics on Words","author":"M Lothaire","year":"2002","unstructured":"Lothaire, M.: Algebraic Combinatorics on Words. Cambridge University Press, Cambridge (2002)"},{"key":"1_CR24","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107341005","volume-title":"Applied Combinatorics on Words (Encyclopedia of Mathematics and its Applications)","author":"M Lothaire","year":"2005","unstructured":"Lothaire, M.: Applied Combinatorics on Words (Encyclopedia of Mathematics and its Applications). Cambridge University Press, New York (2005)"},{"key":"1_CR25","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, A.I.: Genome-Scale Algorithm Design: Biological Sequence Analysis in the Era of High-Throughput Sequencing. Cambridge University Press, Cambridge (2015)"},{"issue":"3","key":"1_CR26","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-Wheeler Transform. Theor. Comput. Sci. 387(3), 298\u2013312 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"1_CR27","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/s00224-007-9078-6","volume":"42","author":"S Mantaci","year":"2008","unstructured":"Mantaci, S., Restivo, A., Rosone, G., Sciortino, M.: A new combinatorial approach to sequence comparison. Theory Comput. Syst. 42(3), 411\u2013429 (2008)","journal-title":"Theory Comput. Syst."},{"key":"1_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1007\/978-3-319-66396-8_21","volume-title":"Combinatorics on Words","author":"S Mantaci","year":"2017","unstructured":"Mantaci, S., Restivo, A., Rosone, G., Sciortino, M.: Burrows-wheeler transform and run-length enconding. In: Brlek, S., Dolce, F., Reutenauer, C., Vandomme, \u00c9. (eds.) WORDS 2017. LNCS, vol. 10432, pp. 228\u2013239. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-66396-8_21"},{"key":"1_CR29","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/j.tcs.2017.07.015","volume":"698","author":"S Mantaci","year":"2017","unstructured":"Mantaci, S., Restivo, A., Rosone, G., Sciortino, M., Versari, L.: Measuring the clustering effect of BWT via RLE. Theor. Comput. Sci. 698, 79\u201387 (2017)","journal-title":"Theor. Comput. Sci."},{"key":"1_CR30","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/S0020-0190(02)00512-4","volume":"86","author":"S Mantaci","year":"2003","unstructured":"Mantaci, S., Restivo, A., Sciortino, M.: Burrows-Wheeler transform and Sturmian words. Inf. Process. Lett. 86, 241\u2013246 (2003)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"1_CR31","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/j.ijar.2007.03.011","volume":"47","author":"S Mantaci","year":"2008","unstructured":"Mantaci, S., Restivo, A., Sciortino, M.: Distance measures for biological sequences: some recent approaches. Int. J. Approx. Reason. 47(1), 109\u2013124 (2008)","journal-title":"Int. J. Approx. Reason."},{"issue":"3","key":"1_CR32","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1145\/382780.382782","volume":"48","author":"G Manzini","year":"2001","unstructured":"Manzini, G.: An analysis of the Burrows-Wheeler transform. J. ACM 48(3), 407\u2013430 (2001)","journal-title":"J. ACM"},{"issue":"1","key":"1_CR33","doi-asserted-by":"publisher","first-page":"2","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. 39(1), 2 (2007)","journal-title":"ACM Comput. Surv."},{"key":"1_CR34","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781316588284","volume-title":"Compact Data Structures - A Practical Approach","author":"G Navarro","year":"2016","unstructured":"Navarro, G.: Compact Data Structures - A Practical Approach. Cambridge University Press, Cambridge (2016)"},{"key":"1_CR35","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/s11853-008-0017-0","volume":"2","author":"I Pak","year":"2008","unstructured":"Pak, I., Redlich, A.: Long cycles in abc-permutations. Funct. Anal. Other Math. 2, 87\u201392 (2008)","journal-title":"Funct. Anal. Other Math."},{"key":"1_CR36","unstructured":"Prezza, N., Pisanti, N., Sciortino, M., Rosone, G.: Detecting mutations by eBWT. In: 18th International Workshop on Algorithms in Bioinformatics, WABI 2018, Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018, to appear)"},{"issue":"30\u201332","key":"1_CR37","doi-asserted-by":"publisher","first-page":"3018","DOI":"10.1016\/j.tcs.2009.03.008","volume":"410","author":"A Restivo","year":"2009","unstructured":"Restivo, A., Rosone, G.: Burrows-Wheeler transform and palindromic richness. Theor. Comput. Sci. 410(30\u201332), 3018\u20133026 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"27","key":"1_CR38","doi-asserted-by":"publisher","first-page":"3019","DOI":"10.1016\/j.tcs.2010.11.040","volume":"412","author":"A Restivo","year":"2011","unstructured":"Restivo, A., Rosone, G.: Balancing and clustering of words in the Burrows-Wheeler transform. Theor. Comput. Sci. 412(27), 3019\u20133032 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"1_CR39","unstructured":"Reutenauer, C.: Mots de Lyndon g\u00e9n\u00e9ralis\u00e9s 54. S\u00e9m. Lothar. Combin. 16 p., B54h (2006)"},{"key":"1_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/978-3-642-39053-1_42","volume-title":"The Nature of Computation. Logic, Algorithms, Applications","author":"G Rosone","year":"2013","unstructured":"Rosone, G., Sciortino, M.: The Burrows-Wheeler transform between data compression and combinatorics on words. In: Bonizzoni, P., Brattka, V., L\u00f6we, B. (eds.) CiE 2013. LNCS, vol. 7921, pp. 353\u2013364. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-39053-1_42"},{"key":"1_CR41","doi-asserted-by":"crossref","unstructured":"Simpson, J., Puglisi, S.J.: Words with simple Burrows-Wheeler transforms. Electron. J. Comb. 15, Article ID R83 (2008)","DOI":"10.37236\/807"},{"issue":"4","key":"1_CR42","doi-asserted-by":"publisher","first-page":"742","DOI":"10.1016\/j.jtbi.2009.10.033","volume":"262","author":"L Yang","year":"2010","unstructured":"Yang, L., Zhang, X., Wang, T.: The Burrows-Wheeler similarity distribution between biological sequences based on Burrows-Wheeler transform. J. Theor. Biol. 262(4), 742\u2013749 (2010)","journal-title":"J. Theor. Biol."}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-98654-8_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,7]],"date-time":"2020-11-07T08:47:24Z","timestamp":1604738844000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-98654-8_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319986531","9783319986548"],"references-count":42,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-98654-8_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]}}}