Optimal compressed representation of high throughput sequence data via light assembly

Antonio A. Ginart, Joseph Hui, Kaiyuan Zhu (), Ibrahim Numanagić, Thomas A. Courtade, S. Cenk Sahinalp () and David N. Tse
Additional contact information
Antonio A. Ginart: Stanford University
Joseph Hui: Massachusetts Institute of Technology
Kaiyuan Zhu: Indiana University Bloomington
Ibrahim Numanagić: Massachusetts Institute of Technology
Thomas A. Courtade: University of California
S. Cenk Sahinalp: Indiana University Bloomington
David N. Tse: Stanford University

Nature Communications, 2018, vol. 9, issue 1, 1-9

Abstract: Abstract The most effective genomic data compression methods either assemble reads into contigs, or replace them with their alignment positions on a reference genome. Such methods require significant computational resources, but faster alternatives that avoid using explicit or de novo-constructed references fail to match their performance. Here, we introduce a new reference-free compressed representation for genomic data based on light de novo assembly of reads, where each read is represented as a node in a (compact) trie. We show how to efficiently build such tries to compactly represent reads and demonstrate that among all methods using this representation (including all de novo assembly based methods), our method achieves the shortest possible output. We also provide an lower bound on the compression rate achievable on uniformly sampled genomic read data, which is approximated by our method well. Our method significantly improves the compression performance of alternatives without compromising speed.

Date: 2018
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.nature.com/articles/s41467-017-02480-6 Abstract (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:nat:natcom:v:9:y:2018:i:1:d:10.1038_s41467-017-02480-6

Ordering information: This journal article can be ordered from
https://www.nature.com/ncomms/

DOI: 10.1038/s41467-017-02480-6

Access Statistics for this article

Nature Communications is currently edited by Nathalie Le Bot, Enda Bergin and Fiona Gillespie

More articles in Nature Communications from Nature
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().