Large-scale compression of genomic sequence databases with the Burrows-Wheeler transform

Cox AJ, Bauer MJ, Jakobi T, Rosone G (2012)
Bioinformatics 28(11): 1415-1419.

Zeitschriftenaufsatz | Veröffentlicht | Englisch
 
Download
Es wurde kein Volltext hochgeladen. Nur Publikationsnachweis!
Autor/in
; ; ;
Abstract / Bemerkung
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 (Bauer et al. (2011)), 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 45× 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 FMindex (Ferragina and Manzini (2000)) on large-scale DNA sequence collections. AVAILABILITY: Code to construct the BWT and SAP-array on large genomic data sets is part of the BEETL library, available as a github respository at git@github.com:BEETL/BEETL.git. CONTACT: acox@illumina.com.
Erscheinungsjahr
2012
Zeitschriftentitel
Bioinformatics
Band
28
Ausgabe
11
Seite(n)
1415-1419
ISSN
1367-4803
eISSN
1460-2059
Page URI
https://pub.uni-bielefeld.de/record/2496829

Zitieren

Cox AJ, Bauer MJ, Jakobi T, Rosone G. Large-scale compression of genomic sequence databases with the Burrows-Wheeler transform. Bioinformatics. 2012;28(11):1415-1419.
Cox, A. J., Bauer, M. J., Jakobi, T., & Rosone, G. (2012). Large-scale compression of genomic sequence databases with the Burrows-Wheeler transform. Bioinformatics, 28(11), 1415-1419. doi:10.1093/bioinformatics/bts173
Cox, A. J., Bauer, M. J., Jakobi, T., and Rosone, G. (2012). Large-scale compression of genomic sequence databases with the Burrows-Wheeler transform. Bioinformatics 28, 1415-1419.
Cox, A.J., et al., 2012. Large-scale compression of genomic sequence databases with the Burrows-Wheeler transform. Bioinformatics, 28(11), p 1415-1419.
A.J. Cox, et al., “Large-scale compression of genomic sequence databases with the Burrows-Wheeler transform”, Bioinformatics, vol. 28, 2012, pp. 1415-1419.
Cox, A.J., Bauer, M.J., Jakobi, T., Rosone, G.: Large-scale compression of genomic sequence databases with the Burrows-Wheeler transform. Bioinformatics. 28, 1415-1419 (2012).
Cox, Anthony J, Bauer, Markus J, Jakobi, Tobias, and Rosone, Giovanna. “Large-scale compression of genomic sequence databases with the Burrows-Wheeler transform”. Bioinformatics 28.11 (2012): 1415-1419.

Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Web of Science

Dieser Datensatz im Web of Science®

Quellen

PMID: 22556365
PubMed | Europe PMC

arXiv: 1205.0192

Suchen in

Google Scholar