Burrows–Wheeler transform
The Burrows–Wheeler transform (BWT, also called blocksorting compression) rearranges a character string into runs of similar characters. This is useful for compression, since it tends to be easy to compress a string that has runs of repeated characters by techniques such as movetofront transform and runlength encoding. More importantly, the transformation is reversible, without needing to store any additional data except the position of the first original character. The BWT is thus a "free" method of improving the efficiency of text compression algorithms, costing only some extra computation.
Contents
Description[edit]
The Burrows–Wheeler transform is an algorithm used to prepare data for use with data compression techniques such as bzip2, it was invented by Michael Burrows and David Wheeler in 1994 while Burrows was working at DEC Systems Research Center in Palo Alto, California. It is based on a previously unpublished transformation discovered by Wheeler in 1983; the algorithm can be implemented efficiently using a suffix array thus reaching linear time complexity.^{[1]}
When a character string is transformed by the BWT, the transformation permutes the order of the characters. If the original string had several substrings that occurred often, then the transformed string will have several places where a single character is repeated multiple times in a row.
For example:
Input  SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES 

Output  TEXYDST.E.IXIXIXXSSMPPS.B..E.S.EUSFXDIIOIIIT^{[2]} 
The output is easier to compress because it has many repeated characters. In this example the transformed string contains six runs of identical characters: XX, SS, PP, .., II, and III, which together make 13 out of the 44 characters.
Example[edit]
The transform is done by sorting all the circular shifts of a text in lexicographic order and by extracting the last column and the index of the original string in the set of sorted permutations of S.
Given an input string S = ^BANANA (step 1 in the table below), rotate it N times (step 2), where N = 8 is the length of the S string considering also the symbol ^ representing the start of the string and the red  character representing the 'EOF' pointer; these rotations, or circular shifts, are then sorted lexicographically (step 3). The output of the encoding phase is the last column L = BNN^AAA after step 3, and the index (0based) I of the row containing the original string S, in this case I = 6.
Transformation  

1. Input  2. All rotations 
3. Sort into lexical order 
4. Take the last column 
5. Output 
^BANANA

^BANANA ^BANANA A^BANAN NA^BANA ANA^BAN NANA^BA ANANA^B BANANA^ 
ANANA^B ANA^BAN A^BANAN BANANA^ NANA^BA NA^BANA ^BANANA ^BANANA 
ANANA^B ANA^BAN A^BANAN BANANA^ NANA^BA NA^BANA ^BANANA ^BANANA 
BNN^AAA

The following pseudocode gives a simple (though inefficient) way to calculate the BWT and its inverse, it assumes that the input string s
contains a special character 'EOF' which is the last character and occurs nowhere else in the text.
function BWT (string s) create a table, rows are all possible rotations of s sort rows alphabetically return (last column of the table)
function inverseBWT (string s) create empty table repeat length(s) times // first insert creates first column insert s as a column of table before first column of the table sort rows of the table alphabetically return (row that ends with the 'EOF' character)
Explanation[edit]
To understand why this creates moreeasilycompressible data, consider transforming a long English text frequently containing the word "the". Sorting the rotations of this text will group rotations starting with "he " together, and the last character of that rotation (which is also the character before the "he ") will usually be "t", so the result of the transform would contain a number of "t" characters along with the perhaps lesscommon exceptions (such as if it contains "Brahe ") mixed in. So it can be seen that the success of this transform depends upon one value having a high probability of occurring before a sequence, so that in general it needs fairly long samples (a few kilobytes at least) of appropriate data (such as text).
The remarkable thing about the BWT is not that it generates a more easily encoded output—an ordinary sort would do that—but that it is reversible, allowing the original document to be regenerated from the last column data.
The inverse can be understood this way. Take the final table in the BWT algorithm, and erase all but the last column. Given only this information, you can easily reconstruct the first column; the last column tells you all the characters in the text, so just sort these characters alphabetically to get the first column. Then, the first and last columns (of each row) together give you all pairs of successive characters in the document, where pairs are taken cyclically so that the last and first character form a pair. Sorting the list of pairs gives the first and second columns. Continuing in this manner, you can reconstruct the entire list. Then, the row with the "end of file" character at the end is the original text. Reversing the example above is done like this:
Inverse transformation  

Input  
BNN^AAA
 
Add 1  Sort 1  Add 2  Sort 2 
B
N
N
^
A
A

A

A
A
A
B
N
N
^


