{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T01:12:06Z","timestamp":1773277926253,"version":"3.50.1"},"reference-count":37,"publisher":"Oxford University Press (OUP)","issue":"2","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":2515,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/2.5\/uk\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010,1,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: It has been proven that the accessibility of the target sites has a critical influence on RNA\u2013RNA binding, in general and the specificity and efficiency of miRNAs and siRNAs, in particular. Recently, O(N6) time and O(N4) space dynamic programming (DP) algorithms have become available that compute the partition function of RNA\u2013RNA interaction complexes, thereby providing detailed insights into their thermodynamic properties.<\/jats:p>\n               <jats:p>Results: Modifications to the grammars underlying earlier approaches enables the calculation of interaction probabilities for any given interval on the target RNA. The computation of the \u2018hybrid probabilities\u2019 is complemented by a stochastic sampling algorithm that produces a Boltzmann weighted ensemble of RNA\u2013RNA interaction structures. The sampling of k structures requires only negligible additional memory resources and runs in O(k\u00b7N3).<\/jats:p>\n               <jats:p>Availability: The algorithms described here are implemented in C as part of the rip package. The source code of rip2 can be downloaded from http:\/\/www.combinatorics.cn\/cbpc\/rip.html and http:\/\/www.bioinf.uni-leipzig.de\/Software\/rip.html.<\/jats:p>\n               <jats:p>Contact: \u00a0duck@santafe.edu<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btp635","type":"journal-article","created":{"date-parts":[[2009,11,13]],"date-time":"2009-11-13T01:15:00Z","timestamp":1258074900000},"page":"175-181","source":"Crossref","is-referenced-by-count":38,"title":["Target prediction and a statistical sampling algorithm for RNA\u2013RNA interaction"],"prefix":"10.1093","volume":"26","author":[{"given":"Fenix W. D.","family":"Huang","sequence":"first","affiliation":[{"name":"1 Center for Combinatorics, LPMC-TJKLC, 2 College of Life Science, Nankai University, Tianjin 300071, P. R. China, 3 Bioinformatics Group, Department of Computer Science, 4 Interdisciplinary Center for Bioinformatics, University of Leipzig, H\u00e4rtelstrasse 16-18, D-04107 Leipzig, 5 Max Planck Institute for Mathematics in the Sciences, Inselstrasse 22, 6 RNomics Group, Fraunhofer Institut for Cell Therapy and Immunology, Perlickstra\u00dfe 1, D-04103 Leipzig, Germany, 7 Institute for Theoretical Chemistry, University of Vienna, W\u00e4hringerstrasse 17, A-1090 Vienna, Austria and 8 The Santa Fe Institute, 1399 Hyde Park Rd., Santa Fe, NM, USA"}]},{"given":"Jing","family":"Qin","sequence":"additional","affiliation":[{"name":"1 Center for Combinatorics, LPMC-TJKLC, 2 College of Life Science, Nankai University, Tianjin 300071, P. R. China, 3 Bioinformatics Group, Department of Computer Science, 4 Interdisciplinary Center for Bioinformatics, University of Leipzig, H\u00e4rtelstrasse 16-18, D-04107 Leipzig, 5 Max Planck Institute for Mathematics in the Sciences, Inselstrasse 22, 6 RNomics Group, Fraunhofer Institut for Cell Therapy and Immunology, Perlickstra\u00dfe 1, D-04103 Leipzig, Germany, 7 Institute for Theoretical Chemistry, University of Vienna, W\u00e4hringerstrasse 17, A-1090 Vienna, Austria and 8 The Santa Fe Institute, 1399 Hyde Park Rd., Santa Fe, NM, USA"}]},{"given":"Christian M.","family":"Reidys","sequence":"additional","affiliation":[{"name":"1 Center for Combinatorics, LPMC-TJKLC, 2 College of Life Science, Nankai University, Tianjin 300071, P. R. China, 3 Bioinformatics Group, Department of Computer Science, 4 Interdisciplinary Center for Bioinformatics, University of Leipzig, H\u00e4rtelstrasse 16-18, D-04107 Leipzig, 5 Max Planck Institute for Mathematics in the Sciences, Inselstrasse 22, 6 RNomics Group, Fraunhofer Institut for Cell Therapy and Immunology, Perlickstra\u00dfe 1, D-04103 Leipzig, Germany, 7 Institute for Theoretical Chemistry, University of Vienna, W\u00e4hringerstrasse 17, A-1090 Vienna, Austria and 8 The Santa Fe Institute, 1399 Hyde Park Rd., Santa Fe, NM, USA"},{"name":"1 Center for Combinatorics, LPMC-TJKLC, 2 College of Life Science, Nankai University, Tianjin 300071, P. R. China, 3 Bioinformatics Group, Department of Computer Science, 4 Interdisciplinary Center for Bioinformatics, University of Leipzig, H\u00e4rtelstrasse 16-18, D-04107 Leipzig, 5 Max Planck Institute for Mathematics in the Sciences, Inselstrasse 22, 6 RNomics Group, Fraunhofer Institut for Cell Therapy and Immunology, Perlickstra\u00dfe 1, D-04103 Leipzig, Germany, 7 Institute for Theoretical Chemistry, University of Vienna, W\u00e4hringerstrasse 17, A-1090 Vienna, Austria and 8 The Santa Fe Institute, 1399 Hyde Park Rd., Santa Fe, NM, USA"}]},{"given":"Peter F.","family":"Stadler","sequence":"additional","affiliation":[{"name":"1 Center for Combinatorics, LPMC-TJKLC, 2 College of Life Science, Nankai University, Tianjin 300071, P. R. China, 3 Bioinformatics Group, Department of Computer Science, 4 Interdisciplinary Center for Bioinformatics, University of Leipzig, H\u00e4rtelstrasse 16-18, D-04107 Leipzig, 5 Max Planck Institute for Mathematics in the Sciences, Inselstrasse 22, 6 RNomics Group, Fraunhofer Institut for Cell Therapy and Immunology, Perlickstra\u00dfe 1, D-04103 Leipzig, Germany, 7 Institute for Theoretical Chemistry, University of Vienna, W\u00e4hringerstrasse 17, A-1090 Vienna, Austria and 8 The Santa Fe Institute, 1399 Hyde Park Rd., Santa Fe, NM, USA"}]}],"member":"286","published-online":{"date-parts":[[2009,11,13]]},"reference":[{"key":"2023012508173974400_B1","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/S0166-218X(00)00186-4","article-title":"Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots","volume":"104","author":"Akutsu","year":"2000","journal-title":"Disc. Appl. Math."},{"key":"2023012508173974400_B2","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1089\/cmb.2006.13.267","article-title":"RNA-RNA interaction prediction and antisense RNA target search","volume":"13","author":"Alkan","year":"2006","journal-title":"J. Comput. Biol."},{"key":"2023012508173974400_B3","doi-asserted-by":"crossref","first-page":"1101","DOI":"10.1016\/j.jmb.2004.10.082","article-title":"Secondary structure prediction of interacting RNA molecules","volume":"345","author":"Andronescu","year":"2005","journal-title":"J. Mol. Biol."},{"key":"2023012508173974400_B4","doi-asserted-by":"crossref","first-page":"1101","DOI":"10.1006\/jmbi.2000.3942","article-title":"fhlA repression by OxyS RNA: kissing complex formation at two sites results in a stable antisense-target RNA complex","volume":"300","author":"Argaman","year":"2000","journal-title":"J. Mol. Biol."},{"key":"2023012508173974400_B5","doi-asserted-by":"crossref","first-page":"775","DOI":"10.1016\/S0300-9084(02)01402-5","article-title":"The expanding snoRNA world","volume":"84","author":"Bachellerie","year":"2002","journal-title":"Biochimie"},{"key":"2023012508173974400_B6","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1002\/bies.10046","article-title":"Control of developmental timing by small temporal RNAs: a paradigm for RNA-mediated regulation of gene expression","volume":"24","author":"Banerjee","year":"2002","journal-title":"Bioessays"},{"key":"2023012508173974400_B7","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/BF00419661","article-title":"RNA editing in trypanosomes. the use of guide RNAs","volume":"16","author":"Benne","year":"1992","journal-title":"Mol. Biol. Rep."},{"key":"2023012508173974400_B8","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1186\/1748-7188-1-3","article-title":"Partition function and base pairing probabilities of RNA heterodimers","volume":"1","author":"Bernhart","year":"2006","journal-title":"Algorithms Mol. Biol."},{"key":"2023012508173974400_B9","doi-asserted-by":"crossref","first-page":"2849","DOI":"10.1093\/bioinformatics\/btn544","article-title":"IntaRNA: efficient prediction of bacterial sRNA targets incorporating target site accessibility and seed regions","volume":"24","author":"Busch","year":"2008","journal-title":"Bioinformatics"},{"key":"2023012508173974400_B10","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/978-3-642-04241-6_3","article-title":"biRNA: fast RNA-RNA binding sites prediction","volume-title":"Proceedings of the 9th Workshop on Algorithms in Bioinformatics (WABI)","author":"Chitsaz","year":"2009"},{"key":"2023012508173974400_B11","doi-asserted-by":"crossref","first-page":"i365","DOI":"10.1093\/bioinformatics\/btp212","article-title":"A partition function algorithm for interacting nucleic acid strands","volume":"25","author":"Chitsaz","year":"2009","journal-title":"Bioinformatics"},{"key":"2023012508173974400_B12","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 Acid Res."},{"key":"2023012508173974400_B13","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1137\/060651100","article-title":"Thermodynamic analysis of interacting nucleic acid strands","volume":"49","author":"Dirks","year":"2007","journal-title":"SIAM Rev."},{"key":"2023012508173974400_B14","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1186\/1471-2105-5-71","article-title":"Evaluation of several lightweight stochastic context-free grammars for RNA secondary structure prediction","volume":"5","author":"Dowell","year":"2004","journal-title":"BMC Bioinformatics"},{"key":"2023012508173974400_B15","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1038\/sj.emboj.7600058","article-title":"Hfq, a new chaperoning role: binding to messenger RNA determines access for small RNA regulator","volume":"23","author":"Geissmann","year":"2004","journal-title":"EMBO J."},{"key":"2023012508173974400_B16","first-page":"349","article-title":"Algebraic Dynamic Programming","volume-title":"Lecture Notes in Computer Science.","author":"Giegerich","year":"2002"},{"key":"2023012508173974400_B17","doi-asserted-by":"crossref","first-page":"129","DOI":"10.4161\/rna.6.2.8178","article-title":"Non-coding RNAs in polycomb\/trithorax regulation","volume":"6","author":"Hekimoglu","year":"2009","journal-title":"RNA Biol."},{"key":"2023012508173974400_B18","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":"2023012508173974400_B19","doi-asserted-by":"crossref","first-page":"2646","DOI":"10.1093\/bioinformatics\/btp481","article-title":"Partition function and base pairing probabilities for RNA-RNA interaction prediction","volume":"25","author":"Huang","year":"2009","journal-title":"Bioinformatics"},{"key":"2023012508173974400_B20","first-page":"89","article-title":"An RNA transcriptional regulator templates its own regulatory RNA","volume":"3","author":"Kugel","year":"2007","journal-title":"Nat. Struct. Mol. Biol."},{"key":"2023012508173974400_B21","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":"2023012508173974400_B22","doi-asserted-by":"crossref","first-page":"737","DOI":"10.1038\/nrg908","article-title":"Gene silencing in mammals by small interfering RNAs","volume":"3","author":"McManus","year":"2002","journal-title":"Nat. Rev."},{"key":"2023012508173974400_B23","doi-asserted-by":"crossref","first-page":"682","DOI":"10.1109\/TCBB.2007.70258","article-title":"On the approximation of optimal structures for RNA-RNA interaction","volume":"6","author":"Mneimneh","year":"2009","journal-title":"IEEE\/ACM Trans. Comp. Biol. Bioinform."},{"key":"2023012508173974400_B24","doi-asserted-by":"crossref","first-page":"1177","DOI":"10.1093\/bioinformatics\/btl024","article-title":"Thermodynamics of RNA-RNA binding","volume":"22","author":"M\u00fcckstein","year":"2006","journal-title":"Bioinformatics"},{"key":"2023012508173974400_B25","first-page":"114","article-title":"Translational control by RNA-RNA interaction: improved computation of RNA-RNA binding thermodynamics","volume-title":"Bioinformatics Research and Development \u2014 BIRD 2008","author":"M\u00fcckstein","year":"2008"},{"key":"2023012508173974400_B26","doi-asserted-by":"crossref","first-page":"160","DOI":"10.4161\/rna.4.3.5308","article-title":"Sensory and regulatory RNAs in prokaryotes: A new german research focus","volume":"4","author":"Narberhaus","year":"2007","journal-title":"RNA Biol."},{"key":"2023012508173974400_B27","first-page":"92","article-title":"IRIS: intermolecular RNA interaction search","volume":"15","author":"Pervouchine","year":"2004","journal-title":"Proc. Genome Inform."},{"key":"2023012508173974400_B28","article-title":"A combinatorial framework for RNA tertiary interaction","author":"Qin","year":"2007","journal-title":"Technical Report 0710.3523, arXiv."},{"key":"2023012508173974400_B29","first-page":"1507","article-title":"Fast and effective prediction of microRNA\/target duplexes","volume":"10","author":"Rehmsmeier","year":"2004","journal-title":"Gene"},{"key":"2023012508173974400_B30","doi-asserted-by":"crossref","first-page":"2053","DOI":"10.1006\/jmbi.1998.2436","article-title":"A dynamic programming algorithms for RNA structure prediction including pseudoknots","volume":"285","author":"Rivas","year":"1999","journal-title":"J. Mol. Biol."},{"key":"2023012508173974400_B31","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/978-3-642-04241-6_22","article-title":"Fast prediction of RNA-RNA interaction","volume-title":"Proceedings of the 9th Workshop on Algorithms in Bioinformatics (WABI)","author":"Salari","year":"2009"},{"key":"2023012508173974400_B32","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/s002490050023","article-title":"Algorithm independent properties of RNA structure prediction","volume":"25","author":"Tacker","year":"1996","journal-title":"Eur. Biophy. J."},{"key":"2023012508173974400_B33","article-title":"RNAsnoop: efficient target prediction for box H\/ACA snoRNAs","author":"Tafer","year":"2009","journal-title":"Bioinformatics"},{"key":"2023012508173974400_B34","doi-asserted-by":"crossref","first-page":"2791","DOI":"10.1093\/nar\/gkl356","article-title":"Target prediction for small, noncoding RNAs in bacteria","volume":"34","author":"Tjaden","year":"2006","journal-title":"Nucleic Acids Res."},{"key":"2023012508173974400_B35","doi-asserted-by":"crossref","first-page":"2355","DOI":"10.1101\/gad.354405","article-title":"Hfq-dependent regulation of OmpA synthesis is mediated by an antisense RNA","volume":"19","author":"Udekwu","year":"2005","journal-title":"Genes Dev."},{"key":"2023012508173974400_B36","doi-asserted-by":"crossref","first-page":"1018","DOI":"10.1093\/nar\/gkl1040","article-title":"Translational control and target recognition by Escherichia coli small RNAs in vivo","volume":"35","author":"Urban","year":"2007","journal-title":"Nucleic Acids Res."},{"key":"2023012508173974400_B37","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1016\/S0092-8240(84)80062-2","article-title":"RNA secondary structures and their prediction","volume":"46","author":"Zuker","year":"1984","journal-title":"Bull. Math. Biol."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/26\/2\/175\/48857761\/bioinformatics_26_2_175.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/26\/2\/175\/48857761\/bioinformatics_26_2_175.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T08:19:52Z","timestamp":1674634792000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/26\/2\/175\/209425"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,11,13]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,1,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btp635","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2010,1,15]]},"published":{"date-parts":[[2009,11,13]]}}}