Source-linked AI summary
Large-scale compression of genomic sequence databases with the Burrows-Wheeler transform
Anthony J. Cox, Markus J. Bauer, Tobias Jakobi, Giovanna Rosone
TL;DR
Large DNA read collections contain dispersed redundancy that conventional local compressors cannot fully exploit, while computing BWTs at this scale has been difficult. The paper combines practical large-scale BWT construction with sequence reordering and implicit sorting to improve lossless compression. On real 45× human-genome data, the approach reaches 0.48 bits per base and stores 135.3 Gbp in 8.2 Gbytes, while also supporting compressed indexing.
Problem
Large sequencing datasets contain dispersed coverage redundancy, while BWT computation costs have limited application of BWT compression and indexing at genome scale.
Method
The paper combines practical BWT computation with SAP-array-guided sequence reordering and implicit sorting to reduce runs without explicitly sorting the reads.
Results
0.48 bits per base allowed 135.3Gbp of real human-genome data to fit in 8.2Gbytes, with reordering necessary for best compression.
Takeaways & Limitations
The compressed BWT can also support FM-index count and locate queries and may enable indexed algorithms operating directly on whole-genome read collections.
Takeaways & Limitations
Quality scores remain difficult to compress losslessly, and the implementation assumes equal read lengths although that restriction is not intrinsic to the algorithm.
Abstract
from arXiv · showhide
Motivation The Burrows-Wheeler transform (BWT) is the foundation of many algorithms for compression and indexing of text data, but the cost of computing the BWT of very large string collections has prevented these techniques from being widely applied to the large sets of sequences often encountered as the outcome of DNA sequencing experiments. In previous work, we presented a novel algorithm that allows the BWT of human genome scale data to be computed on very moderate hardware, thus enabling us to investigate the BWT as a tool for the compression of such datasets. Results We first used simulated reads to explore the relationship between the level of compression and the error rate, the length of the reads and the level of sampling of the underlying genome and compare choices of second-stage compression algorithm. We demonstrate that compression may be greatly improved by a particular reordering of the sequences in the collection and give a novel `implicit sorting' strategy that enables these benefits to be realised without the overhead of sorting the reads. With these techniques, a 45x coverage of real human genome sequence data compresses losslessly to under 0.5 bits per base, allowing the 135.3Gbp of sequence to fit into only 8.2Gbytes of space (trimming a small proportion of low-quality bases from the reads improves the compression still further). This is more than 4 times smaller than the size achieved by a standard BWT-based compressor (bzip2) on the untrimmed reads, but an important further advantage of our approach is that it facilitates the building of compressed full text indexes such as the FM-index on large-scale DNA sequence collections.
Doc-StartBIOINFORMATICS
The supplied passages contain publication metadata rather than substantive paper content.
- The manuscript lists receipt, revision, and acceptance dates as placeholders.
- An associate editor is identified using a placeholder.
- The correspondence footnote and copyright notice are also placeholders or standard publication metadata.
1 INTRODUCTION
The paper addresses lossless compression of large collections of short DNA reads, whose repeated genomic coverage is difficult for local-comparison compressors to exploit. It develops practical BWT-based infrastructure and evaluates how sequencing and compression choices affect performance.
- The paper presents strategies for lossless compression of the many short DNA sequences produced by sequencing experiments.
- 20-fold average coverage or more creates additional redundancy, but random dispersion of locus copies makes it inaccessible to small recent-data buffers.
- Reference-based compression saves space by aligning reads to a reference, but is fundamentally lossy and can limit future reanalysis.
- BWT-based compression exploits runs and reconstructibility, while bzip2 mainly captures local similarities within blocks of at most 900 kbytes.
- BEETL makes BWT computation practical for large DNA collections and supports evaluation of coverage, sequencing error, read length, trimming, and second-stage compressors.
2 METHODS
The method reorders collection elements to reduce BWT runs within SAP-intervals, while computing the SAP-array alongside the BWT and avoiding explicit sorting through a single-pass procedure.
- The collection BWT associates each transformed symbol with a suffix, and distinct end markers impose an ordering on the input sequences.
- The SAP-array marks whether adjacent BWT-associated suffixes are identical after excluding end markers, partitioning the BWT into SAP-intervals.
- RLO sorting groups symbols within SAP-intervals into at most φ runs, compared with an upper bound of l runs without sorting.
- A single-pass procedure can identify SAP-intervals, sort their characters, and output a modified BWT without preprocessing the collection.
- The SAP-array is computed alongside the BWT by modifying the prior k-stage construction algorithm with minimal additional overhead.
- BWT construction processes j-suffixes iteratively, maintaining partial BWT segments and SAP values for subsequent insertions.
3 RESULTS
Experiments on simulated and real sequencing data show that BWT compression improves with read reordering, longer reads, and lower error rates, while compressor choice and trimming affect performance. On 45× human data, the approach compresses 135.3Gbp of reads to 8.2Gbytes at 0.48 bits per base.
- Coverage and ordering: 0.36bpb was achieved at 60× coverage with RLO ordering, versus 0.38bpb for SAP ordering and 0.55bpb for unsorted reads.PPMd default was used as the second-stage compressor.
- Second-stage compression: PPMd (large) reached 0.50bpb on 60× E.coli data, but compressed human-read BWT less well than PPMd (default) and was several times slower.The larger working space captured redundancy for the small E.coli genome but not for human data.
- Sequencing error: 1.2% substitution error approximately doubled compressed-BWT size from 0.47bpb to 0.90bpb at 40× coverage.
- Read length: Compressed-BWT size fell from 0.54bpb to 0.32bpb as error-free read length increased from 50bp to 800bp at 40× coverage.Longer reads allow repetitive sequences to be grouped together.
4 DISCUSSION
The discussion reports strong compression results while highlighting costs associated with read reordering and quality-score handling. It also emphasizes that the compressed BWT can support FM-index queries and potentially enable large-scale indexed sequence analysis.
- Compression results: 0.48bpb compressed 135.3Gbp of ERA015743 data into 8.2Gbytes, while SRX001540 reached 1.21bpb versus ReCoil’s 1.34bpb.The SRX001540 result was obtained in just over an hour, compared with ReCoil’s 14 hours on a slower processor.
- Read ordering: Reordering the strings was necessary for best compression, but preserving paired-read relationships after reordering requires an additional pointer for each read’s mate.This creates storage overhead when paired-read adjacency is lost.
- Indexed queries: The compressed BWT, augmented with small data structures, forms an FM-index supporting k-mer count and locate queries.The cited FM-index variant uses nHk(T)+o(n) bits, counts length-p strings in O(p) time, and locates occurrences in O(log1+ϵn) time.
- Quality scores: Lossless compression of quality scores can be difficult, motivating future work on identifying bases whose scores may be discarded for downstream variant calling.The proposed direction would use queries to a BWT-based index for de novo identification of such bases.
- Broader implications: Indexed read sets may facilitate computationally intensive sequence-analysis tasks, including overlap computation and practical de novo assembly.The discussion presents this as a possibility enabled by indexing whole-human-genome-scale read collections in compressed form.
Funding:
The paper reports affiliations and compensation involving Illumina. Two authors are employees receiving shares, and another contribution occurred during a paid internship.
- Affiliations: M.J.B. and A.J.C. are employees of Illumina Inc., a public company developing and marketing genetic-analysis systems.Their employment is disclosed in the funding statement.
- Compensation: M.J.B. and A.J.C. receive Illumina shares as part of their compensation.The statement identifies this compensation relationship explicitly.
- Contribution context: Part of T.J.’s contribution was made during a paid internship at Illumina’s offices in Cambridge, UK.The internship location and paid status are both specified.