{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T06:15:15Z","timestamp":1769840115190,"version":"3.49.0"},"reference-count":43,"publisher":"Oxford University Press (OUP)","issue":"2","license":[{"start":{"date-parts":[[2021,9,15]],"date-time":"2021-09-15T00:00:00Z","timestamp":1631664000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61373044"],"award-info":[{"award-number":["61373044"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,1,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec><jats:title>Motivation<\/jats:title><jats:p>Ultrahigh-throughput next-generation sequencing instruments continue to generate vast amounts of genomic data. These data are generally stored in FASTQ format. Two important simultaneous goals are space-efficient compressed storage of the genomic data and fast query performance. Toward that end, we introduce compressed indexing to store and retrieve FASTQ files.<\/jats:p><\/jats:sec><jats:sec><jats:title>Results<\/jats:title><jats:p>We propose a compressed index for FASTQ files called CIndex. CIndex uses the Burrows\u2013Wheeler transform and the wavelet tree, combined with hybrid encoding, succinct data structures and tables REF and R\u03b3, to achieve minimal space usage and fast retrieval on the compressed FASTQ files. Experiments conducted over real publicly available datasets from various sequencing instruments demonstrate that our proposed index substantially outperforms existing state-of-the-art solutions. For count, locate and extract queries on reads, our method uses 2.7\u201341.66% points less space and provides a speedup of 70\u2013167.16 times, 1.44\u201335.57 times and 1.3\u201355.4 times. For extracting records in FASTQ files, our method uses 2.86\u201314.88% points less space and provides a speedup of 3.13\u201320.1 times. CIndex has an additional advantage in that it can be readily adapted to work as a general-purpose text index; experiments show that it performs very well in practice.<\/jats:p><\/jats:sec><jats:sec><jats:title>Availability and implementation<\/jats:title><jats:p>The software is available on Github: https:\/\/github.com\/Hongweihuo-Lab\/CIndex.<\/jats:p><\/jats:sec><jats:sec><jats:title>Supplementary information<\/jats:title><jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p><\/jats:sec>","DOI":"10.1093\/bioinformatics\/btab655","type":"journal-article","created":{"date-parts":[[2021,9,10]],"date-time":"2021-09-10T19:10:14Z","timestamp":1631301014000},"page":"335-343","source":"Crossref","is-referenced-by-count":6,"title":["CIndex: compressed indexes for fast retrieval of FASTQ files"],"prefix":"10.1093","volume":"38","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5436-1851","authenticated-orcid":false,"given":"Hongwei","family":"Huo","sequence":"first","affiliation":[{"name":"Department of Computer Science, Xidian University , Xi\u2019an 710071, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pengfei","family":"Liu","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Xidian University , Xi\u2019an 710071, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chenhui","family":"Wang","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Xidian University , Xi\u2019an 710071, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hongbo","family":"Jiang","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Xidian University , Xi\u2019an 710071, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7970-6118","authenticated-orcid":false,"given":"Jeffrey Scott","family":"Vitter","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Tulane University , New Orleans, LA 70118, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2021,9,15]]},"reference":[{"key":"2023020108442754000_btab655-B1","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1016\/j.tcs.2012.02.002","article-title":"Lightweight algorithms for constructing and inverting the BWT of string collections","volume":"483","author":"Bauer","year":"2013","journal-title":"Theor. Comput. Sci"},{"key":"2023020108442754000_btab655-B2","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1093\/bioinformatics\/bty608","article-title":"Crumble: reference free lossy compression of sequence quality values","volume":"35","author":"Bonfield","year":"2019","journal-title":"Bioinformatics"},{"key":"2023020108442754000_btab655-B3","doi-asserted-by":"crossref","first-page":"1731","DOI":"10.1093\/bioinformatics\/btp319","article-title":"Data structures and compression algorithms for genomic sequence data","volume":"25","author":"Brandon","year":"2009","journal-title":"Bioinformatics"},{"key":"2023020108442754000_btab655-B4","volume-title":"A block-sorting lossless data compression algorithm (Tech. Report SRC-RR-124)","author":"Burrows","year":"1994"},{"key":"2023020108442754000_btab655-B5","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":"2023020108442754000_btab655-B6","doi-asserted-by":"crossref","first-page":"2674","DOI":"10.1093\/bioinformatics\/bty1015","article-title":"SPRING: a next-generation compressor for FASTQ data","volume":"35","author":"Chandak","year":"2019","journal-title":"Bioinformatics"},{"key":"2023020108442754000_btab655-B7","doi-asserted-by":"crossref","first-page":"1696","DOI":"10.1093\/bioinformatics\/18.12.1696","article-title":"DNACompress: fast and effective DNA sequence compression","volume":"18","author":"Chen","year":"2002","journal-title":"Bioinformatics"},{"key":"2023020108442754000_btab655-B8","doi-asserted-by":"crossref","first-page":"2654","DOI":"10.1109\/TKDE.2019.2954527","article-title":"MSQ-Index: a succinct index for fast graph similarity search","volume":"33","author":"Chen","year":"2021","journal-title":"IEEE Trans. Knowl. Data Eng"},{"key":"2023020108442754000_btab655-B9","volume-title":"Compact pat trees","author":"Clark","year":"1996"},{"key":"2023020108442754000_btab655-B10","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":"2023020108442754000_btab655-B11","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":"2023020108442754000_btab655-B12","doi-asserted-by":"crossref","first-page":"860","DOI":"10.1093\/bioinformatics\/btr014","article-title":"Compression of DNA sequence reads in FASTQ format","volume":"27","author":"Deorowicz","year":"2011","journal-title":"Bioinformatics"},{"key":"2023020108442754000_btab655-B13","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1145\/321812.321820","article-title":"Efficient storage and retrieval by content and address of static files","volume":"21","author":"Elias","year":"1974","journal-title":"J. Assoc. Comput. Mach"},{"key":"2023020108442754000_btab655-B14","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1109\/TIT.1975.1055349","article-title":"Universal codeword sets and representations of the integers","volume":"21","author":"Elias","year":"1975","journal-title":"IEEE Trans. Inform. Theory"},{"key":"2023020108442754000_btab655-B15","volume-title":"Memorandum","author":"Fano","year":"1971"},{"key":"2023020108442754000_btab655-B16","doi-asserted-by":"crossref","first-page":"552","DOI":"10.1145\/1082036.1082039","article-title":"Indexing compressed texts","volume":"52","author":"Ferragina","year":"2005","journal-title":"J. ACM"},{"key":"2023020108442754000_btab655-B17","first-page":"62","author":"Foschini","year":"2004"},{"key":"2023020108442754000_btab655-B18","doi-asserted-by":"crossref","first-page":"611","DOI":"10.1145\/1198513.1198521","article-title":"When indexing equals compression: experiments with compressing suffix arrays and applications","volume":"2","author":"Foschini","year":"2006","journal-title":"ACM Trans. Algor"},{"key":"2023020108442754000_btab655-B19","doi-asserted-by":"crossref","first-page":"1370","DOI":"10.1007\/s00453-018-0475-9","article-title":"Fixed block compression boosting in FM-indexes: theory and practice","volume":"81","author":"Gog","year":"2019","journal-title":"Algorithmica"},{"key":"2023020108442754000_btab655-B20","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1137\/S0097539702402354","article-title":"Compressed suffix arrays and suffix trees with applications to text indexing and string matching","volume":"35","author":"Grossi","year":"2005","journal-title":"SIAM J. Comput"},{"key":"2023020108442754000_btab655-B21","first-page":"841","author":"Grossi","year":"2003"},{"key":"2023020108442754000_btab655-B22","first-page":"210","author":"Grossi","year":"2011"},{"key":"2023020108442754000_btab655-B23","doi-asserted-by":"crossref","first-page":"765","DOI":"10.1016\/0306-4573(92)90067-A","article-title":"New methods for lossless image compression using arithmetic coding, invited paper in special issue on data compression for image and text in","volume":"28","author":"Howard","year":"1992","journal-title":"J. Inform. Process. Manage"},{"key":"2023020108442754000_btab655-B24","first-page":"292","author":"Huo","year":"2014"},{"key":"2023020108442754000_btab655-B25","first-page":"10","author":"Huo","year":"2015"},{"key":"2023020108442754000_btab655-B26","first-page":"271","author":"Huo","year":"2016"},{"key":"2023020108442754000_btab655-B27","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2020.2968323","article-title":"Efficient compression and indexing for highly repetitive DNA sequence collections","author":"Huo","year":"2020","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinf"},{"key":"2023020108442754000_btab655-B28","article-title":"Practical high-order entropy-compressed text self-indexing","author":"Huo","year":"2020"},{"key":"2023020108442754000_btab655-B29","volume-title":"Succinct static data structures","author":"Jacobson","year":"1989"},{"key":"2023020108442754000_btab655-B30","doi-asserted-by":"crossref","first-page":"2796","DOI":"10.1093\/bioinformatics\/btu387","article-title":"BEETL-fastq: a searchable compressed archive for DNA reads","volume":"30","author":"Janin","year":"2014","journal-title":"Bioinformatics"},{"key":"2023020108442754000_btab655-B32","doi-asserted-by":"crossref","first-page":"791","DOI":"10.1093\/bioinformatics\/btn032","article-title":"Compressed indexing and local alignment of DNA","volume":"24","author":"Lam","year":"2008","journal-title":"Bioinformatics"},{"key":"2023020108442754000_btab655-B33","doi-asserted-by":"crossref","first-page":"R25","DOI":"10.1186\/gb-2009-10-3-r25","article-title":"Ultrafast and memory-efficient alignment of short DNA sequences to the human genome","volume":"10","author":"Langmead","year":"2009","journal-title":"Genome Biol"},{"key":"2023020108442754000_btab655-B34","doi-asserted-by":"crossref","first-page":"1754","DOI":"10.1093\/bioinformatics\/btp324","article-title":"Fast and accurate short read alignment with Burrows-Wheeler transform","volume":"25","author":"Li","year":"2009","journal-title":"Bioinformatics"},{"key":"2023020108442754000_btab655-B35","doi-asserted-by":"crossref","first-page":"2078","DOI":"10.1093\/bioinformatics\/btp352","article-title":"The sequence alignment\/map format and samtools","volume":"25","author":"Li","year":"2009","journal-title":"Bioinformatics"},{"key":"2023020108442754000_btab655-B36","doi-asserted-by":"crossref","first-page":"2066","DOI":"10.1093\/bioinformatics\/bty936","article-title":"Index suffix-prefix overlaps by (w, k)-minimizer to generate long contigs for reads compression","volume":"35","author":"Liu","year":"2019","journal-title":"Bioinformatics"},{"key":"2023020108442754000_btab655-B38","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":"2023020108442754000_btab655-B39","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0222058","article-title":"Suffix arrays: a new method for on-line string searches","volume":"22","author":"Manber","year":"1993","journal-title":"SIAM J. Comput"},{"key":"2023020108442754000_btab655-B40","doi-asserted-by":"crossref","first-page":"1464","DOI":"10.1093\/bioinformatics\/btx001","article-title":"AFRESh: an adaptive framework for compression of reads and assembled sequences with random access functionality","volume":"33","author":"Paridaens","year":"2017","journal-title":"Bioinformatics"},{"key":"2023020108442754000_btab655-B41","doi-asserted-by":"crossref","first-page":"911","DOI":"10.1093\/bioinformatics\/btx685","article-title":"ChIPWig: a random access-enabling lossless and lossy compression method for ChIP-seq data","volume":"34","author":"Ravanmehr","year":"2018","journal-title":"Bioinformatics"},{"key":"2023020108442754000_btab655-B42","doi-asserted-by":"crossref","first-page":"2213","DOI":"10.1093\/bioinformatics\/btu208","article-title":"DSRC 2\u2014industry-oriented compression of FASTQ files","volume":"30","author":"Roguski","year":"2014","journal-title":"Bioinformatics"},{"key":"2023020108442754000_btab655-B43","doi-asserted-by":"crossref","first-page":"2058","DOI":"10.1093\/bioinformatics\/bty934","article-title":"High efficiency referential genome compression algorithm","volume":"35","author":"Shi","year":"2019","journal-title":"Bioinformatics"},{"key":"2023020108442754000_btab655-B44","first-page":"83","author":"Vigna","year":"2013"},{"key":"2023020108442754000_btab655-B45","doi-asserted-by":"crossref","first-page":"4551","DOI":"10.1093\/bioinformatics\/btaa543","article-title":"ScaleQC: a scalable lossy to lossless solution for NGS data compression","volume":"36","author":"Yu","year":"2020","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btab655\/41103913\/btab655.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/38\/2\/335\/49006500\/btab655.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/38\/2\/335\/49006500\/btab655.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,8]],"date-time":"2023-11-08T17:18:07Z","timestamp":1699463887000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/38\/2\/335\/6370694"}},"subtitle":[],"editor":[{"given":"Jonathan","family":"Wren","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2021,9,15]]},"references-count":43,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,1,3]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btab655","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2022,1,15]]},"published":{"date-parts":[[2021,9,15]]}}}