Prefix-free parsing for building big BWTs

DOI10.4230/LIPICS.WABI.2018.2MaRDI QIDQ5090326zbMATH OpenOpenAlexFDO

Authors Christina Boucher, Travis Gagie, Alan Kuhnle, Giovanni Manzini

Publication date 18 July 2022

Full work available at URL https://arxiv.org/abs/1803.11245

zbMATH Keywords

Burrows-Wheeler transformcompression-aware algorithmsgenomic databasesprefix-free parsing

Mathematics Subject Classification ID

Computational methods for problems pertaining to biology (92-08) Genetics and epigenetics (92D10) Protein sequences, DNA sequences (92D20)

Abstract: High-throughput sequencing technologies have led to explosive growth of genomic databases; one of which will soon reach hundreds of terabytes. For many applications we want to build and store indexes of these databases but constructing such indexes is a challenge. Fortunately, many of these genomic databases are highly-repetitive---a characteristic that can be exploited to ease the computation of the Burrows-Wheeler Transform (BWT), which underlies many popular indexes. In this paper, we introduce a preprocessing algorithm, referred to as {em prefix-free parsing}, that takes a text $T$ as input, and in one-pass generates a dictionary $D$ and a parse $P$ of $T$ with the property that the BWT of $T$ can be constructed from $D$ and $P$ using workspace proportional to their total size and $O(|T|)$-time. Our experiments show that $D$ and $P$ are significantly smaller than $T$ in practice, and thus, can fit in a reasonable internal memory even when $T$ is very large. In particular, we show that with prefix-free parsing we can build an 131-megabyte run-length compressed FM-index (restricted to support only counting and not locating) for 1000 copies of human chromosome 19 in 2 hours using 21 gigabytes of memory, suggesting that we can build a 6.73 gigabyte index for 1000 complete human-genome haplotypes in approximately 102 hours using about 1 terabyte of memory.

Recommendations

• Lightweight BWT construction for very large string collections
• Linear-time string indexing and analysis in small space
• Lightweight algorithms for constructing and inverting the BWT of string collections
• Space-efficient construction of compressed suffix trees
• Computing the multi-string BWT and LCP array in external memory

Cites work

• From LZ77 to the run-length encoded Burrows-Wheeler transform, and back
• scientific article; zbMATH DE number 6850405 (Why is no real title available?)
• Indexing compressed text
• Inducing enhanced suffix arrays for string collections
• Lightweight data indexing and compression in external memory

Cited in

(5)

• Refining the \(r\)-index
• Efficient construction of the BWT for repetitive text using string compression
• Rpair: rescaling RePair with Rsync
• Prefix-free parsing for building large tunnelled Wheeler graphs
• b-move: faster bidirectional character extensions in a run-length compressed index

Describes a project that uses

Uses Software

• Big-BWT

This page was built for publication: Prefix-free parsing for building big BWTs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090326)