BA NA NA ^B AN AN ^ A 
AN AN A BA NA NA ^B ^ 
Add 3  Sort 3  Add 4  Sort 4 
BAN NAN NA ^BA ANA ANA ^B A^ 
ANA ANA A^ BAN NAN NA ^BA ^B 
BANA NANA NA^ ^BAN ANAN ANA ^BA A^B 
ANAN ANA A^B BANA NANA NA^ ^BAN ^BA 
Add 5  Sort 5  Add 6  Sort 6 
BANAN NANA NA^B ^BANA ANANA ANA^ ^BAN A^BA 
ANANA ANA^ A^BA BANAN NANA NA^B ^BANA ^BAN 
BANANA NANA^ NA^BA ^BANAN ANANA ANA^B ^BANA A^BAN 
ANANA ANA^B A^BAN BANANA NANA^ NA^BA ^BANAN ^BANA 
Add 7  Sort 7  Add 8  Sort 8 
BANANA NANA^B NA^BAN ^BANANA ANANA^ ANA^BA ^BANAN A^BANA 
ANANA^ ANA^BA A^BANA BANANA NANA^B NA^BAN ^BANANA ^BANAN 
BANANA^ NANA^BA NA^BANA ^BANANA ANANA^B ANA^BAN ^BANANA A^BANAN 
ANANA^B ANA^BAN A^BANAN BANANA^ NANA^BA NA^BANA ^BANANA ^BANANA 
Output  
^BANANA

