@article{Chitsaz:Salari:Sahinalp:parti_funct_algor:2009,
author = {Chitsaz, Hamidreza and Salari, Raheleh and Sahinalp, S. 
          Cenk and Backofen, Rolf},
title = {A partition function algorithm for interacting nucleic acid 
         strands},
journal = {Bioinformatics},
year = {2009},
doi = {10.1093/bioinformatics/btp212},
volume = {25},
user = {arichter},
pmid = {19478011},
pages = {i365-73},
number = {12},
issn = {1367-4803},
abstract = {Recent interests, such as RNA interference and antisense 
            RNA regulation, strongly motivate the problem of predicting 
            whether two nucleic acid strands interact. 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. 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(n(6)) 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-fhlA complex. In both experiments, our algorithm shows 
            high accuracy and outperforms competitors. AVAILABILITY: 
            Software and web server is available at 
            http://compbio.cs.sfu.ca/taverna/pirna/. SUPPLEMENTARY 
            INFORMATION: Supplementary data are avaliable at 
            Bioinformatics online.}
}