@article{Will_Otto_Miladi-SPARS_quadr_time-2015,
author = {Will, Sebastian and Otto, Christina and Miladi, Milad and 
          Möhl, Mathias and Backofen, Rolf},
title = {{SPARSE}: quadratic time simultaneous alignment and folding 
         of {RNAs} without sequence-based heuristics},
journal = {Bioinformatics},
year = {2015},
doi = {10.1093/bioinformatics/btv185},
volume = {31},
user = {wrightp},
pmid = {25838465},
pages = {2489-2496},
number = {15},
issn = {1367-4811},
abstract = {MOTIVATION: 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. AVAILABILITY AND IMPLEMENTATION: 
            SPARSE is freely available at 
            http://www.bioinf.uni-freiburg.de/Software/SPARSE. CONTACT: 
            backofen@informatik.uni-freiburg.de Supplementary 
            information: Supplementary data are available at 
            Bioinformatics online.}
}