{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T14:21:08Z","timestamp":1790778068257,"version":"4.1.0"},"publisher-location":"Berlin, Heidelberg","reference-count":39,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642126826","type":"print"},{"value":"9783642126833","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-12683-3_31","type":"book-chapter","created":{"date-parts":[[2010,5,4]],"date-time":"2010-05-04T23:00:43Z","timestamp":1273014043000},"page":"473-490","source":"Crossref","is-referenced-by-count":21,"title":["Time and Space Efficient RNA-RNA Interaction Prediction via Sparse Folding"],"prefix":"10.1007","author":[{"given":"Raheleh","family":"Salari","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mathias","family":"M\u00f6hl","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sebastian","family":"Will","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S. Cenk","family":"Sahinalp","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rolf","family":"Backofen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"2","key":"31_CR1","first-page":"267","volume":"13","author":"C. Alkan","year":"2006","unstructured":"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)\u00a013(2), 267\u2013282 (2006)","journal-title":"Journal of Computational Biology (Special RECOMB 2005 Issue)"},{"key":"31_CR2","doi-asserted-by":"crossref","unstructured":"Chitsaz, H., Salari, R., Sahinalp, S.C., Backofen, R.: A partition function algorithm for interacting nucleic acid strands. Bioinformatics (Special ISMB\/ECCB 2009 Issue)\u00a025(12), i365\u2013i373 (2009)","DOI":"10.1093\/bioinformatics\/btp212"},{"issue":"5571","key":"31_CR3","doi-asserted-by":"publisher","first-page":"1260","DOI":"10.1126\/science.1072249","volume":"296","author":"G. Storz","year":"2002","unstructured":"Storz, G.: An expanding universe of noncoding RNAs. Science\u00a0296(5571), 1260\u20131263 (2002)","journal-title":"Science"},{"issue":"2","key":"31_CR4","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/S0092-8674(04)00045-5","volume":"116","author":"D.P. Bartel","year":"2004","unstructured":"Bartel, D.P.: MicroRNAs: genomics, biogenesis, mechanism, and function. Cell\u00a0116(2), 281\u2013297 (2004)","journal-title":"Cell"},{"issue":"6894","key":"31_CR5","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1038\/418244a","volume":"418","author":"G.J. Hannon","year":"2002","unstructured":"Hannon, G.J.: RNA interference. Nature\u00a0418(6894), 244\u2013251 (2002)","journal-title":"Nature"},{"issue":"5740","key":"31_CR6","doi-asserted-by":"publisher","first-page":"1519","DOI":"10.1126\/science.1111444","volume":"309","author":"P.D. Zamore","year":"2005","unstructured":"Zamore, P.D., Haley, B.: Ribo-gnome: the big world of small RNAs. Science\u00a0309(5740), 1519\u20131524 (2005)","journal-title":"Science"},{"key":"31_CR7","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/S0168-9525(02)02658-6","volume":"18","author":"E. Wagner","year":"2002","unstructured":"Wagner, E., Flardh, K.: Antisense RNAs everywhere?. Trends Genet.\u00a018, 223\u2013226 (2002)","journal-title":"Trends Genet."},{"issue":"1-3","key":"31_CR8","first-page":"15","volume":"1575","author":"S. Brantl","year":"2002","unstructured":"Brantl, S.: Antisense-RNA regulation and RNA interference. Bioch. Biophys. Acta\u00a01575(1-3), 15\u201325 (2002)","journal-title":"Bioch. Biophys. Acta"},{"issue":"7","key":"31_CR9","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1016\/j.tig.2005.05.008","volume":"21","author":"S. Gottesman","year":"2005","unstructured":"Gottesman, S.: Micros for microbes: non-coding regulatory RNAs in bacteria. Trends in Genetics\u00a021(7), 399\u2013404 (2005)","journal-title":"Trends in Genetics"},{"key":"31_CR10","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/j.tibs.2005.01.007","volume":"30","author":"N. Seeman","year":"2005","unstructured":"Seeman, N.: From genes to machines: DNA nanomechanical devices. Trends Biochem. Sci.\u00a030, 119\u2013125 (2005)","journal-title":"Trends Biochem. Sci."},{"key":"31_CR11","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1088\/0034-4885\/68\/1\/R05","volume":"68","author":"N.C. Seeman","year":"2005","unstructured":"Seeman, N.C., Lukeman, P.S.: Nucleic acid nanostructures: bottom-up control of geometry on the nanoscale. Reports on Progress in Physics\u00a068, 237\u2013270 (2005)","journal-title":"Reports on Progress in Physics"},{"key":"31_CR12","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1002\/smll.200400111","volume":"1","author":"F. Simmel","year":"2005","unstructured":"Simmel, F., Dittmer, W.: DNA nanodevices. Small\u00a01, 284\u2013299 (2005)","journal-title":"Small"},{"key":"31_CR13","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1038\/nnano.2007.225","volume":"2","author":"S. Venkataraman","year":"2007","unstructured":"Venkataraman, S., Dirks, R., Rothemund, P., Winfree, E., Pierce, N.: An autonomous polymerization motor powered by DNA hybridization. Nat. Nanotechnol.\u00a02, 490\u2013494 (2007)","journal-title":"Nat. Nanotechnol."},{"key":"31_CR14","doi-asserted-by":"publisher","first-page":"824","DOI":"10.1126\/science.1157312","volume":"321","author":"P. Yin","year":"2008","unstructured":"Yin, P., Hariadi, R., Sahu, S., Choi, H., Park, S., Labean, T., Reif, J.: Programming DNA tube circumferences. Science\u00a0321, 824\u2013826 (2008)","journal-title":"Science"},{"issue":"2","key":"31_CR15","first-page":"92","volume":"15","author":"D.D. Pervouchine","year":"2004","unstructured":"Pervouchine, D.D.: IRIS: intermolecular RNA interaction search. Genome Inform.\u00a015(2), 92\u2013101 (2004)","journal-title":"Genome Inform."},{"issue":"20","key":"31_CR16","doi-asserted-by":"crossref","first-page":"2646","DOI":"10.1093\/bioinformatics\/btp481","volume":"25","author":"F.W. Huang","year":"2009","unstructured":"Huang, F.W., Qin, J., Reidys, C.M., Stadler, P.F.: Partition Function and Base Pairing Probabilities for RNA-RNA Interaction Prediction. Bioinformatics\u00a025(20), 2646\u20132654 (2009)","journal-title":"Bioinformatics"},{"issue":"14","key":"31_CR17","doi-asserted-by":"publisher","first-page":"5320","DOI":"10.1073\/pnas.0601091103","volume":"103","author":"L. David","year":"2006","unstructured":"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.\u00a0103(14), 5320\u20135325 (2006)","journal-title":"Proc. Natl. Acad. Sci. U.S.A."},{"issue":"6","key":"31_CR18","first-page":"856","volume":"14","author":"Y. Wexler","year":"2007","unstructured":"Wexler, Y., Zilberstein, C., Ziv-Ukelson, M.: A study of accessible motifs and RNA folding complexity. Journal of Computational Biology (Special RECOMB 2006 Issue)\u00a014(6), 856\u2013872 (2007)","journal-title":"Journal of Computational Biology (Special RECOMB 2006 Issue)"},{"key":"31_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/978-3-642-02441-2_22","volume-title":"Combinatorial Pattern Matching","author":"R. Backofen","year":"2009","unstructured":"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.\u00a05577, pp. 249\u2013262. Springer, Heidelberg (2009)"},{"issue":"5","key":"31_CR20","doi-asserted-by":"publisher","first-page":"810","DOI":"10.1137\/0145048","volume":"45","author":"D. Sankoff","year":"1985","unstructured":"Sankoff, D.: Simultaneous solution of the RNA folding, alignment and protosequence problems. SIAM J. Appl. Math.\u00a045(5), 810\u2013825 (1985)","journal-title":"SIAM J. Appl. Math."},{"key":"31_CR21","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1007\/978-3-540-87361-7_15","volume-title":"Algorithms in Bioinformatics","author":"M. Ziv-Ukelson","year":"2008","unstructured":"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.\u00a05251, pp. 174\u2013185. Springer, Heidelberg (2008)"},{"issue":"10","key":"31_CR22","doi-asserted-by":"publisher","first-page":"1507","DOI":"10.1261\/rna.5248604","volume":"10","author":"M. Rehmsmeier","year":"2004","unstructured":"Rehmsmeier, M., Steffen, P., H\u00f6chsmann, M., Giegerich, R.: Fast and effective prediction of microRNA\/target duplexes. RNA\u00a010(10), 1507\u20131517 (2004)","journal-title":"RNA"},{"issue":"9","key":"31_CR23","doi-asserted-by":"publisher","first-page":"2791","DOI":"10.1093\/nar\/gkl356","volume":"34","author":"B. Tjaden","year":"2006","unstructured":"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\u00a034(9), 2791\u20132802 (2006)","journal-title":"Nucleic Acids Research"},{"issue":"5","key":"31_CR24","doi-asserted-by":"publisher","first-page":"987","DOI":"10.1016\/j.jmb.2004.10.082","volume":"345","author":"M. Andronescu","year":"2005","unstructured":"Andronescu, M., Zhang, Z.C., Condon, A.: Secondary structure prediction of interacting RNA molecules. Journal of Molecular Biology\u00a0345(5), 987\u20131001 (2005)","journal-title":"Journal of Molecular Biology"},{"issue":"1","key":"31_CR25","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1186\/1748-7188-1-3","volume":"1","author":"S.H. Bernhart","year":"2006","unstructured":"Bernhart, S.H., Tafer, H., M\u00fcckstein, U., Flamm, C., Stadler, P.F., Hofacker, I.L.: Partition function and base pairing probabilities of RNA heterodimers. Algorithms Mol. Biol.\u00a01(1), 3 (2006)","journal-title":"Algorithms Mol. Biol."},{"issue":"1","key":"31_CR26","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1137\/060651100","volume":"49","author":"R.M. Dirks","year":"2007","unstructured":"Dirks, R.M., Bois, J.S., Schaeffer, J.M., Winfree, E., Pierce, N.A.: Thermodynamic analysis of interacting nucleic acid strands. SIAM Review\u00a049(1), 65\u201388 (2007)","journal-title":"SIAM Review"},{"key":"31_CR27","first-page":"267","volume":"25","author":"M. Zuker","year":"1994","unstructured":"Zuker, M.: Prediction of RNA secondary structure by energy minimization. Methods in Molecular Biology\u00a025, 267\u2013294 (1994)","journal-title":"Methods in Molecular Biology"},{"key":"31_CR28","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/BF00818163","volume":"125","author":"I.L. Hofacker","year":"1994","unstructured":"Hofacker, I.L., Fontana, W., Stadler, P.F., Bonhoeffer, S., Tacker, M., Schuster, P.: Fast folding and comparison of RNA secondary structures. Monatshefte Chemie\u00a0125, 167\u2013188 (1994)","journal-title":"Monatshefte Chemie"},{"issue":"10","key":"31_CR29","doi-asserted-by":"publisher","first-page":"1177","DOI":"10.1093\/bioinformatics\/btl024","volume":"22","author":"U. M\u00fcckstein","year":"2006","unstructured":"M\u00fcckstein, U., Tafer, H., Hackerm\u00fcller, J., Bernhart, S.H., Stadler, P.F., Hofacker, I.L.: Thermodynamics of RNA-RNA binding. Bioinformatics\u00a022(10), 1177\u20131182 (2006)","journal-title":"Bioinformatics"},{"issue":"24","key":"31_CR30","doi-asserted-by":"publisher","first-page":"2849","DOI":"10.1093\/bioinformatics\/btn544","volume":"24","author":"A. Busch","year":"2008","unstructured":"Busch, A., Richter, A.S., Backofen, R.: IntaRNA: efficient prediction of bacterial sRNA targets incorporating target site accessibility and seed regions. Bioinformatics\u00a024(24), 2849\u20132856 (2008)","journal-title":"Bioinformatics"},{"issue":"5","key":"31_CR31","doi-asserted-by":"publisher","first-page":"1101","DOI":"10.1006\/jmbi.2000.3942","volume":"300","author":"L. Argaman","year":"2000","unstructured":"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\u00a0300(5), 1101\u20131112 (2000)","journal-title":"Journal of Molecular Biology"},{"key":"31_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/978-3-642-04241-6_22","volume-title":"Algorithms in Bioinformatics","author":"R. Salari","year":"2009","unstructured":"Salari, R., Backofen, R., Sahinalp, S.C.: Fast prediction of RNA-RNA interaction. In: Salzberg, S.L., Warnow, T. (eds.) WABI 2009. LNCS, vol.\u00a05724, pp. 261\u2013272. Springer, Heidelberg (2009); Also Algorithms for Molecular Biology (in press)"},{"key":"31_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/978-3-642-04241-6_3","volume-title":"Algorithms in Bioinformatics","author":"H. Chitsaz","year":"2009","unstructured":"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.\u00a05724, pp. 25\u201336. Springer, Heidelberg (2009)"},{"issue":"1","key":"31_CR34","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1137\/0135006","volume":"35","author":"R. Nussinov","year":"1978","unstructured":"Nussinov, R., Pieczenik, G., Griggs, J.R., Kleitman, D.J.: Algorithms for loop matchings. SIAM Journal on Applied Mathematics\u00a035(1), 68\u201382 (1978)","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"31_CR35","doi-asserted-by":"publisher","first-page":"616","DOI":"10.1063\/1.1726734","volume":"44","author":"M.E. Fisher","year":"1966","unstructured":"Fisher, M.E.: Shape of a self-avoiding walk or polymer chain. Journal of Chemical Physics\u00a044, 616\u2013622 (1966)","journal-title":"Journal of Chemical Physics"},{"key":"31_CR36","doi-asserted-by":"publisher","first-page":"4988","DOI":"10.1103\/PhysRevLett.85.4988","volume":"85","author":"Y. Kafri","year":"2000","unstructured":"Kafri, Y., Mukamel, D., Peliti, L.: Why is the DNA denaturation transition first order? Phys. Rev. Lett.\u00a085, 4988\u20134991 (2000)","journal-title":"Phys. Rev. Lett."},{"issue":"4","key":"31_CR37","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1016\/j.patcog.2008.08.004","volume":"42","author":"Y. Kato","year":"2009","unstructured":"Kato, Y., Akutsu, T., Seki, H.: A grammatical approach to rna-rna interaction prediction. Pattern Recogn.\u00a042(4), 531\u2013538 (2009)","journal-title":"Pattern Recogn."},{"key":"31_CR38","doi-asserted-by":"crossref","first-page":"D150","DOI":"10.1093\/nar\/gkj025","volume":"34","author":"T. Wu","year":"2006","unstructured":"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.\u00a034, D150\u2013D152 (2006)","journal-title":"Nucleic Acids Res"},{"issue":"Database issue","key":"31_CR39","first-page":"D25","volume":"36","author":"D.A. Benson","year":"2008","unstructured":"Benson, D.A., Karsch-Mizrachi, I., Lipman, D.J., Ostell, J., Wheeler, D.L.: GenBank. Nucleic Acids Research\u00a036(Database issue), D25\u2013D30 (2008)","journal-title":"Nucleic Acids Research"}],"container-title":["Lecture Notes in Computer Science","Research in Computational Molecular Biology"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-12683-3_31.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:56:24Z","timestamp":1606186584000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-12683-3_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642126826","9783642126833"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-12683-3_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010]]}}}