{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,17]],"date-time":"2026-02-17T13:39:28Z","timestamp":1771335568676,"version":"3.50.1"},"reference-count":40,"publisher":"Oxford University Press (OUP)","issue":"20","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009,10,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: The RNA\u2013RNA interaction problem (RIP) consists in finding the energetically optimal structure of two RNA molecules that bind to each other. The standard model allows secondary structures in both partners as well as additional base pairs between the two RNAs subject to certain restrictions that ensure that RIP is solvabale by a polynomial time dynamic programming algorithm. RNA\u2013RNA binding, like RNA folding, is typically not dominated by the ground state structure. Instead, a large ensemble of alternative structures contributes to the interaction thermodynamics.<\/jats:p>\n               <jats:p>Results: We present here an O(N6) time and O(N4) dynamics programming algorithm for computing the full partition function for RIP which is based on the combinatorial notion of \u2018tight structures\u2019. Albeit equivalent to recent work by H. Chitsaz and collaborators, our approach in addition provides a full-fledged computation of the base pairing probabilities, which relies on the notion of a decomposition tree for joint structures. In practise, our implementation is efficient enough to investigate, for instance, the interactions of small bacterial RNAs and their target mRNAs.<\/jats:p>\n               <jats:p>Availability: The program rip is implemented in C. The source code is available for download 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\/btp481","type":"journal-article","created":{"date-parts":[[2009,8,12]],"date-time":"2009-08-12T03:55:08Z","timestamp":1250049308000},"page":"2646-2654","source":"Crossref","is-referenced-by-count":68,"title":["Partition function and base pairing probabilities for RNA\u2013RNA interaction prediction"],"prefix":"10.1093","volume":"25","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, and Interdisciplinary Center for Bioinformatics, University of Leipzig, H\u00e4rtelstrasse 16-18, D-04107 Leipzig, 4 Max Planck Institute for Mathematics in the Sciences, Inselstrasse 22, 5 RNomics Group, Fraunhofer Institut for Cell Therapy and Immunology, Perlickstra\u00dfe 1,D-04103 Leipzig, Germany, 6 Institute for Theoretical Chemistry, University of Vienna, W\u00e4hringerstrasse 17, A-1090 Vienna, Austria and 7 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, and Interdisciplinary Center for Bioinformatics, University of Leipzig, H\u00e4rtelstrasse 16-18, D-04107 Leipzig, 4 Max Planck Institute for Mathematics in the Sciences, Inselstrasse 22, 5 RNomics Group, Fraunhofer Institut for Cell Therapy and Immunology, Perlickstra\u00dfe 1,D-04103 Leipzig, Germany, 6 Institute for Theoretical Chemistry, University of Vienna, W\u00e4hringerstrasse 17, A-1090 Vienna, Austria and 7 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, and Interdisciplinary Center for Bioinformatics, University of Leipzig, H\u00e4rtelstrasse 16-18, D-04107 Leipzig, 4 Max Planck Institute for Mathematics in the Sciences, Inselstrasse 22, 5 RNomics Group, Fraunhofer Institut for Cell Therapy and Immunology, Perlickstra\u00dfe 1,D-04103 Leipzig, Germany, 6 Institute for Theoretical Chemistry, University of Vienna, W\u00e4hringerstrasse 17, A-1090 Vienna, Austria and 7 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, and Interdisciplinary Center for Bioinformatics, University of Leipzig, H\u00e4rtelstrasse 16-18, D-04107 Leipzig, 4 Max Planck Institute for Mathematics in the Sciences, Inselstrasse 22, 5 RNomics Group, Fraunhofer Institut for Cell Therapy and Immunology, Perlickstra\u00dfe 1,D-04103 Leipzig, Germany, 6 Institute for Theoretical Chemistry, University of Vienna, W\u00e4hringerstrasse 17, A-1090 Vienna, Austria and 7 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, and Interdisciplinary Center for Bioinformatics, University of Leipzig, H\u00e4rtelstrasse 16-18, D-04107 Leipzig, 4 Max Planck Institute for Mathematics in the Sciences, Inselstrasse 22, 5 RNomics Group, Fraunhofer Institut for Cell Therapy and Immunology, Perlickstra\u00dfe 1,D-04103 Leipzig, Germany, 6 Institute for Theoretical Chemistry, University of Vienna, W\u00e4hringerstrasse 17, A-1090 Vienna, Austria and 7 The Santa Fe Institute, 1399 Hyde Park Rd., Santa Fe, NM, USA"}]}],"member":"286","published-online":{"date-parts":[[2009,8,11]]},"reference":[{"key":"2023013112124787300_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":"2023013112124787300_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":"2023013112124787300_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":"2023013112124787300_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":"2023013112124787300_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":"2023013112124787300_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":"2023013112124787300_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":"2023013112124787300_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":"2023013112124787300_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":"2023013112124787300_B10","first-page":"75","article-title":"Graph-theoretic approach to RNA modeling using comparative data","volume":"3","author":"Cary","year":"1995","journal-title":"Proc. Intl Conf. Intell. Syst. Mol. Biol."},{"key":"2023013112124787300_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":"2023013112124787300_B12","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1529\/biophysj.103.020743","article-title":"Prediction of hybridization and melting for double-stranded nucleic acids","volume":"87","author":"Dimitrov","year":"2004","journal-title":"Biophys. J."},{"key":"2023013112124787300_B13","doi-asserted-by":"crossref","first-page":"1664","DOI":"10.1002\/jcc.10296","article-title":"A partition function algorithm for nucleoic acid secondary structure inluding pseudoknots","volume":"24","author":"Dirks","year":"2003","journal-title":"J. Comput. Chem."},{"key":"2023013112124787300_B14","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":"2023013112124787300_B15","first-page":"248","article-title":"Implementation of algorithms for maximum matching on nonbipartite graphs","volume-title":"PhD Thesis","author":"Gabow","year":"1973"},{"key":"2023013112124787300_B16","doi-asserted-by":"crossref","first-page":"1073","DOI":"10.1261\/rna.2230605","article-title":"A kissing-loop interaction in a hammerhead viroid RNA critical for its in vitro folding and in vivo viability","volume":"11","author":"Gago","year":"2005","journal-title":"RNA"},{"key":"2023013112124787300_B17","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":"2023013112124787300_B18","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/3-540-45719-4_24","article-title":"Algebraic dynamic programming","volume-title":"Algebraic Methodology And Software Technology","author":"Giegerich","year":"2002"},{"key":"2023013112124787300_B19","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/j.gene.2004.11.043","article-title":"The effect of RNA secondary structures on RNA-ligand binding and the modifier RNA mechanism: a quantitative model","volume":"345","author":"Hackerm\u00fcller","year":"2005","journal-title":"Gene"},{"key":"2023013112124787300_B20","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":"2023013112124787300_B21","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":"2023013112124787300_B22","article-title":"Target prediction and a statistical sampling algorithm for RNA-RNA interaction","author":"Huang","year":"2009","journal-title":"Technical Report 0908.0597"},{"key":"2023013112124787300_B23","doi-asserted-by":"crossref","first-page":"6515","DOI":"10.1073\/pnas.110533697","article-title":"Modeling RNA folding paths with pseudoknots: application to hepatitis delta virus ribozyme","volume":"97","author":"Isambert","year":"2000","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023013112124787300_B24","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":"2023013112124787300_B25","doi-asserted-by":"crossref","first-page":"813","DOI":"10.1046\/j.1365-2958.2002.03203.x","article-title":"Regulation and mode of action of the second small RNA activator of RpoS translation, RprA","volume":"46","author":"Majdalani","year":"2002","journal-title":"Mol. Microbiol."},{"key":"2023013112124787300_B26","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":"2023013112124787300_B27","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":"2023013112124787300_B28","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":"2023013112124787300_B29","doi-asserted-by":"crossref","first-page":"1432","DOI":"10.1002\/cbic.200400219","article-title":"mRNA openers and closers: modulating AU-rich element-controlled mRNA stability by a molecular switch in mRNA secondary structure","volume":"5","author":"Meisner","year":"2004","journal-title":"Chembiochem."},{"key":"2023013112124787300_B30","article-title":"On the approximation of optimal structures for RNA-RNA interaction","author":"Mneimneh","year":"2007","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinf."},{"key":"2023013112124787300_B31","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":"2023013112124787300_B32","first-page":"1177","article-title":"Thermodynamics of RNA-RNA binding","volume-title":"Bioinformatics","author":"M\u00fcckstein","year":"2006"},{"key":"2023013112124787300_B33","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":"2023013112124787300_B34","first-page":"92","article-title":"IRIS: intermolecular RNA interaction search","volume":"15","author":"Pervouchine","year":"2004","journal-title":"Proc. Genome Inform."},{"key":"2023013112124787300_B35","article-title":"A combinatorial framework for RNA tertiary interaction","author":"Qin","year":"2007","journal-title":"Technical Report 0710.3523"},{"key":"2023013112124787300_B36","first-page":"1507","article-title":"Fast and effective prediction of microRNA\/target duplexes","volume":"10","author":"Rehmsmeier","year":"2004","journal-title":"Gene"},{"key":"2023013112124787300_B37","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":"2023013112124787300_B38","doi-asserted-by":"crossref","first-page":"2804","DOI":"10.1101\/gad.447207","article-title":"A small RNA regulates multiple ABC transporter mRNAs by targeting C\/A-rich elements inside and upstream of ribosome-binding sites","volume":"21","author":"Sharma","year":"2007","journal-title":"Genes Dev."},{"key":"2023013112124787300_B39","article-title":"RNAsnoop: Efficient target prediction for box H\/ACA snoRNAs","volume-title":"Technical report","author":"Tafer","year":"2009"},{"key":"2023013112124787300_B40","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1093\/nar\/9.1.133","article-title":"Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information","volume":"9","author":"Zuker","year":"1981","journal-title":"Nucleic Acids Res."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/25\/20\/2646\/48995537\/bioinformatics_25_20_2646.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/25\/20\/2646\/48995537\/bioinformatics_25_20_2646.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T21:39:22Z","timestamp":1675201162000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/25\/20\/2646\/193475"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8,11]]},"references-count":40,"journal-issue":{"issue":"20","published-print":{"date-parts":[[2009,10,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btp481","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2009,10,15]]},"published":{"date-parts":[[2009,8,11]]}}}