Skip Navigation



Bioinformatics Advance Access published online on May 15, 2009
Bioinformatics, doi:10.1093/bioinformatics/btp319
This Article
Right arrow Advance Access manuscript (PDF)
Right arrow All Versions of this Article:
25/14/1731    most recent
btp319v1
Right arrow Comments: Submit a response
Right arrow Alert me when this article is cited
Right arrow Alert me when Comments are posted
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in PubMed
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Brandon, M. C.
Right arrow Articles by Baldi, P.
Right arrow Search for Related Content
PubMed
Right arrow PubMed Citation
Right arrow Articles by Brandon, M. C.
Right arrow Articles by Baldi, P.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author (2009). Published by Oxford University Press. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

Data Structures and Compression Algorithms for Genomic Sequence Data

Marty C. Brandon 1,2,4, Douglas C. Wallace 2,3,4 and Pierre Baldi 1,2,3,*

1Department of Computer Science, UCI, Irvine, CA 92697
2 Institute for Genomics and Bioinformatics, UCI, Irvine, CA 92697
3 Department of Biological Chemistry, UCI, Irvine, CA 92697
4 Center for Molecular and Mitochondrial Medicine and Genetics, UCI, Irvine, CA 92697

*To whom correspondence should be addressed. Prof. Pierre Baldi, E-mail: pfbaldi{at}ics.uci.edu


  Abstract

Motivation: The continuing exponential accumulation of full genome data, including full diploid human genomes, creates new challenges not only for understanding genomic structure, function, and evolution, but also for the storage, navigation, and privacy of genomic data. Here we develop data structures and algorithms for the efficient storage of genomic and other sequence data that may also facilitate querying and protecting the data.

Results: The general idea is to encode only the differences between a genome sequence and a reference sequence, using absolute or relative coordinates for the location of the differences. These locations and the corresponding differential variants can be encoded into binary strings using various entropy coding methods, from fixed codes such as Golomb and Elias codes, to variables codes, such as Huffman codes. We demonstrate the approach and various tradeoffs using highly variables human mitochondrial genome sequences as a testbed. With only a partial level of optimization, 3,615 genome sequences occupying 56 Megabytes in GenBank are compressed down to only 167 Kilobytes, achieving a 345-fold compression rate, using the revised Cambridge Reference Sequence as the reference sequence. Using the consensus sequence as the reference sequence, the data can be stored using only 133 Kilobytes, corresponding to a 433-fold level of compression, roughly a 23% improvement. Extensions to nuclear genomes and high-throughput sequencing data are discussed.

Availability: Data is publicly available from GenBank, the HapMap Web site, and the MITOMAP database. Supplementary materials with additional results, statistics, and software implementations are available from http://mammag.web.uci.edu/bin/view/Mitowiki/ProjectDNACompression.

Contact: pfbaldi{at}uci.com,mbrandon{at}uci.edu

Associate Editor: Prof. Alfonso Valencia

Received on November 25, 2008; revised on April 13, 2009; accepted on May 11, 2009

Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer: Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.