{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:19:20Z","timestamp":1759637960891},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642317699"},{"type":"electronic","value":"9783642317705"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31770-5_16","type":"book-chapter","created":{"date-parts":[[2012,7,26]],"date-time":"2012-07-26T05:03:12Z","timestamp":1343278992000},"page":"176-187","source":"Crossref","is-referenced-by-count":4,"title":["Speedup of RNA Pseudoknotted Secondary Structure Recurrence Computation with the Four-Russians Method"],"prefix":"10.1007","author":[{"given":"Yelena","family":"Frid","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dan","family":"Gusfield","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4-5","key":"16_CR1","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1016\/j.tcs.2008.09.042","volume":"410","author":"A. Condon","year":"2009","unstructured":"Condon, A., Jabbari, H.: Computational prediction of nucleic acid secondary structure: Methods, applications, and challenges. Theor. Comput. Sci.\u00a0410(4-5), 294\u2013301 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"16_CR2","doi-asserted-by":"publisher","first-page":"2053","DOI":"10.1006\/jmbi.1998.2436","volume":"285","author":"E. Rivas","year":"1999","unstructured":"Rivas, E., Eddy, S.R.: A dynamic programming algorithm for RNA structure prediction including pseudoknots. Journal of Molecular Biology\u00a0285(5), 2053\u20132068 (1999)","journal-title":"Journal of Molecular Biology"},{"issue":"8","key":"16_CR3","doi-asserted-by":"publisher","first-page":"926","DOI":"10.1093\/bioinformatics\/btm049","volume":"23","author":"E. Torarinsson","year":"2007","unstructured":"Torarinsson, E., Havgaard, J.H., Gorodkin, J.: Multiple structural alignment and clustering of RNA sequences. Bioinformatics\u00a023(8), 926\u2013932 (2007)","journal-title":"Bioinformatics"},{"issue":"1","key":"16_CR4","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1186\/1471-2164-8-406","volume":"8","author":"D. Rose","year":"2007","unstructured":"Rose, D., Hackermuller, J., Washietl, S., Reiche, K., Hertel, J., FindeiSZ, S., Stadler, P., Prohaska, S.: Computational rnomics of drosophilids. BMC Genomics\u00a08(1), 406 (2007)","journal-title":"BMC Genomics"},{"issue":"2","key":"16_CR5","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1101\/gr.6887408","volume":"18","author":"E. Torarinsson","year":"2008","unstructured":"Torarinsson, E., Yao, Z., Wiklund, E.D., Bramsen, J.B., Hansen, C., Kjems, J., Tommerup, N., Ruzzo, W.L., Gorodkin, J.: Comparative genomics beyond sequence-based alignments: RNA structures in the encode regions. Genome Res.\u00a018(2), 242\u2013251 (2008)","journal-title":"Genome Res."},{"key":"16_CR6","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1007\/978-3-540-74126-8_29","volume-title":"Algorithms in Bioinformatics","author":"C. Liu","year":"2007","unstructured":"Liu, C., Song, Y., Shapiro, L.: RNA Folding Including Pseudoknots: A New Parameterized Algorithm and Improved Upper Bound. In: Giancarlo, R., Hannenhalli, S. (eds.) WABI 2007. LNCS (LNBI), vol.\u00a04645, pp. 310\u2013322. Springer, Heidelberg (2007)"},{"issue":"1","key":"16_CR7","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"},{"issue":"4","key":"16_CR8","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1007\/BF02459506","volume":"46","author":"M. Zuker","year":"1984","unstructured":"Zuker, M., Sankoff, D.: RNA secondary structures and their prediction. Bulletin of Mathematical Biology\u00a046(4), 591\u2013621 (1984)","journal-title":"Bulletin of Mathematical Biology"},{"key":"16_CR9","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/0025-5564(78)90099-8","volume":"42","author":"M.S. Waterman","year":"1978","unstructured":"Waterman, M.S., Smith, T.F.: RNA secondary structure: A complete mathematical analysis. Math. Biosc.\u00a042, 257\u2013266 (1978)","journal-title":"Math. Biosc."},{"key":"16_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/978-3-642-04241-6_9","volume-title":"Algorithms in Bioinformatics","author":"Y. Frid","year":"2009","unstructured":"Frid, Y., Gusfield, D.: A Simple, Practical and Complete \n                  \n                    \n                  \n                  $O(\\frac{n^3}{ \\log n})$\n                -Time Algorithm for RNA Folding Using the Four-Russians Speedup. In: Salzberg, S.L., Warnow, T. (eds.) WABI 2009. LNCS, vol.\u00a05724, pp. 97\u2013107. Springer, Heidelberg (2009)"},{"issue":"3-4","key":"16_CR11","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1089\/106652700750050862","volume":"7","author":"R.B. Lyngs\u00f8","year":"2000","unstructured":"Lyngs\u00f8, R.B., Pedersen, C.N.S.: RNA pseudoknot prediction in energy-based models. Journal of Computational Biology\u00a07(3-4), 409\u2013427 (2000)","journal-title":"Journal of Computational Biology"},{"issue":"1-3","key":"16_CR12","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/S0166-218X(00)00186-4","volume":"104","author":"T. Akutsu","year":"2000","unstructured":"Akutsu, T.: Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots. Discrete Applied Mathematics\u00a0104(1-3), 45\u201362 (2000)","journal-title":"Discrete Applied Mathematics"},{"issue":"13","key":"16_CR13","doi-asserted-by":"publisher","first-page":"1664","DOI":"10.1002\/jcc.10296","volume":"24","author":"R.M. Dirks","year":"2003","unstructured":"Dirks, R.M., Pierce, N.A.: A partition function algorithm for nucleic acid secondary structure including pseudoknots. Journal of Computational Chemistry\u00a024(13), 1664\u20131677 (2003)","journal-title":"Journal of Computational Chemistry"},{"issue":"3","key":"16_CR14","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1016\/j.sbi.2006.05.010","volume":"16","author":"D.H. Mathews","year":"2006","unstructured":"Mathews, D.H., Turner, D.H.: Prediction of RNA secondary structure by free energy minimization. Current Opinion in Structural Biology\u00a016(3), 270\u2013278 (2006); Nucleic acids\/Sequences and topology - Anna Marie Pyle and Jonathan Widom\/Nick V Grishin and Sarah A Teichmann","journal-title":"Current Opinion in Structural Biology"},{"issue":"1","key":"16_CR15","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1186\/1471-2105-5-104","volume":"5","author":"J. Reeder","year":"2004","unstructured":"Reeder, J., Giegerich, R.: Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics. BMC Bioinformatics\u00a05(1), 104 (2004)","journal-title":"BMC Bioinformatics"},{"issue":"2","key":"16_CR16","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/S0304-3975(98)00090-5","volume":"210","author":"Y. Uemura","year":"1999","unstructured":"Uemura, Y., Hasegawa, A., Kobayashi, S., Yokomori, T.: Tree adjoining grammars for RNA structure prediction. Theoretical Computer Science\u00a0210(2), 277\u2013303 (1999)","journal-title":"Theoretical Computer Science"},{"key":"16_CR17","unstructured":"Deogun, J.S., Donts, R., Komina, O., Ma, F.: RNA secondary structure prediction with simple pseudoknots. In: Chen, Y.-P.P. (ed.) APBC. CRPIT, vol.\u00a029, pp. 239\u2013246. Australian Computer Society (2004)"},{"issue":"4","key":"16_CR18","doi-asserted-by":"publisher","first-page":"696","DOI":"10.1261\/rna.1429009","volume":"15","author":"S. Cao","year":"2009","unstructured":"Cao, S., Chen, S.-J.: Predicting structures and stabilities for h-type pseudoknots with interhelix loops. RNA\u00a015(4), 696\u2013706 (2009)","journal-title":"RNA"},{"issue":"1","key":"16_CR19","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/j.tcs.2004.03.042","volume":"320","author":"A. Condon","year":"2004","unstructured":"Condon, A., Davy, B., Rastegari, B., Zhao, S., Tarrant, F.: Classifying RNA pseudoknotted structures. Theoretical Computer Science\u00a0320(1), 35\u201350 (2004)","journal-title":"Theoretical Computer Science"},{"issue":"10","key":"16_CR20","doi-asserted-by":"publisher","first-page":"1339","DOI":"10.1089\/cmb.2010.0086","volume":"18","author":"C. Saule","year":"2011","unstructured":"Saule, C., R\u00e9gnier, J.-M.S.M., Denise, A.: Counting RNA pseudoknotted structures. Journal of Computational Biology\u00a018(10), 1339\u20131351 (2011)","journal-title":"Journal of Computational Biology"},{"key":"16_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1007\/978-3-642-15294-8_4","volume-title":"Algorithms in Bioinformatics","author":"M. M\u00f6hl","year":"2010","unstructured":"M\u00f6hl, M., Salari, R., Will, S., Backofen, R., Sahinalp, S.C.: Sparsification of RNA Structure Prediction Including Pseudoknots. In: Moulton, V., Singh, M. (eds.) WABI 2010. LNCS, vol.\u00a06293, pp. 40\u201351. Springer, Heidelberg (2010)"},{"key":"16_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1007\/978-3-642-21458-5_37","volume-title":"Combinatorial Pattern Matching","author":"T. Pinhas","year":"2011","unstructured":"Pinhas, T., Tsur, D., Zakov, S., Ziv-Ukelson, M.: Edit Distance with Duplications and Contractions Revisited. In: Giancarlo, R., Manzini, G. (eds.) CPM 2011. LNCS, vol.\u00a06661, pp. 441\u2013454. Springer, Heidelberg (2011)"},{"key":"16_CR23","unstructured":"Williams, R.: Matrix-vector multiplication in sub-quadratic time (some preprocessing required). In: Bansal, N., Pruhs, K., Stein, C. (eds.) SODA, pp. 995\u20131001. SIAM (2007)"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31770-5_16.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T11:47:42Z","timestamp":1620128862000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31770-5_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642317699","9783642317705"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31770-5_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}