Computational methods for RNA-RNA interaction prediction

Non-Coding RNAs (ncRNAs) such as microRNAs play an important role in the gene regulation. Studies on both prokaryotic and eukaryotic cells show that ncRNAs usually bind to their target mRNA to regulate the translation of corresponding genes. Therapeutic applications of RNA interference and antisense RNA regulation strongly motivate the problem of predicting whether two RNAs interact. In the past few years, high-throughput sequencing technologies have identified a large set of new regulatory ncRNAs, but the number of experimentally verified targets is considerably low. Thus, computational target prediction methods are in high demand. Current methods for predicting ncRNA-target mRNA interactions suffer from low specificity and accuracy. Moreover, their high computational complexity makes them impractical for genome-wide target prediction problems. In this dissertation, we present fast and accurate computational methods for prediction and analysis of binding thermodynamics between two RNAs, typically oligonucleotides and target RNAs. We develop a partition function algorithm to compute the stability and probability of binding between two RNAs. 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, the heat capacity and the melting temperature of interacting nucleic acids can be calculated based on the partition function of the complex. In order to reduce the time and space requirements of the computational RNA-RNA interaction prediction problem, we introduce an efficient algorithm that can predict the optimal interaction between two RNAs. Our algorithm applying a technique called sparsification has been able to reduce both time and space requirements of the interaction prediction by a linear factor. Finally, we propose a fast heuristic method for multiple binding sites prediction, based on the site accessibility and binding probabilities, that can be used for genome-wide target prediction problems.