{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,17]],"date-time":"2026-08-17T23:14:39Z","timestamp":1787008479056,"version":"3.56.0"},"reference-count":23,"publisher":"Oxford University Press (OUP)","issue":"4","license":[{"start":{"date-parts":[[2017,10,9]],"date-time":"2017-10-09T00:00:00Z","timestamp":1507507200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/about_us\/legal\/notices"}],"funder":[{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"publisher","award":["5U01CA198943"],"award-info":[{"award-number":["5U01CA198943"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018,2,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Motivation<\/jats:title>\n                    <jats:p>New Generation Sequencing (NGS) technologies for genome sequencing produce large amounts of short genomic reads per experiment, which are highly redundant and compressible. However, general-purpose compressors are unable to exploit this redundancy due to the special structure present in the data.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>We present a new algorithm for compressing reads both with and without preserving the read order. In both cases, it achieves 1.4\u00d7\u20132\u00d7 compression gain over state-of-the-art read compression tools for datasets containing as many as 3 billion Illumina reads. Our tool is based on the idea of approximately reordering the reads according to their position in the genome using hashed substring indices. We also present a systematic analysis of the read compression problem and compute bounds on fundamental limits of read compression. This analysis sheds light on the dynamics of the proposed algorithm (and read compression algorithms in general) and helps understand its performance in practice. The algorithm compresses only the read sequence, works with unaligned FASTQ files, and does not require a reference.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Supplementary information<\/jats:title>\n                    <jats:p>Supplementary material are available at Bioinformatics online. The proposed algorithm is available for download at https:\/\/github.com\/shubhamchandak94\/HARC.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btx639","type":"journal-article","created":{"date-parts":[[2017,10,6]],"date-time":"2017-10-06T15:12:01Z","timestamp":1507302721000},"page":"558-567","source":"Crossref","is-referenced-by-count":40,"title":["Compression of genomic sequencing reads via hash-based reordering: algorithm and analysis"],"prefix":"10.1093","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1130-9762","authenticated-orcid":false,"given":"Shubham","family":"Chandak","sequence":"first","affiliation":[{"name":"Department of Electrical Engineering, Stanford University, Stanford, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kedar","family":"Tatwawadi","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering, Stanford University, Stanford, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tsachy","family":"Weissman","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering, Stanford University, Stanford, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2017,10,9]]},"reference":[{"key":"2023012712332798700_btx639-B1","author":"Adler","year":"2016"},{"key":"2023012712332798700_btx639-B2","doi-asserted-by":"crossref","first-page":"406","DOI":"10.1038\/jhg.2011.43","article-title":"Evaluation of next-generation sequencing software in mapping and assembly","volume":"56","author":"Bao","year":"2011","journal-title":"J. Hum. Genet"},{"key":"2023012712332798700_btx639-B3","doi-asserted-by":"crossref","first-page":"288.","DOI":"10.1186\/s12859-015-0709-7","article-title":"Reference-free compression of high throughput sequencing data with a probabilistic de Bruijn graph","volume":"16","author":"Benoit","year":"2015","journal-title":"BMC Bioinformatics"},{"issue":"3","key":"2023012712332798700_btx639-B4","first-page":"e59190","article-title":"Compression of FASTQ and SAM Format Sequencing Data","volume":"8","author":"Bonfield","year":"2013"},{"key":"2023012712332798700_btx639-B5","author":"Burrows","year":"1994"},{"key":"2023012712332798700_btx639-B6","doi-asserted-by":"crossref","first-page":"2130","DOI":"10.1093\/bioinformatics\/btu183","article-title":"Lossy compression of quality scores in genomic data","volume":"30","author":"C\u00e1novas","year":"2014","journal-title":"Bioinformatics"},{"key":"2023012712332798700_btx639-B7","doi-asserted-by":"crossref","first-page":"1767","DOI":"10.1093\/nar\/gkp1137","article-title":"The Sanger FASTQ file format for sequences with quality scores, and the Solexa\/Illumina FASTQ variants","volume":"38","author":"Cock","year":"2010","journal-title":"Nucleic Acids Res"},{"key":"2023012712332798700_btx639-B8","doi-asserted-by":"crossref","first-page":"1415","DOI":"10.1093\/bioinformatics\/bts173","article-title":"Large-scale compression of genomic sequence databases with the Burrows-Wheeler transform","volume":"28","author":"Cox","year":"2012","journal-title":"Bioinformatics"},{"key":"2023012712332798700_btx639-B9","doi-asserted-by":"crossref","first-page":"1389","DOI":"10.1093\/bioinformatics\/btu844","article-title":"Disk-based compression of data from genome sequencing","volume":"31","author":"Grabowski","year":"2015","journal-title":"Bioinformatics"},{"key":"2023012712332798700_btx639-B10","author":"Grebnov","year":"2015"},{"key":"2023012712332798700_btx639-B11","doi-asserted-by":"crossref","first-page":"3051","DOI":"10.1093\/bioinformatics\/bts593","article-title":"SCALCE: boosting sequence compression algorithms using locally consistent encoding","volume":"28","author":"Hach","year":"2012","journal-title":"Bioinformatics"},{"key":"2023012712332798700_btx639-B12","first-page":"50","volume-title":"Dynamic Alignment-Free and Reference-Free Read Compression","author":"Holley","year":"2017"},{"key":"2023012712332798700_btx639-B13","doi-asserted-by":"crossref","first-page":"e171.","DOI":"10.1093\/nar\/gks754","article-title":"Compression of next-generation sequencing reads aided by highly efficient de novo assembly","volume":"40","author":"Jones","year":"2012","journal-title":"Nucleic Acids Res"},{"key":"2023012712332798700_btx639-B14","author":"Limasset","year":"2017"},{"key":"2023012712332798700_btx639-B15","doi-asserted-by":"crossref","first-page":"3122","DOI":"10.1093\/bioinformatics\/btv330","article-title":"QVZ: lossy compression of quality values","volume":"31","author":"Malysa","year":"2015","journal-title":"Bioinformatics"},{"key":"2023012712332798700_btx639-B16","doi-asserted-by":"crossref","first-page":"R112.","DOI":"10.1186\/gb-2011-12-11-r112","article-title":"Evaluation of genomic high-throughput sequencing data generated on Illumina HiSeq and Genome Analyzer systems","volume":"12","author":"Minoche","year":"2011","journal-title":"Genome Biol"},{"key":"2023012712332798700_btx639-B17","doi-asserted-by":"crossref","first-page":"1005","DOI":"10.1038\/nmeth.4037","article-title":"Comparison of high-throughput sequencing data compression tools","volume":"13","author":"Numanagic","year":"2016","journal-title":"Nat. Methods"},{"key":"2023012712332798700_btx639-B18","doi-asserted-by":"crossref","first-page":"1442002.","DOI":"10.1142\/S0219720014420025","article-title":"Aligned genomic data compression via improved modeling","volume":"12","author":"Ochoa","year":"2014","journal-title":"J. Bioinform. Computat. Biol"},{"key":"2023012712332798700_btx639-B19","doi-asserted-by":"crossref","first-page":"2770","DOI":"10.1093\/bioinformatics\/btv248","article-title":"Data-dependent bucketing improves reference-free compression of sequencing reads","volume":"31","author":"Patro","year":"2015","journal-title":"Bioinformatics"},{"key":"2023012712332798700_btx639-B20","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1093\/bioinformatics\/btt594","article-title":"MFCompress: a compression tool for FASTA and multi-FASTA data","volume":"30","author":"Pinho","year":"2014","journal-title":"Bioinformatics"},{"key":"2023012712332798700_btx639-B21","doi-asserted-by":"crossref","first-page":"3363","DOI":"10.1093\/bioinformatics\/bth408","article-title":"Reducing storage requirements for biological sequence","volume":"20","author":"Roberts","year":"2004","journal-title":"Bioinformatics"},{"key":"2023012712332798700_btx639-B22","author":"Trojette","year":"2016"},{"key":"2023012712332798700_btx639-B23","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","article-title":"A universal algorithm for sequential data compression","volume":"23","author":"Ziv","year":"1977","journal-title":"IEEE Trans. Inform. Theor"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/34\/4\/558\/48913889\/bioinformatics_34_4_558.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/34\/4\/558\/48913889\/bioinformatics_34_4_558.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T08:21:44Z","timestamp":1674807704000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/34\/4\/558\/4386919"}},"subtitle":[],"editor":[{"given":"Inanc","family":"Birol","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]}],"short-title":[],"issued":{"date-parts":[[2017,10,9]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,2,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btx639","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2018,2,15]]},"published":{"date-parts":[[2017,10,9]]}}}