{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,5]],"date-time":"2026-10-05T13:15:18Z","timestamp":1791206118425,"version":"4.1.0"},"reference-count":40,"publisher":"Oxford University Press (OUP)","issue":"12","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":2685,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/2.0\/uk\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009,6,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Recent interests, such as RNA interference and antisense RNA regulation, strongly motivate the problem of predicting whether two nucleic acid strands interact.<\/jats:p>\n               <jats:p>Motivation: Regulatory non-coding RNAs (ncRNAs) such as microRNAs play an important role in gene regulation. Studies on both prokaryotic and eukaryotic cells show that such ncRNAs usually bind to their target mRNA to regulate the translation of corresponding genes. The specificity of these interactions depends on the stability of intermolecular and intramolecular base pairing. While methods like deep sequencing allow to discover an ever increasing set of ncRNAs, there are no high-throughput methods available to detect their associated targets. Hence, there is an increasing need for precise computational target prediction. In order to predict base-pairing probability of any two bases in interacting nucleic acids, it is necessary to compute the interaction partition function over the whole ensemble. The partition function is a scalar value from which various thermodynamic quantities can be derived. For example, the equilibrium concentration of each complex nucleic acid species and also the melting temperature of interacting nucleic acids can be calculated based on the partition function of the complex.<\/jats:p>\n               <jats:p>Results: We present a model for analyzing the thermodynamics of two interacting nucleic acid strands considering the most general type of interactions studied in the literature. We also present a corresponding dynamic programming algorithm that computes the partition function over (almost) all physically possible joint secondary structures formed by two interacting nucleic acids in O(n6) time. We verify the predictive power of our algorithm by computing (i) the melting temperature for interacting RNA pairs studied in the literature and (ii) the equilibrium concentration for several variants of the OxyS\u2013fhlA complex. In both experiments, our algorithm shows high accuracy and outperforms competitors.<\/jats:p>\n               <jats:p>Availability: Software and web server is available at http:\/\/compbio.cs.sfu.ca\/taverna\/pirna\/<\/jats:p>\n               <jats:p>Contact: \u00a0cenk@cs.sfu.ca; backofen@informatik.uni-freiburg.de<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are avaliable at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btp212","type":"journal-article","created":{"date-parts":[[2009,5,28]],"date-time":"2009-05-28T15:48:54Z","timestamp":1243525734000},"page":"i365-i373","source":"Crossref","is-referenced-by-count":94,"title":["A partition function algorithm for interacting nucleic acid strands"],"prefix":"10.1093","volume":"25","author":[{"given":"Hamidreza","family":"Chitsaz","sequence":"first","affiliation":[{"name":"1 Lab for Computational Biology, School of Computing Science, Simon Fraser University, Burnaby, BC, Canada and 2Department of Bioinformatics, Institute of Computer Science, Albert-Ludwigs-Universit\u00e4t, Freiburg, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Raheleh","family":"Salari","sequence":"additional","affiliation":[{"name":"1 Lab for Computational Biology, School of Computing Science, Simon Fraser University, Burnaby, BC, Canada and 2Department of Bioinformatics, Institute of Computer Science, Albert-Ludwigs-Universit\u00e4t, Freiburg, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S. Cenk","family":"Sahinalp","sequence":"additional","affiliation":[{"name":"1 Lab for Computational Biology, School of Computing Science, Simon Fraser University, Burnaby, BC, Canada and 2Department of Bioinformatics, Institute of Computer Science, Albert-Ludwigs-Universit\u00e4t, Freiburg, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rolf","family":"Backofen","sequence":"additional","affiliation":[{"name":"1 Lab for Computational Biology, School of Computing Science, Simon Fraser University, Burnaby, BC, Canada and 2Department of Bioinformatics, Institute of Computer Science, Albert-Ludwigs-Universit\u00e4t, Freiburg, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2009,5,27]]},"reference":[{"key":"2023013112005369500_B1","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":"2023013112005369500_B2","doi-asserted-by":"crossref","first-page":"987","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":"2023013112005369500_B3","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":"2023013112005369500_B4","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/S0092-8674(04)00045-5","article-title":"MicroRNAs: genomics, biogenesis, mechanism, and function","volume":"116","author":"Bartel","year":"2004","journal-title":"Cell"},{"key":"2023013112005369500_B5","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":"2023013112005369500_B6","first-page":"15","article-title":"Antisense-RNA regulation and RNA interference","volume":"1575","author":"Brantl","year":"2002","journal-title":"Bioch. Biophys. Acta"},{"key":"2023013112005369500_B7","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":"2023013112005369500_B8","doi-asserted-by":"crossref","first-page":"2634","DOI":"10.1093\/nar\/gkl346","article-title":"Predicting RNA pseudoknot folding thermodynamics","volume":"34","author":"Cao","year":"2006","journal-title":"Nucleic Acids Res."},{"key":"2023013112005369500_B9","doi-asserted-by":"crossref","first-page":"6971","DOI":"10.1021\/bi0029548","article-title":"Thermodynamics of three-way multibranch loops in RNA","volume":"40","author":"Diamond","year":"2001","journal-title":"Biochemistry"},{"key":"2023013112005369500_B10","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":"2023013112005369500_B11","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 Review"},{"key":"2023013112005369500_B12","doi-asserted-by":"crossref","first-page":"1664","DOI":"10.1002\/jcc.10296","article-title":"A partition function algorithm for nucleic acid secondary structure including pseudoknots","volume":"24","author":"Dirks","year":"2003","journal-title":"J. Comput. Chem."},{"key":"2023013112005369500_B13","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1016\/j.tig.2005.05.008","article-title":"Micros for microbes: non-coding regulatory RNAs in bacteria","volume":"21","author":"Gottesman","year":"2005","journal-title":"Trends Genet."},{"key":"2023013112005369500_B14","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1038\/418244a","article-title":"RNA interference","volume":"418","author":"Hannon","year":"2002","journal-title":"Nature"},{"key":"2023013112005369500_B15","doi-asserted-by":"crossref","first-page":"580","DOI":"10.1093\/nar\/23.4.580","article-title":"Bulged-out nucleotides in an antisense RNA are required for rapid target RNA binding in vitro and inhibition in vivo","volume":"23","author":"Hjalt","year":"1995","journal-title":"Nucleic Acids Res."},{"key":"2023013112005369500_B16","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1016\/j.patcog.2008.08.004","article-title":"A grammatical approach to RNA-RNA interaction prediction","volume":"42","author":"Kato","year":"2009","journal-title":"Pattern Recognit."},{"key":"2023013112005369500_B17","volume-title":"Statistical Physics.","author":"Landau","year":"1969"},{"key":"2023013112005369500_B18","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/978-1-60327-429-6_1","article-title":"UNAFold: software for nucleic acid folding and hybridization","volume":"453","author":"Markham","year":"2008","journal-title":"Methods Mol. Biol."},{"key":"2023013112005369500_B19","doi-asserted-by":"crossref","first-page":"1178","DOI":"10.1261\/rna.7650904","article-title":"Using an RNA secondary structure partition function to determine confidence in base pairs predicted by free energy minimization","volume":"10","author":"Mathews","year":"2004","journal-title":"RNA"},{"key":"2023013112005369500_B20","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":"2023013112005369500_B21","doi-asserted-by":"crossref","first-page":"869","DOI":"10.1021\/bi011441d","article-title":"Experimentally derived nearest-neighbor parameters for the stability of RNA three- and four-way multibranch loops","volume":"41","author":"Mathews","year":"2002","journal-title":"Biochemistry"},{"key":"2023013112005369500_B22","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":"2023013112005369500_B23","doi-asserted-by":"crossref","first-page":"1177","DOI":"10.1093\/bioinformatics\/btl024","article-title":"Thermodynamics of RNA-RNA binding","volume":"22","author":"M\u00fc#ckstein","year":"2006","journal-title":"Bioinformatics"},{"key":"2023013112005369500_B24","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1137\/0135006","article-title":"Algorithms for loop matchings","volume":"35","author":"Nussinov","year":"1978","journal-title":"SIAM J. Appl. Math."},{"key":"2023013112005369500_B25","first-page":"92","article-title":"IRIS: intermolecular RNA interaction search","volume":"15","author":"Pervouchine","year":"2004","journal-title":"Genome Inform."},{"key":"2023013112005369500_B26","doi-asserted-by":"crossref","first-page":"304","DOI":"10.1016\/0076-6879(89)80108-9","article-title":"Absorbance melting curves of RNA","volume":"180","author":"Puglisi","year":"1989","journal-title":"Meth. Enzymol."},{"key":"2023013112005369500_B27","doi-asserted-by":"crossref","first-page":"1507","DOI":"10.1261\/rna.5248604","article-title":"Fast and effective prediction of microRNA\/target duplexes","volume":"10","author":"Rehmsmeier","year":"2004","journal-title":"RNA"},{"key":"2023013112005369500_B28","doi-asserted-by":"crossref","first-page":"2053","DOI":"10.1006\/jmbi.1998.2436","article-title":"A dynamic programming algorithm for RNA structure prediction including pseudoknots","volume":"285","author":"Rivas","year":"1999","journal-title":"J. Mol. Biol."},{"key":"2023013112005369500_B29","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/j.tibs.2005.01.007","article-title":"From genes to machines: DNA nanomechanical devices","volume":"30","author":"Seeman","year":"2005","journal-title":"Trends Biochem. Sci."},{"key":"2023013112005369500_B30","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1088\/0034-4885\/68\/1\/R05","article-title":"Nucleic acid nanostructures: bottom-up control of geometry on the nanoscale","volume":"68","author":"Seeman","year":"2005","journal-title":"Rep. Prog. Phys."},{"key":"2023013112005369500_B31","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1002\/smll.200400111","article-title":"DNA nanodevices","volume":"1","author":"Simmel","year":"2005","journal-title":"Small"},{"key":"2023013112005369500_B32","doi-asserted-by":"crossref","first-page":"1260","DOI":"10.1126\/science.1072249","article-title":"An expanding universe of noncoding RNAs","volume":"296","author":"Storz","year":"2002","journal-title":"Science"},{"key":"2023013112005369500_B33","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1038\/nnano.2007.225","article-title":"An autonomous polymerization motor powered by DNA hybridization","volume":"2","author":"Venkataraman","year":"2007","journal-title":"Nat. Nanotechnol."},{"key":"2023013112005369500_B34","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/S0168-9525(02)02658-6","article-title":"Antisense RNAs everywhere?","volume":"18","author":"Wagner","year":"2002","journal-title":"Trends Genet."},{"key":"2023013112005369500_B35","doi-asserted-by":"crossref","first-page":"366","DOI":"10.1016\/S0006-3495(02)75401-5","article-title":"Thermodynamic and kinetic characterization of antisense oligodeoxynucleotide binding to a structured mRNA","volume":"82","author":"Walton","year":"2002","journal-title":"Biophys. J."},{"key":"2023013112005369500_B36","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/0025-5564(78)90099-8","article-title":"RNA secondary structure: A complete mathematical analysis","volume":"42","author":"Waterman","year":"1978","journal-title":"Math. Biosc."},{"key":"2023013112005369500_B37","doi-asserted-by":"crossref","first-page":"14719","DOI":"10.1021\/bi9809425","article-title":"Thermodynamic parameters for an expanded nearest-neighbor model for formation of RNA duplexes with Watson-Crick base pairs","volume":"37","author":"Xia","year":"1998","journal-title":"Biochemistry"},{"key":"2023013112005369500_B38","doi-asserted-by":"crossref","first-page":"824","DOI":"10.1126\/science.1157312","article-title":"Programming DNA tube circumferences","volume":"321","author":"Yin","year":"2008","journal-title":"Science"},{"key":"2023013112005369500_B39","doi-asserted-by":"crossref","first-page":"1519","DOI":"10.1126\/science.1111444","article-title":"Ribo-gnome: the big world of small RNAs","volume":"309","author":"Zamore","year":"2005","journal-title":"Science"},{"key":"2023013112005369500_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\/12\/i365\/48991512\/bioinformatics_25_12_i365.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/25\/12\/i365\/48991512\/bioinformatics_25_12_i365.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T21:08:16Z","timestamp":1675199296000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/25\/12\/i365\/190119"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,5,27]]},"references-count":40,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2009,6,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btp212","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2009,6,15]]},"published":{"date-parts":[[2009,5,27]]}}}