title: SPARSE: quadratic time simultaneous alignment and folding of RNAs without sequence-based heuristics.
abstract: BACKGROUND
  RNA-Seq experiments have revealed a multitude of novel ncRNAs. The gold standard for their analysis based on simultaneous alignment and folding suffers from extreme time complexity of [Formula: see text]. Subsequently, numerous faster 'Sankoff-style' approaches have been suggested. Commonly, the performance of such methods relies on sequence-based heuristics that restrict the search space to optimal or near-optimal sequence alignments; however, the accuracy of sequence-based methods breaks down for RNAs with sequence identities below 60%. Alignment approaches like LocARNA that do not require sequence-based heuristics, have been limited to high complexity ([Formula: see text] quartic time).
  
  
  RESULTS
  Breaking this barrier, we introduce the novel Sankoff-style algorithm 'sparsified prediction and alignment of RNAs based on their structure ensembles (SPARSE)', which runs in quadratic time without sequence-based heuristics. To achieve this low complexity, on par with sequence alignment algorithms, SPARSE features strong sparsification based on structural properties of the RNA ensembles. Following PMcomp, SPARSE gains further speed-up from lightweight energy computation. Although all existing lightweight Sankoff-style methods restrict Sankoff's original model by disallowing loop deletions and insertions, SPARSE transfers the Sankoff algorithm to the lightweight energy model completely for the first time. Compared with LocARNA, SPARSE achieves similar alignment and better folding quality in significantly less time (speedup: 3.7). At similar run-time, it aligns low sequence identity instances substantially more accurate than RAF, which uses sequence-based heuristics.
authors.affiliation: Bioinformatics, Department of Computer Science, University of Freiburg, Freiburg, Germany, Bioinformatics, Department of Computer Science, University of Leipzig, Leipzig, Germany.
authors.forename: Sebastian
authors.initials: S
authors.lastname: Will
authors.affiliation: Bioinformatics, Department of Computer Science, University of Freiburg, Freiburg, Germany.
authors.forename: Christina
authors.initials: C
authors.lastname: Otto
authors.affiliation: Bioinformatics, Department of Computer Science, University of Freiburg, Freiburg, Germany.
authors.forename: Milad
authors.initials: M
authors.lastname: Miladi
authors.affiliation: Bioinformatics, Department of Computer Science, University of Freiburg, Freiburg, Germany.
authors.forename: Mathias
authors.initials: M
authors.lastname: Möhl
authors.affiliation: Bioinformatics, Department of Computer Science, University of Freiburg, Freiburg, Germany, Centre for Biological Systems Analysis (ZBSA), University of Freiburg, Freiburg, Germany, Centre for Non-coding RNA in Technology and Health, University of Copenhagen, Copenhagen, Denmark and Centre for Biological Signalling Studies (BIOSS), University of Freiburg, Freiburg, Germany.
authors.forename: Rolf
authors.initials: R
authors.lastname: Backofen
mesh_terms: D000465:Algorithms; D000066506:Heuristics; D059370:RNA Folding; D016415:Sequence Alignment / Q000379:methods*; D017423:Sequence Analysis, RNA / Q000379:methods*
references.citation: Nucleic Acids Res. 2012 Jul;40(Web Server issue):W49-53
references.pmid: 22689637
references.citation: BMC Bioinformatics. 2008;9:474
references.pmid: 19014431
references.citation: PLoS Biol. 2011 Jul;9(7):e1000625; discussion e1001102
references.pmid: 21765801
references.citation: Nature. 2009 May 14;459(7244):266-9
references.pmid: 19444216
references.citation: PLoS Comput Biol. 2007 Apr 13;3(4):e65
references.pmid: 17432929
references.citation: J Mol Biol. 1982 Dec 15;162(3):705-8
references.pmid: 7166760
references.citation: J Mol Biol. 2002 Jun 21;319(5):1059-66
references.pmid: 12079347
references.citation: RNA. 2012 May;18(5):900-14
references.pmid: 22450757
references.citation: Nat Rev Genet. 2009 Dec;10(12):833-44
references.pmid: 19920851
references.citation: Bioinformatics. 2004 Sep 22;20(14):2222-7
references.pmid: 15073017
references.citation: BMC Bioinformatics. 2006;7:400
references.pmid: 16952317
references.citation: Genome Res. 2011 Nov;21(11):1929-43
references.pmid: 21994249
references.citation: Algorithms Mol Biol. 2006 Oct 24;1:19
references.pmid: 17062125
references.citation: BMC Bioinformatics. 2007;8:130
references.pmid: 17445273
references.citation: Bioinformatics. 2008 Jul 1;24(13):i68-76
references.pmid: 18586747
references.citation: Biochim Biophys Acta. 1975 Oct 20;405(2):442-51
references.pmid: 1180967
references.citation: Biopolymers. 1990 May-Jun;29(6-7):1105-19
references.pmid: 1695107
references.citation: Nucleic Acids Res. 2005;33(8):2433-9
references.pmid: 15860779
references.citation: BMC Bioinformatics. 2014;15:404
references.pmid: 25551362
references.citation: BMC Bioinformatics. 2011;12 Suppl 1:S48
references.pmid: 21342580
references.citation: Bioinformatics. 2007 Apr 15;23(8):926-32
references.pmid: 17324941
references.citation: J Bioinform Comput Biol. 2009 Apr;7(2):373-88
references.pmid: 19340921
references.citation: Nucleic Acids Res. 2010 Jun;38(10):e113
references.pmid: 20150415
references.citation: J Mol Biol. 1999 May 21;288(5):911-40
references.pmid: 10329189
references.citation: BMC Bioinformatics. 2005;6:73
references.pmid: 15790387