{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T19:51:18Z","timestamp":1742932278122,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":39,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662482209"},{"type":"electronic","value":"9783662482216"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-48221-6_20","type":"book-chapter","created":{"date-parts":[[2015,8,27]],"date-time":"2015-08-27T14:14:31Z","timestamp":1440684871000},"page":"271-285","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Sparsified Four-Russian Algorithm for RNA Folding"],"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","published-online":{"date-parts":[[2015,8,28]]},"reference":[{"issue":"2\u20133","key":"20_CR1","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1023\/A:1009898029639","volume":"3","author":"T Akutsu","year":"1999","unstructured":"Akutsu, T.: Approximation and exact algorithms for RNA secondary structure prediction and recognition of stochastic context-free languages. J. Comb. Optim. 3(2\u20133), 321\u2013336 (1999)","journal-title":"J. Comb. Optim."},{"issue":"13","key":"20_CR2","doi-asserted-by":"publisher","first-page":"i19","DOI":"10.1093\/bioinformatics\/btm223","volume":"23","author":"M Andronescu","year":"2007","unstructured":"Andronescu, M., Condon, A., Hoos, H.H., Mathews, D.H., Murphy, K.P.: Efficient parameter estimation for RNA secondary structure prediction. Bioinformatics 23(13), i19\u2013i28 (2007)","journal-title":"Bioinformatics"},{"key":"20_CR3","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 Lille. LNCS, vol. 5577, pp. 249\u2013262. Springer, Heidelberg (2009)"},{"issue":"1","key":"20_CR4","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/j.jda.2010.09.001","volume":"9","author":"R Backofen","year":"2011","unstructured":"Backofen, R., Tsur, D., Zakov, S., Ziv-Ukelson, M.: Sparse RNA folding: time and space efficient algorithms. J. Discrete Algorithms 9(1), 12\u201331 (2011)","journal-title":"J. Discrete Algorithms"},{"key":"20_CR5","doi-asserted-by":"crossref","unstructured":"Chan, T.: Speeding up the Four Russians algorithm by about one more logarithmic factor. In: SODA, pp. 212\u2013217 (2015)","DOI":"10.1137\/1.9781611973730.16"},{"issue":"14","key":"20_CR6","doi-asserted-by":"publisher","first-page":"e90","DOI":"10.1093\/bioinformatics\/btl246","volume":"22","author":"CB Do","year":"2006","unstructured":"Do, C.B., Woods, D.A., Batzoglou, S.: Contrafold: RNA secondary structure prediction without physics-based models. Bioinformatics 22(14), e90\u2013e98 (2006)","journal-title":"Bioinformatics"},{"issue":"1","key":"20_CR7","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1186\/1471-2105-5-71","volume":"5","author":"R Dowell","year":"2004","unstructured":"Dowell, R., Eddy, S.: Evaluation of several lightweight stochastic context-free grammars for RNA secondary structure prediction. BMC Bioinform. 5(1), 71 (2004)","journal-title":"BMC Bioinform."},{"key":"20_CR8","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511790492","volume-title":"Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids","author":"R Durbin","year":"1998","unstructured":"Durbin, R., Eddy, S., Krogh, A., Mitchison, G.: Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press, Cambridge (1998)"},{"key":"20_CR9","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 $$O(\\frac{n^3}{ \\log n})$$-time algorithm for RNA folding using the Four-Russians speedup. In: Salzberg, S.L., Warnow, T. (eds.) WABI 2009. LNCS, vol. 5724, pp. 97\u2013107. Springer, Heidelberg (2009)"},{"issue":"1","key":"20_CR10","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1186\/1748-7188-5-13","volume":"5","author":"Y Frid","year":"2010","unstructured":"Frid, Y., Gusfield, D.: A simple, practical and complete O(n$$^{\\text{3 }}$$\/log(n))-time algorithm for RNA folding using the [Four-Russians] speedup. Algorithms Mol. Biol. 5(1), 13 (2010)","journal-title":"Algorithms Mol. Biol."},{"key":"20_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-15294-8_1","volume-title":"Algorithms in Bioinformatics","author":"Y Frid","year":"2010","unstructured":"Frid, Y., Gusfield, D.: A worst-case and practical speedup for the RNA co-folding problem using the Four-Russians idea. In: Moulton, V., Singh, M. (eds.) WABI 2010. LNCS, vol. 6293, pp. 1\u201312. Springer, Heidelberg (2010)"},{"key":"20_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1007\/978-3-642-31770-5_16","volume-title":"Combinatorial Optimization and Applications","author":"Y Frid","year":"2012","unstructured":"Frid, Y., Gusfield, D.: Speedup of RNA pseudoknotted secondary structure recurrence computation with the Four-Russians method. In: Lin, G. (ed.) COCOA 2012. LNCS, vol. 7402, pp. 176\u2013187. Springer, Heidelberg (2012)"},{"issue":"4","key":"20_CR13","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1006\/jmbi.1999.2801","volume":"289","author":"V Juan","year":"1999","unstructured":"Juan, V., Wilson, C.: RNA secondary structure prediction based on free energy and phylogenetic analysis. J. Mol. Biol. 289(4), 935\u2013947 (1999)","journal-title":"J. Mol. Biol."},{"key":"20_CR14","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-25740-7","volume-title":"RNA 3D Structure Analysis and Prediction","author":"NB Leontis","year":"2012","unstructured":"Leontis, N.B., Westhof, E.: RNA 3D Structure Analysis and Prediction, vol. 27. Springer, Heidelberg (2012)"},{"key":"20_CR15","series-title":"Methods in Molecular Biology","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-1-60327-429-6_1","volume-title":"Bioinformatics","author":"NR Markham","year":"2008","unstructured":"Markham, N.R., Zuker, M.: UNAFold. In: Keith, J.M. (ed.) Bioinformatics. Methods in Molecular Biology, vol. 453, pp. 3\u201331. Humana Press, New York (2008)"},{"issue":"19","key":"20_CR16","doi-asserted-by":"publisher","first-page":"7287","DOI":"10.1073\/pnas.0401799101","volume":"101","author":"DH Mathews","year":"2004","unstructured":"Mathews, D.H., Disney, M.D., Childs, J.L., Schroeder, S.J., Zuker, M., Turner, D.H.: Incorporating chemical modification constraints into a dynamic programming algorithm for prediction of RNA secondary structure. Proc. Natl. Acad. Sci. U.S.A. 101(19), 7287\u20137292 (2004)","journal-title":"Proc. Natl. Acad. Sci. U.S.A."},{"issue":"5","key":"20_CR17","doi-asserted-by":"publisher","first-page":"911","DOI":"10.1006\/jmbi.1999.2700","volume":"288","author":"DH Mathews","year":"1999","unstructured":"Mathews, D.H., Sabina, J., Zuker, M., Turner, D.H.: Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structure. J. Mol. Biol. 288(5), 911\u2013940 (1999)","journal-title":"J. Mol. Biol."},{"key":"20_CR18","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1021\/bk-1998-0682.ch015","volume":"682","author":"DH Mathews","year":"1998","unstructured":"Mathews, D.H., Andre, T.C., Kim, J., Turner, D.H., Zuker, M.: An updated recursive algorithm for RNA secondary structure prediction with improved thermodynamic parameters. Mol. Model. Nucleic Acids 682, 246\u2013257 (1998)","journal-title":"Mol. Model. Nucleic Acids"},{"issue":"6\u20137","key":"20_CR19","doi-asserted-by":"publisher","first-page":"1105","DOI":"10.1002\/bip.360290621","volume":"29","author":"JS McCaskill","year":"1990","unstructured":"McCaskill, J.S.: The equilibrium partition function and base pair binding probabilities for RNA secondary structure. Biopolymers 29(6\u20137), 1105\u20131119 (1990)","journal-title":"Biopolymers"},{"key":"20_CR20","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1186\/1748-7188-5-39","volume":"5","author":"M M\u00f8hl","year":"2010","unstructured":"M\u00f8hl, M., Salari, R., Will, S., Backofen, R., Sahinalp, S.C.: Sparsification of RNA structure prediction including pseudoknots. Algorithms Mol. Biol. 5, 39 (2010)","journal-title":"Algorithms Mol. Biol."},{"key":"20_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. 6293, pp. 40\u201351. Springer, Heidelberg (2010)"},{"issue":"11","key":"20_CR22","doi-asserted-by":"publisher","first-page":"6309","DOI":"10.1073\/pnas.77.11.6309","volume":"77","author":"R Nussinov","year":"1980","unstructured":"Nussinov, R., Jacobson, A.B.: Fast algorithm for predicting the secondary structure of single-stranded RNA. PNAS 77(11), 6309\u20136313 (1980)","journal-title":"PNAS"},{"issue":"1","key":"20_CR23","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 J. Appl. Math. 35(1), 68\u201382 (1978)","journal-title":"SIAM J. Appl. Math."},{"key":"20_CR24","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1186\/1748-7188-8-27","volume":"8","author":"T Pinhas","year":"2013","unstructured":"Pinhas, T., Zakov, S., Tsur, D., Ziv-Ukelson, M.: Efficient edit distance with duplications and contractions. Algorithms Mol. Biol. 8, 27 (2013)","journal-title":"Algorithms Mol. Biol."},{"issue":"1","key":"20_CR25","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1186\/1471-2105-11-129","volume":"11","author":"J Reuter","year":"2010","unstructured":"Reuter, J., Mathews, D.H.: RNAstructure: software for RNA secondary structure prediction and analysis. BMC Bioinform. 11(1), 129 (2010)","journal-title":"BMC Bioinform."},{"key":"20_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1007\/978-3-642-12683-3_31","volume-title":"Research in Computational Molecular Biology","author":"R Salari","year":"2010","unstructured":"Salari, R., M\u00f6hl, M., Will, S., Sahinalp, S.C., Backofen, R.: Time and space efficient RNA-RNA interaction prediction via sparse folding. In: Berger, B. (ed.) RECOMB 2010. LNCS, vol. 6044, pp. 473\u2013490. Springer, Heidelberg (2010)"},{"key":"20_CR27","first-page":"93","volume-title":"Time Warps, String Edits and Macromolecules: The Theory and Practice of Sequence Comparison","author":"D Sankoff","year":"1983","unstructured":"Sankoff, D., Kruskal, J.B., Mainville, S., Cedergreen, R.J.: Fast algorithms to determine RNA secondary structures containing multiple loops. In: Sankoff, D., Kruskal, J.B. (eds.) Time Warps, String Edits and Macromolecules: The Theory and Practice of Sequence Comparison, pp. 93\u2013120. Addison-Wesley, Reading (1983)"},{"issue":"150","key":"20_CR28","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1038\/newbio246040a0","volume":"246","author":"I Tinoco","year":"1973","unstructured":"Tinoco, I., Borer, P.N., Dengler, B., Levine, M.D., Uhlenbec, O.C., Crothers, D.M., Gralla, J.: Improved estimation of secondary structure in ribonucleic-acid. Nat. New Biol. 246(150), 40\u201341 (1973)","journal-title":"Nat. New Biol."},{"key":"20_CR29","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/0025-5564(78)90099-8","volume":"42","author":"MS Waterman","year":"1978","unstructured":"Waterman, M.S., Smith, T.F.: RNA secondary structure: a complete mathematical analysis. Math. Biosci. 42, 257\u2013266 (1978)","journal-title":"Math. Biosci."},{"issue":"6","key":"20_CR30","doi-asserted-by":"publisher","first-page":"856","DOI":"10.1089\/cmb.2007.R020","volume":"14","author":"Y Wexler","year":"2007","unstructured":"Wexler, Y., Zilberstein, C.: A study of accessible motifs and RNA folding complexity. J. Comput. Biol. 14(6), 856\u2013872 (2007)","journal-title":"J. Comput. Biol."},{"key":"20_CR31","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)"},{"key":"20_CR32","doi-asserted-by":"crossref","unstructured":"Williams, R.: Faster all-pairs shortest paths via circuit complexity. In: Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31\u2013June 03 2014, pp. 664\u2013673 (2014)","DOI":"10.1145\/2591796.2591811"},{"issue":"42","key":"20_CR33","doi-asserted-by":"publisher","first-page":"14719","DOI":"10.1021\/bi9809425","volume":"37","author":"T Xia","year":"1998","unstructured":"Xia, T., SantaLucia, J., Burkard, M.E., Kierzek, R., Schroeder, S.J., Jiao, X., Cox, C., Turner, D.H.: Thermodynamic parameters for an expanded nearest-neighbor model for formation of RNA duplexes with watson-crick base pairs. Biochemistry 37(42), 14719\u201314735 (1998)","journal-title":"Biochemistry"},{"key":"20_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/978-3-642-15294-8_6","volume-title":"Algorithms in Bioinformatics","author":"S Zakov","year":"2010","unstructured":"Zakov, S., Tsur, D., Ziv-Ukelson, M.: Reducing the worst case running times of a family of RNA and CFG problems, using valiant\u2019s approach. In: Moulton, V., Singh, M. (eds.) WABI 2010. LNCS, vol. 6293, pp. 65\u201377. Springer, Heidelberg (2010)"},{"key":"20_CR35","series-title":"Lecture Notes in Computer Science (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. 5251, pp. 174\u2013185. Springer, Heidelberg (2008)"},{"key":"20_CR36","first-page":"159","volume-title":"Mathematical Methods for DNA Sequences","author":"M Zuker","year":"1989","unstructured":"Zuker, M.: The use of dynamic programming algorithms in RNA secondary structure prediction. In: Waterman, M.S. (ed.) Mathematical Methods for DNA Sequences, pp. 159\u2013184. CRC Press Inc., Boca Raton (1989). Chapter 7"},{"issue":"13","key":"20_CR37","doi-asserted-by":"publisher","first-page":"3406","DOI":"10.1093\/nar\/gkg595","volume":"31","author":"M Zuker","year":"2003","unstructured":"Zuker, M.: Mfold web server for nucleic acid folding and hybridization prediction. Nucleic Acids Res. 31(13), 3406\u20133415 (2003)","journal-title":"Nucleic Acids Res."},{"issue":"4","key":"20_CR38","doi-asserted-by":"publisher","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. Bull. Math. Biol. 46(4), 591\u2013621 (1984)","journal-title":"Bull. Math. Biol."},{"issue":"1","key":"20_CR39","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1093\/nar\/9.1.133","volume":"9","author":"M Zuker","year":"1981","unstructured":"Zuker, M., Stiegler, P.: Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information. Nucleic Acids Res. 9(1), 133\u2013148 (1981)","journal-title":"Nucleic Acids Res."}],"container-title":["Lecture Notes in Computer Science","Algorithms in Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48221-6_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T07:41:46Z","timestamp":1676965306000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-48221-6_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662482209","9783662482216"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48221-6_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"28 August 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}