{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,18]],"date-time":"2026-09-18T01:45:16Z","timestamp":1789695916006,"version":"4.0.1"},"reference-count":29,"publisher":"Oxford University Press (OUP)","issue":"15","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":549,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015,8,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>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 O(n6). Subsequently, numerous faster \u2018Sankoff-style\u2019 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 (\u2265 quartic time).<\/jats:p>\n               <jats:p>Results: Breaking this barrier, we introduce the novel Sankoff-style algorithm \u2018sparsified prediction and alignment of RNAs based on their structure ensembles (SPARSE)\u2019, 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\u2019s 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.<\/jats:p>\n               <jats:p>Availability and implementation: SPARSE is freely available at http:\/\/www.bioinf.uni-freiburg.de\/Software\/SPARSE.<\/jats:p>\n               <jats:p>Contact: \u00a0backofen@informatik.uni-freiburg.de<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btv185","type":"journal-article","created":{"date-parts":[[2015,4,3]],"date-time":"2015-04-03T14:32:57Z","timestamp":1428071577000},"page":"2489-2496","source":"Crossref","is-referenced-by-count":43,"title":["SPARSE: quadratic time simultaneous alignment and folding of RNAs without sequence-based heuristics"],"prefix":"10.1093","volume":"31","author":[{"given":"Sebastian","family":"Will","sequence":"first","affiliation":[{"name":"1 Bioinformatics, Department of Computer Science, University of Freiburg, Freiburg, Germany,"},{"name":"2 Bioinformatics, Department of Computer Science, University of Leipzig, Leipzig, Germany,"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christina","family":"Otto","sequence":"additional","affiliation":[{"name":"1 Bioinformatics, Department of Computer Science, University of Freiburg, Freiburg, Germany,"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Milad","family":"Miladi","sequence":"additional","affiliation":[{"name":"1 Bioinformatics, Department of Computer Science, University of Freiburg, Freiburg, Germany,"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mathias","family":"M\u00f6hl","sequence":"additional","affiliation":[{"name":"1 Bioinformatics, Department of Computer Science, University of Freiburg, Freiburg, Germany,"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rolf","family":"Backofen","sequence":"additional","affiliation":[{"name":"1 Bioinformatics, Department of Computer Science, University of Freiburg, Freiburg, Germany,"},{"name":"3 Centre for Biological Systems Analysis (ZBSA), University of Freiburg, Freiburg, Germany,"},{"name":"4 Centre for Non-coding RNA in Technology and Health, University of Copenhagen, Copenhagen, Denmark and"},{"name":"5 Centre for Biological Signalling Studies (BIOSS), University of Freiburg, Freiburg, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2015,4,2]]},"reference":[{"key":"2023051308492550500_btv185-B1","doi-asserted-by":"crossref","first-page":"474","DOI":"10.1186\/1471-2105-9-474","article-title":"RNAalifold: improved consensus structure prediction for RNA alignments","volume":"9","author":"Bernhart","year":"2008","journal-title":"BMC Bioinformatics"},{"key":"2023051308492550500_btv185-B2","volume-title":"Graphical Methods for Data Analysis","author":"Chambers","year":"1983"},{"key":"2023051308492550500_btv185-B3","doi-asserted-by":"crossref","DOI":"10.1371\/journal.pbio.1000625","article-title":"The reality of pervasive transcription","volume":"9","author":"Clark","year":"2011","journal-title":"PLoS Biol"},{"key":"2023051308492550500_btv185-B4","doi-asserted-by":"crossref","first-page":"54","DOI":"10.2307\/2683591","article-title":"Lowess: a program for smoothing scatterplots by robust locally weighted regression","volume":"35","author":"Cleveland","year":"1981","journal-title":"Am. Stat."},{"key":"2023051308492550500_btv185-B5","doi-asserted-by":"crossref","first-page":"i68","DOI":"10.1093\/bioinformatics\/btn177","article-title":"A max-margin model for efficient simultaneous alignment and folding of RNA sequences","volume":"24","author":"Do","year":"2008","journal-title":"Bioinformatics"},{"key":"2023051308492550500_btv185-B6","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1186\/1471-2105-7-400","article-title":"Efficient pairwise RNA structure prediction and alignment using sequence alignment constraints","volume":"7","author":"Dowell","year":"2006","journal-title":"BMC Bioinformatics"},{"key":"2023051308492550500_btv185-B7","doi-asserted-by":"crossref","first-page":"2433","DOI":"10.1093\/nar\/gki541","article-title":"A benchmark of multiple sequence alignment programs upon structural RNAs","volume":"33","author":"Gardner","year":"2005","journal-title":"Nucleic Acids Res."},{"key":"2023051308492550500_btv185-B8","doi-asserted-by":"crossref","first-page":"705","DOI":"10.1016\/0022-2836(82)90398-9","article-title":"An improved algorithm for matching biological sequences","volume":"162","author":"Gotoh","year":"1982","journal-title":"J. Mol. Biol."},{"key":"2023051308492550500_btv185-B9","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/j.ipl.2007.07.002","article-title":"Optimal implementations of UPGMA and other common clustering algorithms","volume":"104","author":"Gronau","year":"2007","journal-title":"Inf. Process. Lett."},{"key":"2023051308492550500_btv185-B10","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1186\/1471-2105-8-130","article-title":"Efficient pairwise RNA structure prediction using probabilistic alignment constraints in Dynalign","volume":"8","author":"Harmanci","year":"2007","journal-title":"BMC Bioinformatics"},{"key":"2023051308492550500_btv185-B11","doi-asserted-by":"crossref","first-page":"1059","DOI":"10.1016\/S0022-2836(02)00308-X","article-title":"Secondary structure prediction for aligned RNA sequences","volume":"319","author":"Hofacker","year":"2002","journal-title":"J. Mol. Biol."},{"key":"2023051308492550500_btv185-B12","doi-asserted-by":"crossref","first-page":"2222","DOI":"10.1093\/bioinformatics\/bth229","article-title":"Alignment of RNA base pairing probability matrices","volume":"20","author":"Hofacker","year":"2004","journal-title":"Bioinformatics"},{"key":"2023051308492550500_btv185-B13","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1186\/1471-2105-6-73","article-title":"Accelerated probabilistic inference of RNA structure evolution","volume":"6","author":"Holmes","year":"2005","journal-title":"BMC Bioinformatics"},{"key":"2023051308492550500_btv185-B14","doi-asserted-by":"crossref","first-page":"833","DOI":"10.1038\/nrg2683","article-title":"The complex eukaryotic transcriptome: unexpected pervasive transcription and novel small RNAs","volume":"10","author":"Jacquier","year":"2009","journal-title":"Nat. Rev. Genet."},{"key":"2023051308492550500_btv185-B15","doi-asserted-by":"crossref","first-page":"911","DOI":"10.1006\/jmbi.1999.2700","article-title":"Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structure","volume":"288","author":"Mathews","year":"1999","journal-title":"J. Mol. Biol."},{"key":"2023051308492550500_btv185-B16","first-page":"442","article-title":"Comparison of the predicted and observed secondary structure of t4 phage lysozyme","volume":"405","author":"Matthews","year":"1975","journal-title":"Biochem. Biophys. Acta"},{"key":"2023051308492550500_btv185-B17","doi-asserted-by":"crossref","first-page":"1105","DOI":"10.1002\/bip.360290621","article-title":"The equilibrium partition function and base pair binding probabilities for RNA secondary structure","volume":"29","author":"McCaskill","year":"1990","journal-title":"Biopolymers"},{"key":"2023051308492550500_btv185-B18","doi-asserted-by":"crossref","first-page":"6602","DOI":"10.1186\/s12859-014-0404-0","article-title":"ExpaRNA-P: simultaneous exact pattern matching and folding of RNAs","volume":"15","author":"Otto","year":"2014","journal-title":"BMC Bioinformatics"},{"key":"2023051308492550500_btv185-B19","doi-asserted-by":"crossref","first-page":"1929","DOI":"10.1101\/gr.112516.110","article-title":"New families of human regulatory RNA structures identified by comparative analysis of vertebrate genomes","volume":"21","author":"Parker","year":"2011","journal-title":"Genome Res"},{"key":"2023051308492550500_btv185-B20","doi-asserted-by":"crossref","first-page":"e113","DOI":"10.1093\/nar\/gkq057","article-title":"RNPomics: defining the ncRNA transcriptome by cDNA library generation from ribonucleo-protein particles","volume":"38","author":"Rederstorff","year":"2010","journal-title":"Nucleic Acids Res."},{"key":"2023051308492550500_btv185-B21","doi-asserted-by":"crossref","first-page":"S48","DOI":"10.1186\/1471-2105-12-S1-S48","article-title":"Fast and accurate clustering of noncoding RNAs using ensembles of sequence alignments and secondary structures","volume":"12","author":"Saito","year":"2011","journal-title":"BMC Bioinformatics"},{"key":"2023051308492550500_btv185-B22","doi-asserted-by":"crossref","first-page":"810","DOI":"10.1137\/0145048","article-title":"Simultaneous solution of the RNA folding, alignment and protosequence problems","volume":"45","author":"Sankoff","year":"1985","journal-title":"SIAM J. Appl. Math."},{"key":"2023051308492550500_btv185-B23","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1038\/nature08055","article-title":"Metatranscriptomics reveals unique microbial small RNAs in the ocean\u2019s water column","volume":"459","author":"Shi","year":"2009","journal-title":"Nature"},{"key":"2023051308492550500_btv185-B24","doi-asserted-by":"crossref","first-page":"W49","DOI":"10.1093\/nar\/gks491","article-title":"CARNA\u2014alignment of RNA structure ensembles","volume":"40","author":"Sorescu","year":"2012","journal-title":"Nucleic Acids Res."},{"key":"2023051308492550500_btv185-B25","doi-asserted-by":"crossref","first-page":"926","DOI":"10.1093\/bioinformatics\/btm049","article-title":"Multiple structural alignment and clustering of RNA sequences","volume":"23","author":"Torarinsson","year":"2007","journal-title":"Bioinformatics"},{"key":"2023051308492550500_btv185-B26","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1142\/S0219720009004126","article-title":"Finding non-coding RNAs through genome-scale clustering","volume":"7","author":"Tseng","year":"2009","journal-title":"J. Bioinform. Comput. Biol."},{"key":"2023051308492550500_btv185-B27","doi-asserted-by":"crossref","first-page":"e65","DOI":"10.1371\/journal.pcbi.0030065","article-title":"Inferring non-coding RNA families and classes by means of genome-scale structure-based clustering","volume":"3","author":"Will","year":"2007","journal-title":"PLoS Comput. Biol."},{"key":"2023051308492550500_btv185-B28","doi-asserted-by":"crossref","first-page":"900","DOI":"10.1261\/rna.029041.111","article-title":"LocARNA-P: accurate boundary prediction and improved detection of structural RNAs","volume":"18","author":"Will","year":"2012","journal-title":"RNA"},{"key":"2023051308492550500_btv185-B29","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1186\/1748-7188-1-19","article-title":"An enhanced RNA alignment benchmark for sequence alignment programs","volume":"1","author":"Wilm","year":"2006","journal-title":"Algorithms Mol. Biol."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/31\/15\/2489\/50306952\/bioinformatics_31_15_2489.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/31\/15\/2489\/50306952\/bioinformatics_31_15_2489.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,13]],"date-time":"2023-05-13T08:50:25Z","timestamp":1683967825000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/31\/15\/2489\/188821"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4,2]]},"references-count":29,"journal-issue":{"issue":"15","published-print":{"date-parts":[[2015,8,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btv185","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2015,8,1]]},"published":{"date-parts":[[2015,4,2]]}}}