{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,21]],"date-time":"2026-05-21T04:54:31Z","timestamp":1779339271768,"version":"3.51.4"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"published-print":{"date-parts":[[2014,1]]},"DOI":"10.1186\/1748-7188-9-5","type":"journal-article","created":{"date-parts":[[2014,3,6]],"date-time":"2014-03-06T20:01:14Z","timestamp":1394136074000},"source":"Crossref","is-referenced-by-count":18,"title":["Faster algorithms for RNA-folding using the Four-Russians method"],"prefix":"10.1186","volume":"9","author":[{"given":"Balaji","family":"Venkatachalam","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dan","family":"Gusfield","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yelena","family":"Frid","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,3,6]]},"reference":[{"issue":"2\u20133","key":"226_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. 1999, 3 (2\u20133): 321-336.","journal-title":"J Comb Optim"},{"key":"226_CR2","first-page":"65","volume-title":"WABI","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. WABI. 2010, 65-77."},{"issue":"11","key":"226_CR3","first-page":"1209","volume":"194","author":"V Arlazarov","year":"1970","unstructured":"Arlazarov V, Dinic E, Kronrod M, Faradzev I: On economical construction of the transitive closure of a directed graph (in Russian). Dokl Akad Nauk. 1970, 194 (11): 1209-1210.","journal-title":"Dokl Akad Nauk"},{"key":"226_CR4","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(n3)-time algorithm for RNA folding using the Four-Russians Speedup. Algorithms Mol Biol. 2010, 5: 13-","journal-title":"Algorithms Mol Biol"},{"key":"226_CR5","first-page":"120","volume-title":"ISSPIT","author":"DJ Chang","year":"2010","unstructured":"Chang DJ, Kimmer C, Ouyang M: Accelerating the Nussinov RNA folding algorithm with CUDA\/GPU. ISSPIT. 2010, 120-125. IEEE"},{"key":"226_CR6","first-page":"1004","volume-title":"International Conference on, Computational Science, vol. 5544","author":"G Rizk","year":"2009","unstructured":"Rizk G, Lavenier D: GPU accelerated RNA folding algorithm. International Conference on, Computational Science, vol. 5544. Edited by: Gabrielle A, Nabrzyski J, Seidel E, Albada GD, Dongarra J, Sloot PMA. 2009, 1004-1013. Berlin Heidelberg: Springer"},{"key":"226_CR7","first-page":"279","volume-title":"ICT Innovations, vol. 150","author":"M Stojanovski","year":"2011","unstructured":"Stojanovski M, Gjorgjevikj D, Madjarov G: Parallelization of dynamic programming in Nussinov RNA folding algorithm on the CUDA GPU. ICT Innovations, vol. 150. Edited by: Kocarev L. 2011, 279-289. Berlin Heidelberg: Springers"},{"key":"226_CR8","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1137\/0135006","volume":"35","author":"R Nussinov","year":"1978","unstructured":"Nussinov R, Pieczenik G, Griggs JR, Kleitman DJ: Algorithms for loop matchings. SIAM J Appl Math. 1978, 35: 68-82. 10.1137\/0135006.","journal-title":"SIAM J Appl Math"},{"issue":"11","key":"226_CR9","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 AB: Fast algorithm for predicting the secondary structure of single-stranded RNA. PNAS. 1980, 77 (11): 6309-6313.","journal-title":"PNAS"},{"key":"226_CR10","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. 1981, 9: 133-148.","journal-title":"Nucleic Acids Res"},{"issue":"150","key":"226_CR11","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1038\/newbio246040a0","volume":"246","author":"I Tinoco","year":"1973","unstructured":"Tinoco I, Borer PN, Dengler B, Levine MD, Uhlenbeck OC, Crothers DM, Gralla J: Improved estimation of secondary structure in ribonucleic-acids. Nat-New Biol. 1973, 246 (150): 40-41. 10.1038\/newbio246040a0.","journal-title":"Nat-New Biol"},{"issue":"19","key":"226_CR12","doi-asserted-by":"publisher","first-page":"7287","DOI":"10.1073\/pnas.0401799101","volume":"101","author":"DH Mathews","year":"2004","unstructured":"Mathews DH, Disney MD, Childs JL, Schroeder SJ, Zuker M, Turner: Incorporating chemical modification constraints into a dynamic programming algorithm for prediction of RNA secondary structure. PNAS. 2004, 101 (19): 7287-7292.","journal-title":"PNAS"},{"key":"226_CR13","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-1-60327-429-6_1","volume":"453","author":"NR Markham","year":"2008","unstructured":"Markham NR, Zuker M: UNAFold. Bioinformatics. 2008, 453: 3-31. 10.1007\/978-1-60327-429-6_1.","journal-title":"Bioinformatics"},{"issue":"13","key":"226_CR14","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. 2003, 31 (13): 3406-3415.","journal-title":"Nucleic Acids Res"},{"issue":"13","key":"226_CR15","doi-asserted-by":"publisher","first-page":"3429","DOI":"10.1093\/nar\/gkg599","volume":"31","author":"IL Hofacker","year":"2003","unstructured":"Hofacker IL: Vienna RNA secondary structure server. Nucleic Acids Res. 2003, 31 (13): 3429-3431.","journal-title":"Nucleic Acids Res"},{"key":"226_CR16","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: RNAstructure: software for RNA secondary structure prediction and analysis. BMC Bioinformatics. 2010, 11: 129-","journal-title":"BMC Bioinformatics"},{"key":"226_CR17","doi-asserted-by":"crossref","unstructured":"Durbin R, Eddy SR, Krogh A, Mitchison G: Biological Sequence Analysis. Probabilistic Models of Proteins and Nucleic Acids:. Cambridge University Press; 1998s","DOI":"10.1017\/CBO9780511790492"},{"key":"226_CR18","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 Bioinformatics. 2004, 5: 71-","journal-title":"BMC Bioinformatics"},{"issue":"10","key":"226_CR19","doi-asserted-by":"publisher","first-page":"1805","DOI":"10.1261\/rna.1643609","volume":"15","author":"ZJ Lu","year":"2009","unstructured":"Lu ZJ, Gloor JW, Mathews DH: Improved RNA secondary structure prediction by maximizing expected pair accuracy. RNA. 2009, 15 (10): 1805-1813.","journal-title":"RNA"},{"issue":"13","key":"226_CR20","doi-asserted-by":"publisher","first-page":"3423","DOI":"10.1093\/nar\/gkg614","volume":"31","author":"B Knudsen","year":"2003","unstructured":"Knudsen B, Hein J: Pfold: RNA secondary structure prediction using stochastic context-free grammars. Nucleic Acids Res. 2003, 31 (13): 3423-3428.","journal-title":"Nucleic Acids Res"},{"issue":"14","key":"226_CR21","doi-asserted-by":"publisher","first-page":"e90","DOI":"10.1093\/bioinformatics\/btl246","volume":"22","author":"CB Do","year":"2006","unstructured":"Do CB, Woods DA, Batzoglou S: CONTRAfold: RNA secondary structure prediction without physics-based models. Bioinformatics. 2006, 22 (14): e90-e98.","journal-title":"Bioinformatics"},{"issue":"24","key":"226_CR22","doi-asserted-by":"publisher","first-page":"7280","DOI":"10.1093\/nar\/gkg938","volume":"31","author":"Y Ding","year":"2003","unstructured":"Ding Y, Lawrence CE: A statistical sampling algorithm for RNA secondary structure prediction. Nucleic Acids Res. 2003, 31 (24): 7280-7301.","journal-title":"Nucleic Acids Res"},{"issue":"4","key":"226_CR23","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1093\/bioinformatics\/btn601","volume":"25","author":"M Hamada","year":"2009","unstructured":"Hamada M, Kiryu H, Sato K, Mituyama T, Asai K: Prediction of RNA secondary structure using generalized centroid estimators. Bioinformatics. 2009, 25 (4): 465-473.","journal-title":"Bioinformatics"},{"issue":"13","key":"226_CR24","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 HH, Mathews DH, Murphy KP: Efficient parameter estimation for RNA secondary structure prediction. Bioinformatics. 2007, 23 (13): i19-i28.","journal-title":"Bioinformatics"},{"issue":"12","key":"226_CR25","doi-asserted-by":"publisher","first-page":"2304","DOI":"10.1261\/rna.1950510","volume":"16","author":"M Andronescu","year":"2010","unstructured":"Andronescu M, Condon A, Hoos HH, Mathews DH, Murphy KP: Computational approaches for RNA energy parameter estimation. RNA. 2010, 16 (12): 2304-2318.","journal-title":"RNA"},{"key":"226_CR26","first-page":"546","volume-title":"Research in Computational Molecular Biology (RECOMB), Volume 6577, Lecture Notes in, Computer Science","author":"S Zakov","year":"2011","unstructured":"Zakov S, Goldberg Y, Elhadad M, Ziv-Ukelson M: Rich parameterization improves RNA, structure prediction. Research in Computational Molecular Biology (RECOMB), Volume 6577, Lecture Notes in, Computer Science. Edited by: Bafna V, Sahinalp SC. 2011, 546-562. Springer"},{"issue":"6","key":"226_CR27","doi-asserted-by":"publisher","first-page":"856","DOI":"10.1089\/cmb.2007.R020","volume":"14","author":"Y Wexler","year":"2007","unstructured":"Wexler Y, Zilberstein CBZ, Ziv-Ukelson M: A study of accessible motifs and RNA folding complexity. J Comput Biol. 2007, 14 (6): 856-872.","journal-title":"J Comput Biol"},{"key":"226_CR28","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. 2011, 9: 12-31. 10.1016\/j.jda.2010.09.001.","journal-title":"J Discrete Algorithms"},{"key":"226_CR29","doi-asserted-by":"crossref","unstructured":"Venkatachalam B, Frid Y, Gusfield D: Faster algorithms for RNA-folding using the Four-Russians method. UC Davis Technical report 2013S","DOI":"10.1007\/978-3-642-40453-5_11"},{"key":"226_CR30","first-page":"1","volume-title":"WABI","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. WABI. 2010, 1-12."},{"key":"226_CR31","first-page":"176","volume-title":"COCOA, vol. 7402","author":"Y Frid","year":"2012","unstructured":"Frid Y, Gusfield D: Speedup of RNA pseudoknotted secondary structure recurrence computation with the Four-Russians method. COCOA, vol. 7402. Edited by: Lin G. 2012, 176-187."}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/1748-7188-9-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,8]],"date-time":"2019-08-08T05:55:02Z","timestamp":1565243702000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/1748-7188-9-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["226"],"URL":"https:\/\/doi.org\/10.1186\/1748-7188-9-5","relation":{},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1]]},"article-number":"5"}}