title: A memory-efficient algorithm to obtain splicing graphs and de novo expression estimates from de Bruijn graphs of RNA-Seq data.
abstract: BACKGROUND
  The recent advance of high-throughput sequencing makes it feasible to study entire transcriptomes through the application of de novo sequence assembly algorithms. While a popular strategy is to first construct an intermediate de Bruijn graph structure to represent the transcriptome, an additional step is needed to construct predicted transcripts from the graph.
  
  
  RESULTS
  Since the de Bruijn graph contains all branching possibilities, we develop a memory-efficient algorithm to recover alternative splicing information and library-specific expression information directly from the graph without prior genomic knowledge. We implement the algorithm as a postprocessing module of the Velvet assembler. We validate our algorithm by simulating the transcriptome assembly of Drosophila using its known genome, and by performing Drosophila transcriptome assembly using publicly available RNA-Seq libraries. Under a range of conditions, our algorithm recovers sequences and alternative splicing junctions with higher specificity than Oases or Trans-ABySS.
  
  
  CONCLUSIONS
  Since our postprocessing algorithm does not consume as much memory as Velvet and is less memory-intensive than Oases, it allows biologists to assemble large libraries with limited computational resources. Our algorithm has been applied to perform transcriptome assembly of the non-model blow fly Lucilia sericata that was reported in a previous article, which shows that the assembly is of high quality and it facilitates comparison of the Lucilia sericata transcriptome to Drosophila and two mosquitoes, prediction and experimental validation of alternative splicing, investigation of differential expression among various developmental stages, and identification of transposable elements.
authors.forename: Sing-Hoi
authors.initials: SH
authors.lastname: Sze
authors.forename: Aaron M
authors.initials: AM
authors.lastname: Tarone
mesh_terms: D000465:Algorithms; D017398:Alternative Splicing / Q000235:genetics; D000818:Animals; D004330:Drosophila / Q000235:genetics; D059014:High-Throughput Nucleotide Sequencing / Q000379:methods*; D020641:Polymorphism, Single Nucleotide; D017423:Sequence Analysis, RNA / Q000379:methods*; D012984:Software; D059467:Transcriptome
references.citation: Bioinformatics. 2002;18 Suppl 1:S181-8
references.pmid: 12169546
references.citation: Nat Biotechnol. 2010 May;28(5):511-5
references.pmid: 20436464
references.citation: Nat Biotechnol. 2011 May 15;29(7):644-52
references.pmid: 21572440
references.citation: Insect Mol Biol. 2012 Apr;21(2):205-21
references.pmid: 22283785
references.citation: Genome Res. 2011 Feb;21(2):315-24
references.pmid: 21177959
references.citation: Bioinformatics. 2009 Nov 1;25(21):2872-7
references.pmid: 19528083
references.citation: Bioinformatics. 2012 Apr 15;28(8):1086-92
references.pmid: 22368243
references.citation: Nat Methods. 2008 Jul;5(7):621-8
references.pmid: 18516045
references.citation: Genome Res. 2008 May;18(5):810-20
references.pmid: 18340039
references.citation: J Mol Biol. 1990 Oct 5;215(3):403-10
references.pmid: 2231712
references.citation: Genome Res. 2007 Nov;17(11):1697-706
references.pmid: 17908823
references.citation: Nat Methods. 2010 Nov;7(11):909-12
references.pmid: 20935650
references.citation: J Biomol Struct Dyn. 1989 Aug;7(1):63-73
references.pmid: 2684223
references.citation: Genome Res. 2008 Feb;18(2):324-30
references.pmid: 18083777
references.citation: J Comput Biol. 1995 Summer;2(2):291-306
references.pmid: 7497130
references.citation: Nucleic Acids Res. 2010 Jan;38(Database issue):D5-16
references.pmid: 19910364
references.citation: Genome Res. 2008 May;18(5):802-9
references.pmid: 18332092
references.citation: Genome Res. 2008 May;18(5):821-9
references.pmid: 18349386
references.citation: Genome Res. 2010 Feb;20(2):265-72
references.pmid: 20019144
references.citation: Bioinformatics. 2009 May 1;25(9):1105-11
references.pmid: 19289445