title: Reference-based compression of short-read sequences using path encoding.
abstract: BACKGROUND
  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.
  
  
  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-11% 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.
  
  
  METHODS
  Source code and binaries freely available for download at http://www.cs.cmu.edu/∼ckingsf/software/pathenc/, implemented in Go and supported on Linux and Mac OS X.
authors: Department of Computational Biology, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, USA and Department of Computer Science, Stony Brook University, Stony Brook, NY 11794-4400, USA.
authors: Carl
authors: C
authors: Kingsford
authors: Department of Computational Biology, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, USA and Department of Computer Science, Stony Brook University, Stony Brook, NY 11794-4400, USA.
authors: Rob
authors: R
authors: Patro
mesh_terms: D000465:Algorithms; D000818:Animals; D019295:Computational Biology / Q000379:methods*; D044962:Data Compression / Q000379:methods*; D023281:Genomics / Q000379:methods*; D059014:High-Throughput Nucleotide Sequencing / Q000379:methods*; D006801:Humans; D051379:Mice; D011381:Programming Languages; D011550:Pseudomonas aeruginosa / Q000235:genetics; D016415:Sequence Alignment; D012984:Software
references: Proc Natl Acad Sci U S A. 2001 Aug 14;98(17):9748-53
references: 11504945
references: Genome Inform Ser Workshop Genome Inform. 2000;11:43-52
references: 11700586
references: Proc IEEE Comput Soc Bioinform Conf. 2002;1:303-13
references: 15838146
references: Genome Biol. 2009;10(3):R25
references: 19261174
references: Bioinformatics. 2009 Jul 15;25(14):1731-8
references: 19447783
references: Bioinformatics. 2009 Jul 15;25(14):1754-60
references: 19451168
references: Bioinformatics. 2009 Aug 15;25(16):2078-9
references: 19505943
references: BMC Bioinformatics. 2010 Feb 18;11:94
references: 20167110
references: Bioinformatics. 2010 Sep 1;26(17):2192-4
references: 20605925
references: Nucleic Acids Res. 2011 Jan;39(Database issue):D596-600
references: 20929876
references: Genome Res. 2011 May;21(5):734-40
references: 21245279
references: Bioinformatics. 2011 Mar 15;27(6):860-2
references: 21252073
references: Bioinformation. 2011 Jan 22;5(8):350-60
references: 21383923
references: J Comput Biol. 2011 Mar;18(3):401-13
references: 21385043
references: Nat Genet. 2012 Jan 08;44(2):226-32
references: 22231483
references: Bioinformatics. 2012 May 15;28(10):1324-7
references: 22419786
references: BMC Genomics. 2012 Mar 27;13:115
references: 22448651
references: Bioinformatics. 2012 Jun 1;28(11):1415-9
references: 22556365
references: Nat Biotechnol. 2012 Jul 10;30(7):627-30
references: 22781691
references: Nucleic Acids Res. 2012 Dec;40(22):e171
references: 22904078
references: Bioinformatics. 2012 Dec 1;28(23):3051-7
references: 23047557
references: Nucleic Acids Res. 2013 Jan 7;41(1):e27
references: 23066097
references: Nat Methods. 2013 Jan;10(1):71-3
references: 23160280
references: PLoS One. 2013;8(3):e59190
references: 23533605
references: BMC Bioinformatics. 2013 Jun 08;14:187
references: 23758828
references: Bioinformatics. 2013 Jul 1;29(13):i283-90
references: 23812995
references: Nature. 2013 Aug 29;500(7464):593-7
references: 23892778
references: Nat Struct Mol Biol. 2013 Sep;20(9):1131-9
references: 23934149
references: PLoS One. 2013 Nov 18;8(11):e79871
references: 24260313
references: J Am Med Inform Assoc. 2014 Mar-Apr;21(2):363-73
references: 24368726
references: Genome Biol. 2014 Mar 03;15(3):R46
references: 24580807
references: Bioinformatics. 2014 Aug 1;30(15):2130-6
references: 24728856
references: Nat Biotechnol. 2014 May;32(5):462-4
references: 24752080
references: Genome Res. 2014 Aug;24(8):1251-9
references: 24879558
references: Bioinformatics. 2014 Oct;30(19):2818-9
references: 24930138
references: Bioinformatics. 2014 Oct;30(19):2796-801
references: 24950811
references: Res Comput Mol Biol. 2014 Apr;8394:385-399
references: 28825060