Abstract
In the past years, a large set of new regulatory ncRNAs have been identified, but the number of experimentally verified targets is considerably low. Thus, computational target prediction methods are on high demand. Whereas all previous approaches for predicting a general joint structure have a complexity of O(n 6) running time and O(n 4) space, a more time and space efficient interaction prediction that is able to handle complex joint structures is necessary for genome-wide target prediction problems. In this paper we show how to reduce both the time and space complexity of the RNA-RNA interaction prediction problem as described by Alkan et al. [1] via dynamic programming sparsification - which allows to discard large portions of DP tables without loosing optimality. Applying sparsification techniques reduces the complexity of the original algorithm from O(n 6) time and O(n 4) space to O(n 4 ψ(n)) time and O(n 2 ψ(n) + n 3) space for some function ψ(n), which turns out to have small values for the range of n that we encounter in practice. Under the assumption that the polymer-zeta property holds for RNA-structures, we demonstrate that ψ(n) = O(n) on average, resulting in a linear time and space complexity improvement over the original algorithm. We evaluate our sparsified algorithm for RNA-RNA interaction prediction by total free energy minimization, based on the energy model of Chitsaz et al.[2], on a set of known interactions. Our results confirm the significant reduction of time and space requirements in practice.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alkan, C., Karakoc, E., Nadeau, J.H., Sahinalp, S.C., Zhang, K.: RNA-RNA interaction prediction and antisense RNA target search. Journal of Computational Biology (Special RECOMB 2005 Issue) 13(2), 267–282 (2006)
Chitsaz, H., Salari, R., Sahinalp, S.C., Backofen, R.: A partition function algorithm for interacting nucleic acid strands. Bioinformatics (Special ISMB/ECCB 2009 Issue) 25(12), i365–i373 (2009)
Storz, G.: An expanding universe of noncoding RNAs. Science 296(5571), 1260–1263 (2002)
Bartel, D.P.: MicroRNAs: genomics, biogenesis, mechanism, and function. Cell 116(2), 281–297 (2004)
Hannon, G.J.: RNA interference. Nature 418(6894), 244–251 (2002)
Zamore, P.D., Haley, B.: Ribo-gnome: the big world of small RNAs. Science 309(5740), 1519–1524 (2005)
Wagner, E., Flardh, K.: Antisense RNAs everywhere?. Trends Genet. 18, 223–226 (2002)
Brantl, S.: Antisense-RNA regulation and RNA interference. Bioch. Biophys. Acta 1575(1-3), 15–25 (2002)
Gottesman, S.: Micros for microbes: non-coding regulatory RNAs in bacteria. Trends in Genetics 21(7), 399–404 (2005)
Seeman, N.: From genes to machines: DNA nanomechanical devices. Trends Biochem. Sci. 30, 119–125 (2005)
Seeman, N.C., Lukeman, P.S.: Nucleic acid nanostructures: bottom-up control of geometry on the nanoscale. Reports on Progress in Physics 68, 237–270 (2005)
Simmel, F., Dittmer, W.: DNA nanodevices. Small 1, 284–299 (2005)
Venkataraman, S., Dirks, R., Rothemund, P., Winfree, E., Pierce, N.: An autonomous polymerization motor powered by DNA hybridization. Nat. Nanotechnol. 2, 490–494 (2007)
Yin, P., Hariadi, R., Sahu, S., Choi, H., Park, S., Labean, T., Reif, J.: Programming DNA tube circumferences. Science 321, 824–826 (2008)
Pervouchine, D.D.: IRIS: intermolecular RNA interaction search. Genome Inform. 15(2), 92–101 (2004)
Huang, F.W., Qin, J., Reidys, C.M., Stadler, P.F.: Partition Function and Base Pairing Probabilities for RNA-RNA Interaction Prediction. Bioinformatics 25(20), 2646–2654 (2009)
David, L., Huber, W., Granovskaia, M., Toedling, J., Palm, C.J., Bofkin, L., Jones, T., Davis, R.W., Steinmetz, L.M.: A high-resolution map of transcription in the yeast genome. Proc. Natl. Acad. Sci. U.S.A. 103(14), 5320–5325 (2006)
Wexler, Y., Zilberstein, C., Ziv-Ukelson, M.: A study of accessible motifs and RNA folding complexity. Journal of Computational Biology (Special RECOMB 2006 Issue) 14(6), 856–872 (2007)
Backofen, R., Tsur, D., Zakov, S., Ziv-Ukelson, M.: Sparse RNA folding: Time and space efficient algorithms. In: Kucherov, G., Ukkonen, E. (eds.) CPM 2009. LNCS, vol. 5577, pp. 249–262. Springer, Heidelberg (2009)
Sankoff, D.: Simultaneous solution of the RNA folding, alignment and protosequence problems. SIAM J. Appl. Math. 45(5), 810–825 (1985)
Ziv-Ukelson, M., Gat-Viks, I., Wexler, Y., Shamir, R.: A faster algorithm for RNA co-folding. In: Crandall, K.A., Lagergren, J. (eds.) WABI 2008. LNCS (LNBI), vol. 5251, pp. 174–185. Springer, Heidelberg (2008)
Rehmsmeier, M., Steffen, P., Höchsmann, M., Giegerich, R.: Fast and effective prediction of microRNA/target duplexes. RNA 10(10), 1507–1517 (2004)
Tjaden, B., Goodwin, S.S., Opdyke, J.A., Guillier, M., Fu, D.X., Gottesman, S., Storz, G.: Target prediction for small, noncoding RNAs in bacteria. Nucleic Acids Research 34(9), 2791–2802 (2006)
Andronescu, M., Zhang, Z.C., Condon, A.: Secondary structure prediction of interacting RNA molecules. Journal of Molecular Biology 345(5), 987–1001 (2005)
Bernhart, S.H., Tafer, H., Mückstein, U., Flamm, C., Stadler, P.F., Hofacker, I.L.: Partition function and base pairing probabilities of RNA heterodimers. Algorithms Mol. Biol. 1(1), 3 (2006)
Dirks, R.M., Bois, J.S., Schaeffer, J.M., Winfree, E., Pierce, N.A.: Thermodynamic analysis of interacting nucleic acid strands. SIAM Review 49(1), 65–88 (2007)
Zuker, M.: Prediction of RNA secondary structure by energy minimization. Methods in Molecular Biology 25, 267–294 (1994)
Hofacker, I.L., Fontana, W., Stadler, P.F., Bonhoeffer, S., Tacker, M., Schuster, P.: Fast folding and comparison of RNA secondary structures. Monatshefte Chemie 125, 167–188 (1994)
Mückstein, U., Tafer, H., Hackermüller, J., Bernhart, S.H., Stadler, P.F., Hofacker, I.L.: Thermodynamics of RNA-RNA binding. Bioinformatics 22(10), 1177–1182 (2006)
Busch, A., Richter, A.S., Backofen, R.: IntaRNA: efficient prediction of bacterial sRNA targets incorporating target site accessibility and seed regions. Bioinformatics 24(24), 2849–2856 (2008)
Argaman, L., Altuvia, S.: fhla repression by OxyS RNA: kissing complex formation at two sites results in a stable antisense-target RNA complex. Journal of Molecular Biology 300(5), 1101–1112 (2000)
Salari, R., Backofen, R., Sahinalp, S.C.: Fast prediction of RNA-RNA interaction. In: Salzberg, S.L., Warnow, T. (eds.) WABI 2009. LNCS, vol. 5724, pp. 261–272. Springer, Heidelberg (2009); Also Algorithms for Molecular Biology (in press)
Chitsaz, H., Backofen, R., Sahinalp, S.C.: biRNA: Fast RNA-RNA binding sites prediction. In: Salzberg, S.L., Warnow, T. (eds.) WABI 2009. LNCS, vol. 5724, pp. 25–36. Springer, Heidelberg (2009)
Nussinov, R., Pieczenik, G., Griggs, J.R., Kleitman, D.J.: Algorithms for loop matchings. SIAM Journal on Applied Mathematics 35(1), 68–82 (1978)
Fisher, M.E.: Shape of a self-avoiding walk or polymer chain. Journal of Chemical Physics 44, 616–622 (1966)
Kafri, Y., Mukamel, D., Peliti, L.: Why is the DNA denaturation transition first order? Phys. Rev. Lett. 85, 4988–4991 (2000)
Kato, Y., Akutsu, T., Seki, H.: A grammatical approach to rna-rna interaction prediction. Pattern Recogn. 42(4), 531–538 (2009)
Wu, T., Wang, J., Liu, C., Zhang, Y., Shi, B., Zhu, X., Zhang, Z., Skogerb, G., Chen, L., Lu, H., Zhao, Y., Chen, R.: NPInter: the noncoding RNAs and protein related biomacromolecules interaction database. Nucleic Acids Res. 34, D150–D152 (2006)
Benson, D.A., Karsch-Mizrachi, I., Lipman, D.J., Ostell, J., Wheeler, D.L.: GenBank. Nucleic Acids Research 36(Database issue), D25–D30 (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Salari, R., Möhl, M., Will, S., Sahinalp, S.C., Backofen, R. (2010). Time and Space Efficient RNA-RNA Interaction Prediction via Sparse Folding. In: Berger, B. (eds) Research in Computational Molecular Biology. RECOMB 2010. Lecture Notes in Computer Science(), vol 6044. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-12683-3_31
Download citation
DOI: https://doi.org/10.1007/978-3-642-12683-3_31
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-12682-6
Online ISBN: 978-3-642-12683-3
eBook Packages: Computer ScienceComputer Science (R0)