{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T02:48:10Z","timestamp":1764557290438,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":45,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642390524"},{"type":"electronic","value":"9783642390531"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-39053-1_42","type":"book-chapter","created":{"date-parts":[[2013,6,3]],"date-time":"2013-06-03T04:28:12Z","timestamp":1370233692000},"page":"353-364","source":"Crossref","is-referenced-by-count":9,"title":["The Burrows-Wheeler Transform between Data Compression and Combinatorics on Words"],"prefix":"10.1007","author":[{"given":"Giovanna","family":"Rosone","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marinella","family":"Sciortino","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"42_CR1","doi-asserted-by":"crossref","unstructured":"Adjeroh, D., Bell, T., Mukherjee, A.: The Burrows-Wheeler Transform: Data Compression, Suffix Arrays, and Pattern Matching, 1st edn. Springer Publishing Company, Incorporated (2008)","DOI":"10.1007\/978-0-387-78909-5"},{"key":"42_CR2","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/j.tcs.2012.02.002","volume":"483","author":"M.J. Bauer","year":"2013","unstructured":"Bauer, M.J., Cox, A.J., Rosone, G.: Lightweight algorithms for constructing and inverting the BWT of string collections. Theoret. Comput. Sci.\u00a0483, 134\u2013148 (2013)","journal-title":"Theoret. Comput. Sci."},{"key":"42_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/978-3-642-38771-5_13","volume-title":"DLT 2013","author":"S. Bonomo","year":"2013","unstructured":"Bonomo, S., Mantaci, S., Restivo, A., Rosone, G., Sciortino, M.: Suffixes, Conjugates and Lyndon words. In: B\u00e9al, M.-P., Carton, O. (eds.) DLT 2013. LNCS, vol.\u00a07907, pp. 131\u2013142. Springer, Heidelberg (2013)"},{"key":"42_CR4","unstructured":"Burrows, M., Wheeler, D.J.: A block sorting data compression algorithm. Technical report, DIGITAL System Research Center (1994)"},{"issue":"7","key":"42_CR5","doi-asserted-by":"publisher","first-page":"1551","DOI":"10.1109\/TIT.2004.830771","volume":"50","author":"H. Cai","year":"2004","unstructured":"Cai, H., Kulkarni, S.R., Verd\u00fa, S.: Universal entropy estimation via block sorting. IEEE Transactions on Information Theory\u00a050(7), 1551\u20131561 (2004)","journal-title":"IEEE Transactions on Information Theory"},{"issue":"11","key":"42_CR6","doi-asserted-by":"publisher","first-page":"1415","DOI":"10.1093\/bioinformatics\/bts173","volume":"28","author":"A.J. Cox","year":"2012","unstructured":"Cox, A.J., Bauer, M.J., Jakobi, T., Rosone, G.: Large-scale compression of genomic sequence databases with the Burrows-Wheeler transform. Bioinformatics\u00a028(11), 1415\u20131419 (2012)","journal-title":"Bioinformatics"},{"key":"42_CR7","series-title":"LNBI","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1007\/978-3-642-33122-0_17","volume-title":"Algorithms in Bioinformatics","author":"A.J. 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 (LNBI), vol.\u00a07534, pp. 214\u2013224. Springer, Heidelberg (2012)"},{"key":"42_CR8","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. Theoret. Comput. Sci.\u00a0332, 567\u2013572 (2005)","journal-title":"Theoret. Comput. Sci."},{"key":"42_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-63246-8_15","volume-title":"Structures in Logic and Computer Science","author":"A. de Luca","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.\u00a01261, Springer, Heidelberg (1997)"},{"issue":"2","key":"42_CR10","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1016\/0304-3975(94)00035-H","volume":"136","author":"A. de Luca","year":"1994","unstructured":"de Luca, A., Mignosi, F.: Some combinatorial properties of sturmian words. Theoret. Comput. Sci.\u00a0136(2), 361\u2013385 (1994)","journal-title":"Theoret. Comput. Sci."},{"issue":"1-2","key":"42_CR11","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1016\/S0304-3975(99)00320-5","volume":"255","author":"X. Droubay","year":"2001","unstructured":"Droubay, X., Justin, J., Pirillo, G.: Episturmian words and some constructions of de Luca and Rauzy. Theoret. Comput. Sci.\u00a0255(1-2), 539\u2013553 (2001)","journal-title":"Theoret. Comput. Sci."},{"issue":"5","key":"42_CR12","doi-asserted-by":"publisher","first-page":"1061","DOI":"10.1109\/18.995542","volume":"48","author":"M. Effros","year":"2002","unstructured":"Effros, M., Visweswariah, K., Kulkarni, S.R., Verd\u00fa, S.: Universal lossless source coding with the Burrows Wheeler Transform. IEEE Transactions on Information Theory\u00a048(5), 1061\u20131081 (2002)","journal-title":"IEEE Transactions on Information Theory"},{"key":"42_CR13","unstructured":"Ferenczi, S., Zamboni, L.Q.: Clustering Words and Interval Exchanges. Journal of Integer Sequences\u00a016(2), Article 13.2.1 (2013)"},{"issue":"3","key":"42_CR14","doi-asserted-by":"publisher","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\u00a063(3), 707\u2013730 (2012)","journal-title":"Algorithmica"},{"issue":"4","key":"42_CR15","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\u00a052(4), 688\u2013713 (2005)","journal-title":"J. ACM"},{"key":"42_CR16","unstructured":"Ferragina, P., Manzini, G.: Opportunistic data structures with applications. In: FOCS 2000, pp. 390\u2013398. IEEE Computer Society (2000)"},{"key":"42_CR17","unstructured":"Ferragina, P., Manzini, G.: An experimental study of an opportunistic index. In: SODA 2001, pp. 269\u2013278. SIAM (2001)"},{"key":"42_CR18","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\u00a052, 552\u2013581 (2005)","journal-title":"J. ACM"},{"key":"42_CR19","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/s00453-010-9437-6","volume":"61","author":"P. Ferragina","year":"2011","unstructured":"Ferragina, P., Nitto, I., Venturini, R.: On optimally partitioning a text to improve its compression. Algorithmica\u00a061, 51\u201374 (2011)","journal-title":"Algorithmica"},{"issue":"2","key":"42_CR20","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0097-3165(93)90095-P","volume":"64","author":"I.M. Gessel","year":"1993","unstructured":"Gessel, I.M., Reutenauer, C.: Counting permutations with given cycle structure and descent set. J. Combin. Theory Ser. A\u00a064(2), 189\u2013215 (1993)","journal-title":"J. Combin. Theory Ser. A"},{"key":"42_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/3-540-44888-8_10","volume-title":"Combinatorial Pattern Matching","author":"R. Giancarlo","year":"2003","unstructured":"Giancarlo, R., Sciortino, M.: Optimal partitions of strings: A new class of Burrows-Wheeler compression algorithms. In: Baeza-Yates, R., Ch\u00e1vez, E., Crochemore, M. (eds.) CPM 2003. LNCS, vol.\u00a02676, pp. 129\u2013143. Springer, Heidelberg (2003)"},{"key":"42_CR22","unstructured":"Gil, J.Y., Scott, D.A.: A bijective string sorting transform. CoRR (2012); abs\/1201.3077"},{"key":"42_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/978-3-642-31265-6_21","volume-title":"Combinatorial Pattern Matching","author":"W.-K. Hon","year":"2012","unstructured":"Hon, W.-K., Ku, T.-H., Lu, C.-H., Shah, R., Thankachan, S.V.: Efficient Algorithm for Circular Burrows-Wheeler Transform. In: K\u00e4rkk\u00e4inen, J., Stoye, J. (eds.) CPM 2012. LNCS, vol.\u00a07354, pp. 257\u2013268. Springer, Heidelberg (2012)"},{"issue":"3","key":"42_CR24","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/j.tcs.2007.07.020","volume":"387","author":"H. Kaplan","year":"2007","unstructured":"Kaplan, H., Landau, S., Verbin, E.: A simpler analysis of Burrows-Wheeler-based compression. Theoret. Comput. Sci.\u00a0387(3), 220\u2013235 (2007)","journal-title":"Theoret. Comput. Sci."},{"key":"42_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/978-3-540-73437-6_13","volume-title":"Combinatorial Pattern Matching","author":"H. Kaplan","year":"2007","unstructured":"Kaplan, H., Verbin, E.: Most burrows-wheeler based compressors are not optimal. In: Ma, B., Zhang, K. (eds.) CPM 2007. LNCS, vol.\u00a04580, pp. 107\u2013118. Springer, Heidelberg (2007)"},{"issue":"2","key":"42_CR26","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 Journal on Computing\u00a06(2), 323\u2013350 (1977)","journal-title":"SIAM Journal on Computing"},{"key":"42_CR27","unstructured":"Kufleitner, M.: On bijective variants of the Burrows-Wheeler transform, pp. 65\u201379 (2009)"},{"key":"42_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/978-3-642-20712-9_30","volume-title":"Computer Science \u2013 Theory and Applications","author":"K.M. Likhomanov","year":"2011","unstructured":"Likhomanov, K.M., Shur, A.M.: Two combinatorial criteria for BWT images. In: Kulikov, A., Vereshchagin, N. (eds.) CSR 2011. LNCS, vol.\u00a06651, pp. 385\u2013396. Springer, Heidelberg (2011)"},{"key":"42_CR29","doi-asserted-by":"crossref","unstructured":"Lothaire, M.: Algebraic Combinatorics on Words. Cambridge Univ. Press (2002)","DOI":"10.1017\/CBO9781107326019"},{"key":"42_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1007\/11496656_16","volume-title":"Combinatorial Pattern Matching","author":"S. Mantaci","year":"2005","unstructured":"Mantaci, S., Restivo, A., Rosone, G., Sciortino, M.: An Extension of the Burrows Wheeler Transform and Applications to Sequence Comparison and Data Compression. In: Apostolico, A., Crochemore, M., Park, K. (eds.) CPM 2005. LNCS, vol.\u00a03537, pp. 178\u2013189. Springer, Heidelberg (2005)"},{"issue":"3","key":"42_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-Wheeler Transform. Theoret. Comput. Sci.\u00a0387(3), 298\u2013312 (2007)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"42_CR32","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.\u00a042(3), 411\u2013429 (2008)","journal-title":"Theory Comput. Syst."},{"key":"42_CR33","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. Information Processing Letters\u00a086, 241\u2013246 (2003)","journal-title":"Information Processing Letters"},{"issue":"1","key":"42_CR34","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. Reasoning\u00a047(1), 109\u2013124 (2008)","journal-title":"Int. J. Approx. Reasoning"},{"issue":"3","key":"42_CR35","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\u00a048(3), 407\u2013430 (2001)","journal-title":"J. ACM"},{"key":"42_CR36","doi-asserted-by":"crossref","unstructured":"Ng, K.-H., Ho, C.-K., Phon-Amnuaisuk, S.: A hybrid distance measure for clustering expressed sequence tags originating from the same gene family. PLoS ONE\u00a07(10) (2012)","DOI":"10.1371\/journal.pone.0047216"},{"issue":"1","key":"42_CR37","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/S0304-3975(03)00397-9","volume":"310","author":"O. Jenkinson","year":"2004","unstructured":"Jenkinson, O., Zamboni, L.Q.: Characterisations of balanced words via orderings. Theoret. Comput. Sci.\u00a0310(1), 247\u2013271 (2004)","journal-title":"Theoret. Comput. Sci."},{"key":"42_CR38","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. Functional Analysis and Other Mathematics\u00a02, 87\u201392 (2008)","journal-title":"Functional Analysis and Other Mathematics"},{"issue":"30-32","key":"42_CR39","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. Theoret. Comput. Sci.\u00a0410(30-32), 3018\u20133026 (2009)","journal-title":"Theoret. Comput. Sci."},{"issue":"27","key":"42_CR40","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. Theoret. Comput. Sci.\u00a0412(27), 3019\u20133032 (2011)","journal-title":"Theoret. Comput. Sci."},{"key":"42_CR41","doi-asserted-by":"crossref","unstructured":"Simpson, J., Puglisi, S.J.: Words with simple Burrows-Wheeler transforms. Electronic Journal of Combinatorics\u00a015 article R83 (2008)","DOI":"10.37236\/807"},{"issue":"12","key":"42_CR42","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1093\/bioinformatics\/btq217","volume":"26","author":"J.T. Simpson","year":"2010","unstructured":"Simpson, J.T., Durbin, R.: Efficient construction of an assembly string graph using the FM-index. Bioinformatics\u00a026(12), i367\u2013i373 (2010)","journal-title":"Bioinformatics"},{"issue":"4","key":"42_CR43","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1093\/bioinformatics\/btg005","volume":"19","author":"S. Vinga","year":"2003","unstructured":"Vinga, S., Almeida, J.: Alignment-free sequence comparison a review. Bioinformatics\u00a019(4), 513\u2013523 (2003)","journal-title":"Bioinformatics"},{"key":"42_CR44","unstructured":"Witten, I.H., Moffat, A., Bell, T.C.: Managing Gigabytes: Compressing and Indexing Documents and Images, 2nd edn. Morgan Kaufmann (1999)"},{"issue":"4","key":"42_CR45","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. Journal of Theoretical Biology\u00a0262(4), 742\u2013749 (2010)","journal-title":"Journal of Theoretical Biology"}],"container-title":["Lecture Notes in Computer Science","The Nature of Computation. Logic, Algorithms, Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-39053-1_42","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,20]],"date-time":"2023-01-20T07:55:14Z","timestamp":1674201314000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-39053-1_42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642390524","9783642390531"],"references-count":45,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-39053-1_42","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}