A Block-sorting Lossless Data Compression Algorithm

By M. Burrows, D. J. Wheeler D I G I T A L, R. W. Taylor, D. Wheeler, David Wheeler. 1994

Subfields: Information Theory, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Information Theory

In Algorithms & Complexity

Citations in the corpus

Autoregressive Search Engines: Generating Substrings as Document Identifiers (2022, methodology): “Inter-nally, the FM-index relies on the Burrows-Wheeler Transform (Burrows and Wheeler, 1994), or BWT , an invertible transformation that permutes a string to make it easier to compress, deﬁned as follows: all the rotations of the string are sorted lexicograph-ically and laid out in a matrix; the…”
Aligning short sequencing reads with Bowtie (2010, methodology): “The Bowtie index is a refinement of the FM Index (Ferragina and Manzini 2000), which in turn uses the Burrows-Wheeler Transform (Burrows and Wheeler 1994).”
Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications (2001, methodology): “The block-sorting algorithm [4] is a text compression method with good balance of compression ratio and speed.”
De novo assembly of bacterial transcriptomes from RNA-seq data (2015, unknown): “In the first stage of de novo transcriptome assembly, Rockhopper 2 maintains two data structures, a de Bruijn graph [16,17] and a Burrows-Wheeler index [18,19].”
XMill: an efficient compressor for XML data (2000, methodology): “A more recent method is block-sorting compression described in [3], which is used in bzip.”
Data compression algorithms for energy-constrained devices in delay tolerant networks (2006, background): “1 Burrows–Wheeler Transform The Burrows–Wheeler Transform [7] (BWT) is a reversible transform central to the bzip2 compression algorithm.”
Indexing compressed text (2005, methodology): “1992] and two compressors: the Burrows–Wheeler Transform [Burrows and Wheeler 1994] and the LZ78 algorithm [Ziv and Lempel 1978].”
Indexing Compressed Text (2003, methodology): “From the many existing compression techniques, we will review those that are relevant to our topic, especially the Burrows-Wheeler Transform [18].”
Fast and sensitive taxonomic classification for metagenomics with Kaiju (2016, methodology): “Kaiju’s underlying sequence comparison algorithm uses the Burrows–Wheeler transform (BWT) of the protein database, which enables exact string matching in time proportional to the length of the query, to achieve a high classiﬁcation speed.”
Faster and More Accurate Sequence Alignment with SNAP (2011, methodology): “BWT-based aligners, including Bowtie, SOAP2, BWA, and BWA-SW [6, 10, 7, 8], align reads against a preﬁx trie of the reference genome, which is represented compactly using the Burrows-Wheeler transform [4].”
Online algorithms: a survey (2003, methodology): “Recently, list update techniques have been applied very successfully in the development of data compression algorithms [8, 28, 34].”
A survey of sequence alignment algorithms for next-generation sequencing (2010, background): “Wheeler Transform (BWT) [40], we focus on prefix trie which is the trie of the reverse string.”
Computational methods for transcriptome annotation and quantification using RNA-seq (2011, methodology): “In contrast, the second approach includes Burrows-Wheeler transform methods 39–41 such as Burrows-Wheeler alignment (BWA) 40 and Bowtie 39 , which compact the genome into a data structure that is very efficient when searching for perfect matches 42,43 .”
A four-stage algorithm for updating a Burrows-Wheeler transform (2009, background): “LF [0] = CT [G] + rankG(L, 0)− 1 = 3 + 1− 1 = 3 LF [1] = CT [$] + rank$ (L, 1)− 1 = 0 + 1− 1 = 0 LF [2] = CT [G] + rankG(L, 2)− 1 = 3 + 2− 1 = 4 LF [3] = CT [C] + rankC(L, 3)− 1 = 2 + 1− 1 = 2 LF [4] = CT [T] + rankT(L, 4)− 1 = 5 + 1− 1 = 5 LF [5] = CT [A] + rankA(L, 5)− 1 = 1 + 1− 1 = 1 i F L LF 0 ”