{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T21:13:53Z","timestamp":1757452433829},"reference-count":32,"publisher":"Oxford University Press (OUP)","issue":"5","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":2453,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/2.0\/uk\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010,3,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Abstract shape analysis allows efficient computation of a representative sample of low-energy foldings of an RNA molecule. More comprehensive information is obtained by computing shape probabilities, accumulating the Boltzmann probabilities of all structures within each abstract shape. Such information is superior to free energies because it is independent of sequence length and base composition. However, up to this point, computation of shape probabilities evaluates all shapes simultaneously and comes with a computation cost which is exponential in the length of the sequence.<\/jats:p>\n               <jats:p>Results: We device an approach called RapidShapes that computes the shapes above a specified probability threshold T by generating a list of promising shapes and constructing specialized folding programs for each shape to compute its share of Boltzmann probability. This aims at a heuristic improvement of runtime, while still computing exact probability values.<\/jats:p>\n               <jats:p>Conclusion: Evaluating this approach and several substrategies, we find that only a small proportion of shapes have to be actually computed. For an RNA sequence of length 400, this leads, depending on the threshold, to a 10\u2013138 fold speed-up compared with the previous complete method. Thus, probabilistic shape analysis has become feasible in medium-scale applications, such as the screening of RNA transcripts in a bacterial genome.<\/jats:p>\n               <jats:p>Availability: \u00a0RapidShapes is available via http:\/\/bibiserv.cebitec.uni-bielefeld.de\/rnashapes<\/jats:p>\n               <jats:p>Contact: \u00a0robert@techfak.uni-bielefeld.de<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btq014","type":"journal-article","created":{"date-parts":[[2010,1,16]],"date-time":"2010-01-16T01:14:00Z","timestamp":1263604440000},"page":"632-639","source":"Crossref","is-referenced-by-count":18,"title":["Faster computation of exact RNA shape probabilities"],"prefix":"10.1093","volume":"26","author":[{"given":"Stefan","family":"Janssen","sequence":"first","affiliation":[{"name":"Practical Computer Science, Faculty of Technology, Bielefeld University, D-33615 Bielefeld, Germany"}]},{"given":"Robert","family":"Giegerich","sequence":"additional","affiliation":[{"name":"Practical Computer Science, Faculty of Technology, Bielefeld University, D-33615 Bielefeld, Germany"}]}],"member":"286","published-online":{"date-parts":[[2010,1,14]]},"reference":[{"key":"2023012511004116100_B1","doi-asserted-by":"crossref","first-page":"i19","DOI":"10.1093\/bioinformatics\/btm223","article-title":"Efficient parameter estimation for RNA secondary structure prediction","volume":"23","author":"Andronescu","year":"2007","journal-title":"Bioinformatics"},{"key":"2023012511004116100_B2","doi-asserted-by":"crossref","first-page":"1289","DOI":"10.1101\/gr.5159906","article-title":"Many novel mammalian microRNA candidates identified by extensive cloning and RAKE analysis","volume":"16","author":"Berezikov","year":"2006","journal-title":"Genome Res."},{"key":"2023012511004116100_B3","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":"2023012511004116100_B4","doi-asserted-by":"crossref","first-page":"1060","DOI":"10.1016\/j.jcss.2007.03.011","article-title":"The most probable annotation problem in HMMs and its application to bioinformatics","volume":"73","author":"Brejov\u00e1","year":"2007","journal-title":"J. Comput. Syst. Sci."},{"key":"2023012511004116100_B5","doi-asserted-by":"crossref","first-page":"3209","DOI":"10.1073\/pnas.0712329105","article-title":"Centroid estimation in discrete high-dimensional spaces with applications in biology","volume":"105","author":"Carvalho","year":"2008","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023012511004116100_B6","doi-asserted-by":"crossref","first-page":"3926","DOI":"10.1093\/bioinformatics\/bti632","article-title":"Structure clustering features on the Sfold Web server","volume":"21","author":"Chan","year":"2005","journal-title":"Bioinformatics"},{"key":"2023012511004116100_B7","doi-asserted-by":"crossref","first-page":"578","DOI":"10.1261\/rna.7220505","article-title":"Structural RNA has lower folding energy than random RNA of the same dinucleotide frequency","volume":"11","author":"Clote","year":"2005","journal-title":"RNA"},{"key":"2023012511004116100_B8","doi-asserted-by":"crossref","first-page":"7280","DOI":"10.1093\/nar\/gkg938","article-title":"A statistical sampling algorithm for RNA secondary structure prediction","volume":"31","author":"Ding","year":"2003","journal-title":"Nucleic Acids Res."},{"key":"2023012511004116100_B9","doi-asserted-by":"crossref","first-page":"e90","DOI":"10.1093\/bioinformatics\/btl246","article-title":"CONTRAfold: RNA secondary structure prediction without physics-based models","volume":"22","author":"Do","year":"2006","journal-title":"Bioinformatics"},{"key":"2023012511004116100_B10","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1186\/1471-2105-5-105","article-title":"Evaluation of the suitability of free-energy minimization using nearest-neighbor energy parameters for RNA secondary structure prediction","volume":"5","author":"Doshi","year":"2004","journal-title":"BMC Bioinformatics"},{"key":"2023012511004116100_B11","volume-title":"Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids","author":"Durbin","year":"1999"},{"key":"2023012511004116100_B12","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/j.scico.2003.12.005","article-title":"A discipline of dynamic programming over sequence data","volume":"51","author":"Giegerich","year":"2004","journal-title":"Sci. Comp. Program."},{"key":"2023012511004116100_B13","doi-asserted-by":"crossref","first-page":"4843","DOI":"10.1093\/nar\/gkh779","article-title":"Abstract Shapes of RNA","volume":"32","author":"Giegerich","year":"2004","journal-title":"Nucleic Acids Res."},{"key":"2023012511004116100_B14","doi-asserted-by":"crossref","first-page":"D121","DOI":"10.1093\/nar\/gki081","article-title":"Rfam: annotating non-coding RNAs in complete genomes","volume":"33","author":"Griffiths-Jones","year":"2005","journal-title":"Nucleic Acids Res."},{"key":"2023012511004116100_B15","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1093\/bioinformatics\/btn601","article-title":"Prediction of RNA secondary structure using generalized centroid estimators","volume":"25","author":"Hamada","year":"2009","journal-title":"Bioinformatics"},{"key":"2023012511004116100_B16","doi-asserted-by":"crossref","first-page":"1896","DOI":"10.1371\/journal.pcbi.0030193","article-title":"Fast pairwise structural RNA alignments by pruning of the dynamical programming matrix","volume":"3","author":"Havgaard","year":"2007","journal-title":"PLoS Comput. Biol."},{"key":"2023012511004116100_B17","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/BF00818163","article-title":"Fast folding and comparison of RNA secondary structures","volume":"125","author":"Hofacker","year":"1994","journal-title":"Monatsh. Chem."},{"key":"2023012511004116100_B18","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1186\/1471-2105-9-131","article-title":"Shape based indexing for faster search of RNA family databases","volume":"9","author":"Janssen","year":"2008","journal-title":"BMC Bioinformatics"},{"key":"2023012511004116100_B19","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1089\/cmb.2006.0153","article-title":"Asymptotics of RNA shapes","volume":"15","author":"Lorenz","year":"2008","journal-title":"J. Comput. Biol."},{"key":"2023012511004116100_B20","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1038\/ng.73","article-title":"The birth and death of microRNA genes in Drosophila","volume":"40","author":"Lu","year":"2008","journal-title":"Nat. Genet."},{"key":"2023012511004116100_B21","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1038\/nrm1403","article-title":"Gene regulation by riboswitches","volume":"5","author":"Mandal","year":"2004","journal-title":"Nat. Rev. Mol. Cell Biol."},{"key":"2023012511004116100_B22","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":"2023012511004116100_B23","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1016\/j.sbi.2006.05.010","article-title":"Prediction of RNA secondary structure by free energy minimization","volume":"16","author":"Mathews","year":"2006","journal-title":"Curr. Opin. Struct. Biol."},{"key":"2023012511004116100_B24","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":"2023012511004116100_B25","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1186\/1471-2199-5-10","article-title":"Co-transcriptional folding is encoded within RNA genes","volume":"5","author":"Meyer","year":"2004","journal-title":"BMC Mol. Biol."},{"key":"2023012511004116100_B26","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1007\/s12064-009-0074-z","article-title":"On quantitative effects of RNA shape abstraction","volume":"128","author":"Nebel","year":"2009","journal-title":"Theory Biosci."},{"key":"2023012511004116100_B27","doi-asserted-by":"crossref","first-page":"i392","DOI":"10.1093\/bioinformatics\/btm179","article-title":"Locomotif: from graphical motif description to RNA motif search","volume":"23","author":"Reeder","year":"2007","journal-title":"Bioinformatics"},{"key":"2023012511004116100_B28","doi-asserted-by":"crossref","first-page":"3516","DOI":"10.1093\/bioinformatics\/bti577","article-title":"Consensus shapes: an alternative to the Sankoff algorithm for RNA consensus structure prediction","volume":"21","author":"Reeder","year":"2005","journal-title":"Bioinformatics"},{"key":"2023012511004116100_B29","doi-asserted-by":"crossref","first-page":"500","DOI":"10.1093\/bioinformatics\/btk010","article-title":"RNAshapes: an integrated RNA analysis package based on abstract shapes","volume":"22","author":"Steffen","year":"2006","journal-title":"Bioinformatics"},{"key":"2023012511004116100_B30","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1186\/1741-7007-4-5","article-title":"Complete probabilistic analysis of RNA shapes","volume":"4","author":"Vo\u00df","year":"2006","journal-title":"BMC Biol."},{"key":"2023012511004116100_B31","doi-asserted-by":"crossref","DOI":"10.4161\/rna.6.4.9014","article-title":"The Escherichia coli ibpA thermometer is comprised of stable and unstable structural elements","volume":"6","author":"Waldminghaus","year":"2009","journal-title":"RNA Biol."},{"key":"2023012511004116100_B32","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1002\/(SICI)1097-0282(199902)49:2<145::AID-BIP4>3.0.CO;2-G","article-title":"Complete suboptimal folding of RNA and the stability of secondary structures","volume":"49","author":"Wuchty","year":"1999","journal-title":"Biopolymers"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/26\/5\/632\/48860643\/bioinformatics_26_5_632.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/26\/5\/632\/48860643\/bioinformatics_26_5_632.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T11:03:21Z","timestamp":1674644601000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/26\/5\/632\/212857"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1,14]]},"references-count":32,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2010,3,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btq014","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2010,3,1]]},"published":{"date-parts":[[2010,1,14]]}}}