Computing the Burrows–Wheeler transform in place and in small space

Adjeroh, 2008 Aho, 1974 Belazzougui, 2014, Linear time construction of compressed text indices in compact space, 148 Burrows, 1994 Chan, 2010, Comparison-based time–space lower bounds for selection, ACM Trans. Algorithms, 6, 1, 10.1145/1721837.1721842 Crochemore, 2013, A constant-space comparison-based algorithm for computing the Burrows–Wheeler transform, 74 Dobkin, 1981, Optimal time minimal space selection algorithms, J. ACM, 28, 454, 10.1145/322261.322264 Ferragina, 2005, Indexing compressed text, J. ACM, 52, 552, 10.1145/1082036.1082039 Franceschini, 2007, In-place suffix sorting, automata, languages and programming, 533 Grossi, 2003, High-order entropy-compressed text indexes, 841 Grossi, 2012, The wavelet trie: maintaining an indexed sequence of strings in compressed space, 203 Hoare, 1961, Algorithm 65: find, Commun. ACM, 4, 321 Hon, 2007, A space and time efficient algorithm for constructing compressed suffix arrays, Algorithmica, 48, 23, 10.1007/s00453-006-1228-8 Hon, 2009, Breaking a time-and-space barrier in constructing full-text indices, SIAM J. Comput., 38, 2162, 10.1137/070685373 Kärkkäinen, 2007, Fast BWT in small space by blockwise suffix sorting, Theor. Comput. Sci., 387, 249, 10.1016/j.tcs.2007.07.018 Lam, 2009, High throughput short read alignment via bi-directional BWT, 31 Lam, 2015, Compressed indexing and local alignment of DNA, Bioinformatics, 24, 791, 10.1093/bioinformatics/btn032 Li, 2010, Fast and accurate long-read alignment with Burrows–Wheeler transform, Bioinformatics, 26, 589, 10.1093/bioinformatics/btp698 Langmead, 2009, Ultrafast and memory-efficient alignment of short DNA sequences to the human genome, Genome Biol., 10, R25, 10.1186/gb-2009-10-3-r25 Manber, 1993, Suffix arrays: a new method for on-line string searches, SIAM J. Comput., 22, 935, 10.1137/0222058 Manzini, 2001, An analysis of the Burrows–Wheeler transform, J. ACM, 48, 407, 10.1145/382780.382782 Munro, 1996, Tables, vol. 1180, 37 Munro, 1996, Selection from read-only memory and sorting with minimum data movement, Theor. Comput. Sci., 165, 311, 10.1016/0304-3975(95)00225-1 Na, 2007, Alphabet-independent linear-time construction of compressed suffix arrays using o(nlog⁡n)-bit working space, Theor. Comput. Sci., 385, 127, 10.1016/j.tcs.2007.05.030 Navarro, 2014, Wavelet trees for all, J. Discrete Algorithms, 25, 2, 10.1016/j.jda.2013.07.004 Navarro, 2013, Optimal dynamic sequence representations, 865 Okanohara, 2009, A linear-time Burrows–Wheeler transform using induced sorting, vol. 5721, 90 Raman, 1999, Improved upper bounds for time–space trade-offs for selection, Nord. J. Comput., 6, 162 Salson, 2009, A four-stage algorithm for updating a Burrows–Wheeler transform, Theor. Comput. Sci., 410, 4350, 10.1016/j.tcs.2009.07.016