Optimization[edit]
A number of optimizations can make these algorithms run more efficiently without changing the output. There is no need to represent the table in either the encoder or decoder. In the encoder, each row of the table can be represented by a single pointer into the strings, and the sort performed using the indices; some care must be taken to ensure that the sort does not exhibit bad worstcase behavior: Standard library sort functions are unlikely to be appropriate. In the decoder, there is also no need to store the table, and in fact no sort is needed at all. In time proportional to the alphabet size and string length, the decoded string may be generated one character at a time from right to left. A "character" in the algorithm can be a byte, or a bit, or any other convenient size.
One may also make the observation that mathematically, the encoded string can be computed as a simple modification of the suffix array, and suffix arrays can be computed with linear time and memory; the BWT can be defined with regards to the suffix array SA of text T as (1based indexing):
^{[3]}
There is no need to have an actual 'EOF' character. Instead, a pointer can be used that remembers where in a string the 'EOF' would be if it existed. In this approach, the output of the BWT must include both the transformed string, and the final value of the pointer; that means the BWT does expand its input slightly. The inverse transform then shrinks it back down to the original size: it is given a string and a pointer, and returns just a string.
A complete description of the algorithms can be found in Burrows and Wheeler's paper^{[4]}^{[citation needed]}, or in a number of online sources.
Bijective variant[edit]
This section may require cleanup to meet Wikipedia's quality standards. The specific problem is: This section appears to contain two subsequent explanations. (March 2017) (Learn how and when to remove this template message) 
Since any rotation of the input string will lead to the same transformed string, the BWT cannot be inverted without adding an EOF marker to the end of the input or doing something equivalent, making it possible to distinguish the input string from all its rotations. Increasing the size of the alphabet (by appending the EOF character) makes later compression steps awkward.
There is a bijective version of the transform, by which the transformed string uniquely identifies the original, and the two have the same length and contain exactly the same characters, just in a different order.^{[5]}^{[6]}
The bijective transform is computed by factoring the input into a nonincreasing sequence of Lyndon words; such a factorization exists and is unique by the Chen–Fox–Lyndon theorem,^{[7]} and may be found in linear time;^{[8]} the algorithm sorts the rotations of all the words; as in the Burrows–Wheeler transform, this produces a sorted sequence of n strings. The transformed string is then obtained by picking the final character of each string in this sorted list; the one important caveat here is that strings of different lengths are not ordered in the usual way; the two strings are repeated forever, and the infinite repeats are sorted. For example, "ORO" precedes "OR" because "OROORO..." precedes "OROROR...".
For example, the text "^BANANA" is transformed into "ANNBAA^" through these steps (the red  character indicates the EOF pointer) in the original string. The EOF character is unneeded in the bijective transform, so it is dropped during the transform and readded to its proper place in the file.
The string is broken into Lyndon words so the words in the sequence are decreasing using the comparison method above. (Note that we're sorting '^' as succeeding other characters.) "^BANANA" becomes (^) (B) (AN) (AN) (A).
Bijective transformation  

Input  All rotations 
Sorted alphabetically  Last column of rotated Lyndon word 
Output 
^BANANA

^^^^^^^^ (^) BBBBBBBB (B) ANANANAN... (AN) NANANANA... (NA) ANANANAN... (AN) NANANANA... (NA) AAAAAAAA... (A) 
AAAAAAAA... (A) ANANANAN... (AN) ANANANAN... (AN) BBBBBBBB... (B) NANANANA... (NA) NANANANA... (NA) ^^^^^^^^... (^) 
AAAAAAAA... (A) ANANANAN... (AN) ANANANAN... (AN) BBBBBBBB... (B) NANANANA... (NA) NANANANA... (NA) ^^^^^^^^... (^) 
ANNBAA^

Inverse bijective transform  

Input  
ANNBAA^  
Add 1  Sort 1  Add 2  Sort 2 
A N N B A A ^ 
A A A B N N ^ 
AA NA NA BB AN AN ^^ 
AA AN AN BB NA NA ^^ 
Add 3  Sort 3  Add 4  Sort 4 
AAA NAN NAN BBB ANA ANA ^^^ 
AAA ANA ANA BBB NAN NAN ^^^ 
AAAA NANA NANA BBBB ANAN ANAN ^^^^ 
AAAA ANAN ANAN BBBB NANA NANA ^^^^ 
Output  
^BANANA 
Up until the last step, the process is identical to the inverse BurrowsWheeler process, but here it will not necessarily give rotations of a single sequence; it instead gives rotations of Lyndon words (which will start to repeat as the process is continued). Here, we can see (repetitions of) four distinct Lyndon words: (A), (AN) (twice), (B), and (^). (NANA... doesn't represent a distinct word, as it is a cycle of ANAN....) At this point, these words are sorted into reverse order: (^), (B), (AN), (AN), (A). These are then concatenated to get
 ^BANANA
The BurrowsWheeler transform can indeed be viewed as a special case of this bijective transform; instead of the traditional introduction of a new letter from outside our alphabet to denote the end of the string, we can introduce a new letter that compares as preceding all existing letters that is put at the beginning of the string; the whole string is now a Lyndon word, and running it through the bijective process will therefore result in a transformed result that, when inverted, gives back the Lyndon word, with no need for reassembling at the end.
Relatedly, the transformed text will only differ from the result of BWT by one character per Lyndon word; for example, if the input is decomposed into six Lyndon words, the output will only differ in six characters. For example, applying the bijective transform gives:
Input  SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES 

Lyndon words  SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES 
Output  STEYDST.E.IXXIIXXSMPPXS.B..EE..SUSFXDIOIIIIT 
The bijective transform includes eight runs of identical characters; these runs are, in order: XX, II, XX, PP, .., EE, .., and IIII.
In total, 18 characters are used in these runs.
Dynamic Burrows–Wheeler transform[edit]
When a text is edited, its Burrows–Wheeler transform will change. Salson et al.^{[9]} propose an algorithm that deduces the Burrows–Wheeler transform of an edited text from that of the original text, doing a limited number of local reorderings in the original Burrows–Wheeler transform, which can be faster than constructing the Burrows–Wheeler transform of the edited text directly.
Sample implementation[edit]
This Python implementation sacrifices speed for simplicity: the program is short, but takes more than the linear time that would be desired in a practical implementation.
Using the STX/ETX control codes to mark the start and end of the text, and using s[i:] + s[:i]
to construct the i
th rotation of s
, the forward transform takes the last character of each of the sorted rows:
def bwt(s):
"""Apply BurrowsWheeler transform to input string."""
assert "\002" not in s and "\003" not in s, "Input string cannot contain STX and ETX characters"
s = "\002" + s + "\003" # Add start and end of text marker
table = sorted(s[i:] + s[:i] for i in range(len(s))) # Table of rotations of string
last_column = [row[1:] for row in table] # Last characters of each row
return "".join(last_column) # Convert list of characters into string
The inverse transform repeatedly inserts r
as the left column of the table and sorts the table. After the whole table is built, it returns the row that ends with ETX, minus the STX and ETX.
def ibwt(r):
"""Apply inverse BurrowsWheeler transform."""
table = [""] * len(r) # Make empty table
for i in range(len(r)):
table = sorted(r[i] + table[i] for i in range(len(r))) # Add a column of r
s = [row for row in table if row.endswith("\003")][0] # Find the correct row (ending in ETX)
return s.rstrip("\003").strip("\002") # Get rid of start and end markers
Here is another, more efficient method using the new LTS 'League Table Sort' algorithm, using weights instead of sorting; this is R code. The code below produces the weighting matrix for demonstration, but it could easily be transformed to produce the weights directly as the columns sums. See the External link: League Table Sort. for fully functional java code and the way it could be up scaled for parallel processing.
generateWeightMatrix = function(inputStr1,zero = 1){
inputStr1 = paste(inputStr1,'!',sep="")
inputStr = paste(inputStr1,inputStr1,sep="")
strLen = nchar(inputStr1)
strLen1 = strLen  1
W = matrix(0,strLen,strLen)
arr = strsplit(inputStr, "")[[1]]
for(i in 1:strLen1){W[i,strLen] = 1;W[strLen,i] = 1}
###
for(j in strLen1:1)
{
for (i in 1:strLen1)
{
aj = arr[j]
ai = arr[i]
if(aj == ai){if(zero == 1){W[i,j] = W[i+1,j + 1]}}else{
if(aj>ai){flag = 1}else{flag = 1}
W[i,j] = flag
}
}
}
###
diag(W) = 0
#W[lower.tri(W)] < 0#;W = W t(W)
W = as.data.frame(W)
rownames(W) = paste(1:strLen,arr[1:strLen],sep = '')
names(W) = arr[1:strLen] #paste(1:strLen,arr[1:strLen],sep = '')
W
}
##################
getIndex = function(size, buckets, strEncoded, indices){
for (i in 1:size){
buckets[strEncoded[i]] = buckets[strEncoded[i]] + 1
indices[buckets[strEncoded[i]]] = i
}
indices
}
#####################
# reverse BWT process to test the above code
bwt_decode = function(strEncoded)
{
############### transform to array of bite code
#strEncoded = strsplit(strEncoded,'')
strEncoded = utf8ToInt(strEncoded)
size = length(strEncoded)
###############
F = rep(0,size)
strDecoded = rep(0, size)
buckets = rep(0,256)
indices = rep(0,size)
###############
### get frequencies of ascii codes
for (i in 1:(size)){buckets[strEncoded[i]] = buckets[strEncoded[i]] + 1}
### sort input array
F = sort(strEncoded)
### accumulated frequencies
j = 1
for (i in 1:256)
{
while (i > F[j] & j < size)
{
j = j + 1
}
buckets[i] = j1
}
###
indices = getIndex(size, buckets, strEncoded, indices)
j = 1
for (i in 1:size)
{
strDecoded[i] = strEncoded[j];
j = indices[j];
}
g = grep('33', strDecoded)
strDecoded1 = intToUtf8(strDecoded)
strDecoded2 = paste(substr(strDecoded1,g+1,size),substr(strDecoded1,1,g1),sep = '')
strDecoded2
}
#############################################
# example:
inputString = 'SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES'
inputString = 'SSSMMMMDDXXXTTTTT....BBBEEE000'
#inputString = paste(inputString,inputString, sep = '')
#nputString = paste(inputString,inputString, sep = '')
n = nchar(inputString)
v = rep(1,n+1)
# generae the weights matrix W
d = generateWeightMatrix(inputString,1)
W = as.matrix(d)
W;det(W)
# calculate weights
result = t(W)%*%v
t(result)
# to calculate the position of each character in the new string
# calculate (result + n)/2
# or
# calculate output
S = strsplit(paste('!',inputString,sep = ""),"")
d1 = data.frame(unlist(S),as.numeric(result))
names(d1) = c('S', 'w')
outputString = paste(as.character(as.factor(d1[order(d1$w),][,1])),collapse = '')
outputString
bwt_decode(outputString);inputString
# zero cell are the off diagonal zero cells
zeroCells = generateWeightMatrix(inputString,0)
zeroCells
Here is a third one, more efficient and very simple method, it increases the speed greatly when decoding lengthy strings. Although it needs an origin index list generated by bwt.
def bwt(s):
"""Apply BurrowsWheeler transform to input string. Not indicated by a unique byte but use index list"""
# Table of rotations of string
table = [s[i:] + s[:i] for i in range(len(s))]
# Sorted table
table_sorted = table[:]
table_sorted.sort()
# Get index list of ((every string in sorted table)'s next string in unsorted table)'s index in sorted table
indexlist = []
for t in table_sorted:
index1 = table.index(t)
index1 = index1+1 if index1 < len(s)1 else 0
index2 = table_sorted.index(table[index1])
indexlist.append(index2)
# Join last characters of each row into string
r = ''.join([row[1] for row in table_sorted])
return r, indexlist
def ibwt(r,indexlist):
"""Inverse BurrowsWheeler transform. Not indicated by a unique byte but use index list"""
s = ''
x = indexlist[0]
for _ in r:
s = s + r[x]
x = indexlist[x]
return s
BWT in bioinformatics[edit]
The advent of nextgeneration sequencing (NGS) techniques at the end of the 2000s decade has led to another application of the Burrows–Wheeler transformation. In NGS, DNA is fragmented into small pieces, of which the first few bases are sequenced, yielding several millions of "reads", each 30 to 500 base pairs ("DNA characters") long. In many experiments, e.g., in ChIPSeq, the task is now to align these reads to a reference genome, i.e., to the known, nearly complete sequence of the organism in question (which may be up to several billion base pairs long). A number of alignment programs, specialized for this task, were published, which initially relied on hashing (e.g., Eland, SOAP,^{[10]} or Maq^{[11]}). In an effort to reduce the memory requirement for sequence alignment, several alignment programs were developed (Bowtie,^{[12]} BWA,^{[13]} and SOAP2^{[14]}) that use the Burrows–Wheeler transform.
References[edit]
 ^ Burrows, Michael; Wheeler, David J. (1994), A block sorting lossless data compression algorithm, Technical Report 124, Digital Equipment Corporation
 ^ "adrienmogenet/scalabwt". GitHub. Retrieved 19 April 2018.
 ^ Simpson, Jared T.; Durbin, Richard (20100615). "Efficient construction of an assembly string graph using the FMindex". Bioinformatics. 26 (12): i367–i373. doi:10.1093/bioinformatics/btq217. ISSN 13674803. PMC 2881401. PMID 20529929.
 ^ Kutylowski, Miroslaw; Pacholski, Leszek (19990818). Mathematical Foundations of Computer Science 1999: 24th International Symposium, MFCS'99 Szklarska Poreba, Poland, September 610, 1999 Proceedings. Springer Science & Business Media. ISBN 9783540664086.
 ^ Gil, J.; Scott, D. A. (2009), A bijective string sorting transform (PDF)
 ^ Kufleitner, Manfred (2009), "On bijective variants of the BurrowsWheeler transform", in Holub, Jan; Žďárek, Jan (eds.), Prague Stringology Conference, pp. 65–69, arXiv:0908.0239, Bibcode:2009arXiv0908.0239K.
 ^ *Lothaire, M. (1997), Combinatorics on words, Encyclopedia of Mathematics and Its Applications, 17, Perrin, D.; Reutenauer, C.; Berstel, J.; Pin, J. E.; Pirillo, G.; Foata, D.; Sakarovitch, J.; Simon, I.; Schützenberger, M. P.; Choffrut, C.; Cori, R.; Lyndon, Roger; Rota, GianCarlo. Foreword by Roger Lyndon (2nd ed.), Cambridge University Press, p. 67, ISBN 9780521599245, Zbl 0874.20040
 ^ Duval, JeanPierre (1983), "Factorizing words over an ordered alphabet", Journal of Algorithms, 4 (4): 363–381, doi:10.1016/01966774(83)900172, ISSN 01966774, Zbl 0532.68061.
 ^ Salson M, Lecroq T, Léonard M, Mouchard L (2009). "A FourStage Algorithm for Updating a Burrows–Wheeler Transform". Theoretical Computer Science. 410 (43): 4350–4359. doi:10.1016/j.tcs.2009.07.016.
 ^ Li R; et al. (2008). "SOAP: short oligonucleotide alignment program". Bioinformatics. 24 (5): 713–714. doi:10.1093/bioinformatics/btn025. PMID 18227114.
 ^ Li H, Ruan J, Durbin R (20080819). "Mapping short DNA sequencing reads and calling variants using mapping quality scores". Genome Research. 18 (11): 1851–1858. doi:10.1101/gr.078212.108. PMC 2577856. PMID 18714091.
 ^ Langmead B, Trapnell C, Pop M, Salzberg SL (2009). "Ultrafast and memoryefficient alignment of short DNA sequences to the human genome". Genome Biology. 10 (3): R25. doi:10.1186/gb2009103r25. PMC 2690996. PMID 19261174.
 ^ Li H, Durbin R (2009). "Fast and accurate short read alignment with Burrows–Wheeler Transform". Bioinformatics. 25 (14): 1754–1760. doi:10.1093/bioinformatics/btp324. PMC 2705234. PMID 19451168.
 ^ Li R; et al. (2009). "SOAP2: an improved ultrafast tool for short read alignment". Bioinformatics. 25 (15): 1966–1967. doi:10.1093/bioinformatics/btp336. PMID 19497933.
External links[edit]
 Article by Mark Nelson on the BWT
 A Bijective StringSorting Transform, by Gil and Scott
 Yuta's openbwtv1.5.zip contains source code for various BWT routines including BWTS for bijective version
 On Bijective Variants of the Burrows–Wheeler Transform, by Kufleitner
 Blog post and project page for an opensource compression program and library based on the Burrows–Wheeler algorithm
 MIT open courseware lecture on BWT (Foundations of Computational and Systems Biology)
 League Table Sort or The Weighting algorithm to BWT ,by Abderrahim Hechachena