Document Detail


SCALCE: boosting sequence compression algorithms using locally consistent encoding.
MedLine Citation:
PMID:  23047557     Owner:  NLM     Status:  MEDLINE    
Abstract/OtherAbstract:
MOTIVATION: The high throughput sequencing (HTS) platforms generate unprecedented amounts of data that introduce challenges for the computational infrastructure. Data management, storage and analysis have become major logistical obstacles for those adopting the new platforms. The requirement for large investment for this purpose almost signalled the end of the Sequence Read Archive hosted at the National Center for Biotechnology Information (NCBI), which holds most of the sequence data generated world wide. Currently, most HTS data are compressed through general purpose algorithms such as gzip. These algorithms are not designed for compressing data generated by the HTS platforms; for example, they do not take advantage of the specific nature of genomic sequence data, that is, limited alphabet size and high similarity among reads. Fast and efficient compression algorithms designed specifically for HTS data should be able to address some of the issues in data management, storage and communication. Such algorithms would also help with analysis provided they offer additional capabilities such as random access to any read and indexing for efficient sequence similarity search. Here we present SCALCE, a 'boosting' scheme based on Locally Consistent Parsing technique, which reorganizes the reads in a way that results in a higher compression speed and compression rate, independent of the compression algorithm in use and without using a reference genome.
RESULTS: Our tests indicate that SCALCE can improve the compression rate achieved through gzip by a factor of 4.19-when the goal is to compress the reads alone. In fact, on SCALCE reordered reads, gzip running time can improve by a factor of 15.06 on a standard PC with a single core and 6 GB memory. Interestingly even the running time of SCALCE + gzip improves that of gzip alone by a factor of 2.09. When compared with the recently published BEETL, which aims to sort the (inverted) reads in lexicographic order for improving bzip2, SCALCE + gzip provides up to 2.01 times better compression while improving the running time by a factor of 5.17. SCALCE also provides the option to compress the quality scores as well as the read names, in addition to the reads themselves. This is achieved by compressing the quality scores through order-3 Arithmetic Coding (AC) and the read names through gzip through the reordering SCALCE provides on the reads. This way, in comparison with gzip compression of the unordered FASTQ files (including reads, read names and quality scores), SCALCE (together with gzip and arithmetic encoding) can provide up to 3.34 improvement in the compression rate and 1.26 improvement in running time.
AVAILABILITY: Our algorithm, SCALCE (Sequence Compression Algorithm using Locally Consistent Encoding), is implemented in C++ with both gzip and bzip2 compression options. It also supports multithreading when gzip option is selected, and the pigz binary is available. It is available at http://scalce.sourceforge.net.
CONTACT: fhach@cs.sfu.ca or cenk@cs.sfu.ca
SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.
Authors:
Faraz Hach; Ibrahim Numanagic; Can Alkan; S Cenk Sahinalp
Related Documents :
24136997 - Img/m 4 version of the integrated metagenome comparative analysis system.
1327967 - Mutational analysis of the escherichia coli serb promoter region reveals transcriptiona...
18227257 - Induction of aggregatibacter actinomycetemcomitans leukotoxin expression by is1301 and ...
9603867 - Expression of the transposase gene tnpa of tn4652 is positively affected by integration...
18612417 - Lateral transfer of a lectin-like antifreeze protein gene in fishes.
19324097 - Speciation of a tropical fungal species pair following transoceanic dispersal.
Publication Detail:
Type:  Journal Article; Research Support, N.I.H., Extramural; Research Support, Non-U.S. Gov't     Date:  2012-10-09
Journal Detail:
Title:  Bioinformatics (Oxford, England)     Volume:  28     ISSN:  1367-4811     ISO Abbreviation:  Bioinformatics     Publication Date:  2012 Dec 
Date Detail:
Created Date:  2012-11-29     Completed Date:  2013-08-05     Revised Date:  2013-12-04    
Medline Journal Info:
Nlm Unique ID:  9808944     Medline TA:  Bioinformatics     Country:  England    
Other Details:
Languages:  eng     Pagination:  3051-7     Citation Subset:  IM    
Export Citation:
APA/MLA Format     Download EndNote     Download BibTex
MeSH Terms
Descriptor/Qualifier:
Algorithms*
Computational Biology / methods
Data Compression / methods*
Genome
Genomics / methods
High-Throughput Nucleotide Sequencing
Humans
Pseudomonas aeruginosa / genetics
Sequence Alignment
Software*
Grant Support
ID/Acronym/Agency:
HG006004/HG/NHGRI NIH HHS
Comments/Corrections

From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine


Previous Document:  Global network alignment using multiscale spectral signatures.
Next Document:  Bayesian correlated clustering to integrate multiple datasets.