{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T10:30:50Z","timestamp":1778754650670,"version":"3.51.4"},"reference-count":45,"publisher":"Oxford University Press (OUP)","issue":"12","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":608,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015,6,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Motivation: Storing, transmitting and archiving data produced by next-generation sequencing is a significant computational burden. New compression techniques tailored to short-read sequence data are needed.<\/jats:p>\n                  <jats:p>Results: We present here an approach to compression that reduces the difficulty of managing large-scale sequencing data. Our novel approach sits between pure reference-based compression and reference-free compression and combines much of the benefit of reference-based approaches with the flexibility of de novo encoding. Our method, called path encoding, draws a connection between storing paths in de Bruijn graphs and context-dependent arithmetic coding. Supporting this method is a system to compactly store sets of kmers that is of independent interest. We are able to encode RNA-seq reads using 3\u201311% of the space of the sequence in raw FASTA files, which is on average more than 34% smaller than competing approaches. We also show that even if the reference is very poorly matched to the reads that are being encoded, good compression can still be achieved.<\/jats:p>\n                  <jats:p>Availability and implementation: Source code and binaries freely available for download at http:\/\/www.cs.cmu.edu\/\u223cckingsf\/software\/pathenc\/, implemented in Go and supported on Linux and Mac OS X.<\/jats:p>\n                  <jats:p>Contact: carlk@cs.cmu.edu.<\/jats:p>\n                  <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btv071","type":"journal-article","created":{"date-parts":[[2015,2,3]],"date-time":"2015-02-03T20:18:07Z","timestamp":1422994687000},"page":"1920-1928","source":"Crossref","is-referenced-by-count":49,"title":["Reference-based compression of short-read sequences using path encoding"],"prefix":"10.1093","volume":"31","author":[{"given":"Carl","family":"Kingsford","sequence":"first","affiliation":[{"name":"1 Department of Computational Biology, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, USA and 2Department of Computer Science, Stony Brook University, Stony Brook, NY 11794-4400, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rob","family":"Patro","sequence":"additional","affiliation":[{"name":"1 Department of Computational Biology, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, USA and 2Department of Computer Science, Stony Brook University, Stony Brook, NY 11794-4400, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2015,2,2]]},"reference":[{"key":"2023020115111879100_btv071-B1","doi-asserted-by":"crossref","DOI":"10.1109\/CSB.2002.1039352","article-title":"DNA sequence compression using the Burrows-Wheeler transform","volume-title":"Procceeding IEEE Computer Society Bioinformatics Conference","author":"Adjeroh","year":"2002"},{"key":"2023020115111879100_btv071-B2","doi-asserted-by":"crossref","DOI":"10.1109\/BIBM.2011.110","article-title":"No-reference compression of genomic data stored in FASTQ format","volume-title":"IEEE International Conference on Bioinformatics and Biomedicine","author":"Bhola","year":"2011"},{"key":"2023020115111879100_btv071-B3","doi-asserted-by":"crossref","first-page":"2818","DOI":"10.1093\/bioinformatics\/btu390","article-title":"The Scramble conversion tool","volume":"30","author":"Bonfield","year":"2014","journal-title":"Bioinformatics"},{"key":"2023020115111879100_btv071-B4","doi-asserted-by":"crossref","first-page":"e59190","DOI":"10.1371\/journal.pone.0059190","article-title":"Compression of FASTQ and SAM format sequencing data","volume":"8","author":"Bonfield","year":"2013","journal-title":"PLoS One"},{"key":"2023020115111879100_btv071-B5","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":"2023020115111879100_btv071-B6","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1186\/1471-2105-11-94","article-title":"Evaluation of statistical methods for normalization and differential expression in mRNA-Seq experiments","volume":"11","author":"Bullard","year":"2010","journal-title":"BMC Bioinformatics"},{"key":"2023020115111879100_btv071-B7","doi-asserted-by":"crossref","first-page":"1324","DOI":"10.1093\/bioinformatics\/bts123","article-title":"Fulcrum: condensing redundant reads from high-throughput sequencing studies","volume":"28","author":"Burriesci","year":"2012","journal-title":"Bioinformatics"},{"key":"2023020115111879100_btv071-B8","article-title":"A block sorting lossless data compression algorithm","author":"Burrows","year":"1994","journal-title":"Technical Report 124"},{"key":"2023020115111879100_btv071-B9","doi-asserted-by":"crossref","first-page":"e79871","DOI":"10.1371\/journal.pone.0079871","article-title":"Compression of structured high-throughput sequencing data","volume":"8","author":"Campagne","year":"2013","journal-title":"PLoS One"},{"key":"2023020115111879100_btv071-B10","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":"2023020115111879100_btv071-B11","article-title":"Grammar-based compression of DNA sequences","author":"Cherniavsky","year":"2004","journal-title":"Technical Report"},{"key":"2023020115111879100_btv071-B12","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":"2023020115111879100_btv071-B13","doi-asserted-by":"crossref","first-page":"i283","DOI":"10.1093\/bioinformatics\/btt214","article-title":"Compressive genomics for protein databases","volume":"29","author":"Daniels","year":"2013","journal-title":"Bioinformatics"},{"key":"2023020115111879100_btv071-B14","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1006\/ciun.1994.1018","article-title":"S+-trees: an efficient structure for the representation of large pictures","volume":"59","author":"de Jonge","year":"1994","journal-title":"CVGIP: Imag. Understan."},{"key":"2023020115111879100_btv071-B15","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":"2023020115111879100_btv071-B16","doi-asserted-by":"crossref","first-page":"1251","DOI":"10.1101\/gr.172809.114","article-title":"Loss of transcriptional control over endogenous retroelements during reprogramming to pluripotency","volume":"24","author":"Friedli","year":"2014","journal-title":"Genome Res"},{"key":"2023020115111879100_btv071-B17","doi-asserted-by":"crossref","first-page":"734","DOI":"10.1101\/gr.114819.110","article-title":"Efficient storage of high throughput DNA sequencing data using reference-based compression","volume":"21","author":"Fritz","year":"2011","journal-title":"Genome Res."},{"key":"2023020115111879100_btv071-B18","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":"2023020115111879100_btv071-B19","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1038\/ng.1028","article-title":"De\u00a0novo assembly and genotyping of variants using colored de Bruijn graphs","volume":"44","author":"Iqbal","year":"2012","journal-title":"Nat. Genet."},{"key":"2023020115111879100_btv071-B20","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":"2023020115111879100_btv071-B21","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":"2023020115111879100_btv071-B22","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1186\/1471-2164-13-115","article-title":"Transcriptome landscape of the human placenta","volume":"13","author":"Kim","year":"2012","journal-title":"BMC Genomics"},{"key":"2023020115111879100_btv071-B23","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1089\/cmb.2010.0253","article-title":"Compressing genomic sequence fragments using SlimGene","volume":"18","author":"Kozanitis","year":"2011","journal-title":"J. Comput. Biol."},{"key":"2023020115111879100_btv071-B24","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":"2023020115111879100_btv071-B25","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":"2023020115111879100_btv071-B26","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":"2023020115111879100_btv071-B27","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1136\/amiajnl-2013-002147","article-title":"HUGO: hierarchical mUlti-reference Genome cOmpression for aligned reads","volume":"21","author":"Li","year":"2014","journal-title":"J. Am. Med. Inform. Assoc."},{"key":"2023020115111879100_btv071-B28","doi-asserted-by":"crossref","first-page":"627","DOI":"10.1038\/nbt.2241","article-title":"Compressive genomics","volume":"30","author":"Loh","year":"2012","journal-title":"Nat. Biotechnol."},{"key":"2023020115111879100_btv071-B29","first-page":"43","article-title":"Biological sequence compression algorithms","volume":"11","author":"Matsumoto","year":"2000","journal-title":"Genome Inform. Ser. Workshop Genome Inform."},{"key":"2023020115111879100_btv071-B30","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1145\/290159.290162","article-title":"Arithmetic coding revisited","volume":"16","author":"Moffat","year":"1998","journal-title":"ACM Trans. Inform. Syst."},{"key":"2023020115111879100_btv071-B31","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1186\/1471-2105-14-187","article-title":"QualComp: a new lossy compressor for quality scores based on rate distortion theory","volume":"14","author":"Ochoa","year":"2013","journal-title":"BMC Bioinformatics"},{"key":"2023020115111879100_btv071-B32","doi-asserted-by":"crossref","first-page":"462","DOI":"10.1038\/nbt.2862","article-title":"Sailfish enables alignment-free isoform quantification from RNA-seq reads using lightweight algorithms","volume":"32","author":"Patro","year":"2014","journal-title":"Nat. Biotechnol."},{"key":"2023020115111879100_btv071-B33","doi-asserted-by":"crossref","first-page":"9748","DOI":"10.1073\/pnas.171285098","article-title":"An Eulerian path approach to DNA fragment assembly","volume":"98","author":"Pevzner","year":"2001","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023020115111879100_btv071-B34","doi-asserted-by":"crossref","first-page":"e27","DOI":"10.1093\/nar\/gks939","article-title":"NGC: lossless and lossy compression of aligned high-throughput sequencing data","volume":"41","author":"Popitsch","year":"2013","journal-title":"Nucleic Acids Res."},{"key":"2023020115111879100_btv071-B35","doi-asserted-by":"crossref","first-page":"350","DOI":"10.6026\/97320630005350","article-title":"DNABIT Compress\u2014genome compression algorithm","volume":"5","author":"Rajarajeswari","year":"2011","journal-title":"Bioinformation"},{"key":"2023020115111879100_btv071-B36","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1147\/rd.232.0149","article-title":"Arithmetic coding","volume":"23","author":"Rissanen","year":"1979","journal-title":"IBM J. Res. Dev."},{"key":"2023020115111879100_btv071-B37","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1038\/nmeth.2251","article-title":"Streaming fragment assignment for real-time analysis of sequencing experiments","volume":"10","author":"Roberts","year":"2013","journal-title":"Nat. Methods"},{"key":"2023020115111879100_btv071-B38","doi-asserted-by":"crossref","DOI":"10.1109\/DCC.2014.89","article-title":"Compressing sets and multisets of sequences","author":"Steinruecken","year":"2014"},{"key":"2023020115111879100_btv071-B39","doi-asserted-by":"crossref","first-page":"2192","DOI":"10.1093\/bioinformatics\/btq346","article-title":"G-SQZ: compact encoding of genomic sequence and quality data","volume":"26","author":"Tembe","year":"2010","journal-title":"Bioinformatics"},{"key":"2023020115111879100_btv071-B40","doi-asserted-by":"crossref","first-page":"D596","DOI":"10.1093\/nar\/gkq869","article-title":"Pseudomonas Genome Database: improved comparative analysis and population genomics capability for Pseudomonas genomes","volume":"39","author":"Winsor","year":"2011","journal-title":"Nucleic Acids Res."},{"key":"2023020115111879100_btv071-B41","doi-asserted-by":"crossref","first-page":"520","DOI":"10.1145\/214762.214771","article-title":"Arithmetic coding for data compression","volume":"30","author":"Witten","year":"1987","journal-title":"Comm. ACM"},{"key":"2023020115111879100_btv071-B42","doi-asserted-by":"crossref","first-page":"R46","DOI":"10.1186\/gb-2014-15-3-r46","article-title":"Kraken: ultrafast metagenomic sequence classification using exact alignments","volume":"15","author":"Wood","year":"2014","journal-title":"Genome Biol."},{"key":"2023020115111879100_btv071-B43","doi-asserted-by":"crossref","first-page":"593","DOI":"10.1038\/nature12364","article-title":"Genetic programs in human and mouse early embryos revealed by single-cell RNA sequencing","volume":"500","author":"Xue","year":"2013","journal-title":"Nature"},{"key":"2023020115111879100_btv071-B44","doi-asserted-by":"crossref","first-page":"1131","DOI":"10.1038\/nsmb.2660","article-title":"Single-cell RNA-Seq profiling of human preimplantation embryos and embryonic stem cells","volume":"20","author":"Yan","year":"2013","journal-title":"Nat. Struct. Mol. Biol."},{"key":"2023020115111879100_btv071-B45","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-05269-4_31","article-title":"Traversing the k-mer landscape of NGS read datasets for quality score sparsification","volume-title":"Research in Computational Molecular Biology","author":"Yu","year":"2014"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/31\/12\/1920\/49014023\/bioinformatics_31_12_1920.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/31\/12\/1920\/49014023\/bioinformatics_31_12_1920.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,1]],"date-time":"2023-02-01T19:03:00Z","timestamp":1675278180000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/31\/12\/1920\/214016"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,2,2]]},"references-count":45,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2015,6,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btv071","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/006551","asserted-by":"object"}]},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2015,6,15]]},"published":{"date-parts":[[2015,2,2]]}}}