{"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":1779339271763,"version":"3.51.4"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,8,5]],"date-time":"2016-08-05T00:00:00Z","timestamp":1470355200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"},{"start":{"date-parts":[[2016,8,5]],"date-time":"2016-08-05T00:00:00Z","timestamp":1470355200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-1219278"],"award-info":[{"award-number":["IIS-1219278"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"published-print":{"date-parts":[[2016,12]]},"DOI":"10.1186\/s13015-016-0081-9","type":"journal-article","created":{"date-parts":[[2016,8,5]],"date-time":"2016-08-05T02:06:21Z","timestamp":1470362781000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["An improved Four-Russians method and sparsified Four-Russians algorithm for RNA folding"],"prefix":"10.1186","volume":"11","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":[[2016,8,5]]},"reference":[{"issue":"2\u20133","key":"81_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\u201336.","journal-title":"J Comb Optim"},{"key":"81_CR2","doi-asserted-by":"publisher","unstructured":"Andronescu M, Condon A, Hoos H, Mathews D, Murphy KP. Efficient parameter estimation for RNA secondary structure prediction. Bioinformatics. 2007;23(13):i19\u201328. doi:  \n                    10.1093\/bioinformatics\/btm223\n                    \n                  . \n                    http:\/\/bioinformatics.oxfordjournals.org\/content\/23\/13\/i19.abstract","DOI":"10.1093\/bioinformatics\/btm223"},{"key":"81_CR3","doi-asserted-by":"crossref","unstructured":"Backofen R, Tsur D, Zakov S, Ziv-Ukelson M (2009) Sparse RNA folding: time and space efficient algorithms. In: CPM09; 2009. p. 249\u201362","DOI":"10.1007\/978-3-642-02441-2_22"},{"issue":"1","key":"81_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. 2011;9(1):12\u201331. doi:\n                    10.1016\/j.jda.2010.09.001\n                    \n                  .","journal-title":"J Discrete Algorithms"},{"key":"81_CR5","doi-asserted-by":"crossref","unstructured":"Chan T. Speeding up the Four Russians algorithm by about one more logarithmic factor. In: SODA; 2015. p. 212\u201317","DOI":"10.1137\/1.9781611973730.16"},{"key":"81_CR6","doi-asserted-by":"publisher","unstructured":"Do C, Woods D, Batzoglou S. Contrafold: RNA secondary structure prediction without physics-based models. Bioinformatics. 2006;22(14):e90\u20138. doi:\n                    10.1093\/bioinformatics\/btl246\n                    \n                  . \n                    http:\/\/bioinformatics.oxfordjournals.org\/content\/22\/14\/e90.abstract\n                    \n                  .","DOI":"10.1093\/bioinformatics\/btl246"},{"key":"81_CR7","doi-asserted-by":"publisher","unstructured":"Dowell R, Eddy S. Evaluation of several lightweight stochastic context-free grammars for RNA secondary structure prediction. BMC Bioinformatics. 2004;5(1):71. doi:\n                    10.1186\/1471-2105-5-71\n                    \n                  . \n                    http:\/\/www.biomedcentral.com\/1471-2105\/5\/71\n                    \n                  .","DOI":"10.1186\/1471-2105-5-71"},{"key":"81_CR8","doi-asserted-by":"crossref","unstructured":"Durbin R, Eddy S, Krogh A, Mitchison G . Biological sequence analysis: probabilistic models of proteins and nucleic acids. Cambridge: Cambridge University Press; 1998. \n                    http:\/\/www.amazon.com\/Biological-Sequence-Analysis-Probabilistic-Proteins\/dp\/0521629713","DOI":"10.1017\/CBO9780511790492"},{"key":"81_CR9","doi-asserted-by":"crossref","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. In: WABI; 2009. p. 97\u2013107","DOI":"10.1007\/978-3-642-04241-6_9"},{"issue":"1","key":"81_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. 2010a;5(1):13.","journal-title":"Algorithms Mol Biol"},{"key":"81_CR11","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, editors. Algorithms in bioinformatics. Heidelberg: Springer; 2010b. p. 1\u201312."},{"key":"81_CR12","doi-asserted-by":"crossref","unstructured":"Frid Y, Gusfield D. Speedup of RNA pseudoknotted secondary structure recurrence computation with the four-Russians Method. In: COCOA; 2012. p. 176\u201387","DOI":"10.1007\/978-3-642-31770-5_16"},{"issue":"4","key":"81_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. 1999;289(4):935\u201347.","journal-title":"J Mol Biol"},{"key":"81_CR14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25740-7","volume-title":"RNA 3D structure analysis and prediction","author":"NB Leontis","year":"2012","unstructured":"Leontis NB, Westhof E. RNA 3D structure analysis and prediction. Berlin: Springer; 2012."},{"key":"81_CR15","first-page":"3","volume-title":"Bioinformatics, methods in molecular biology","author":"NR Markham","year":"2008","unstructured":"Markham NR, Zuker M. UNAFold. In: Keith JM, editor. Bioinformatics, methods in molecular biology. New York: Humana Press; 2008. p. 3\u201331."},{"key":"81_CR16","doi-asserted-by":"crossref","unstructured":"Mathews D, Andre T, Kim J, Turner D, Zuker M. An updated recursive algorithm for RNA secondary structure prediction with improved thermodynamic parameters. Mol Modeling Nucleic Acids: 246\u201357","DOI":"10.1021\/bk-1998-0682.ch015"},{"key":"81_CR17","doi-asserted-by":"publisher","unstructured":"Mathews DH, Sabina J, Zuker M, Turner D. Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structure. J Mol Biol. 1999;288(5):911\u201340. doi:\n                    10.1006\/jmbi.1999.2700\n                    \n                  . \n                    http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0022283699927006\n                    \n                  .","DOI":"10.1006\/jmbi.1999.2700"},{"key":"81_CR18","doi-asserted-by":"publisher","unstructured":"Mathews DH, Disney MD, Childs J, Schroeder S, Zuker M, Turner DH. Incorporating chemical modification constraints into a dynamic programming algorithm for prediction of RNA secondary structure. Proceedings of the National Academy of Sciences of the United States of America. 2004;101(19):7287\u201392. doi:\n                    10.1073\/pnas.0401799101\n                    \n                  . \n                    http:\/\/www.pnas.org\/content\/101\/19\/7287.abstract\n                    \n                  .","DOI":"10.1073\/pnas.0401799101"},{"key":"81_CR19","doi-asserted-by":"publisher","unstructured":"McCaskill JS. The equilibrium partition function and base pair binding probabilities for RNA secondary structure. Biopolymers. 1990;29(6\u20137):1105\u201319. doi:\n                    10.1002\/bip.360290621\n                    \n                  . \n                    http:\/\/dx.doi.org\/10.1002\/bip.360290621\n                    \n                  .","DOI":"10.1002\/bip.360290621"},{"key":"81_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. Sparsification of RNA structure prediction including pseudoknots. Algorithms Mol Biol. 2010;5:39.","journal-title":"Algorithms Mol Biol"},{"key":"81_CR21","first-page":"40","volume-title":"WABI","author":"R Salari","year":"2010","unstructured":"Salari R, Will S, Backofen R, Sahinalp S, M\u00f6hl M. Sparsification of RNA structure prediction including pseudoknots. In: Moulton V, Singh M, editors. WABI. Berlin: Springer; 2010. p. 40\u201351."},{"key":"81_CR22","doi-asserted-by":"publisher","unstructured":"Nussinov R, Jacobson A. Fast algorithm for predicting the secondary structure of single-stranded RNA. PNAS. 1980;77(11):6309\u201313. doi:\n                    10.1073\/pnas.77.11.6309\n                    \n                  . \n                    http:\/\/dx.doi.org\/10.1073\/pnas.77.11.6309\n                    \n                  .","DOI":"10.1073\/pnas.77.11.6309"},{"key":"81_CR23","doi-asserted-by":"publisher","unstructured":"Nussinov R, Pieczenik G, Griggs JR, Kleitman DJ. Algorithms for loop matchings. SIAM J Applied Math. 1978;35(1):68\u201382. doi:\n                    10.1137\/0135006\n                    \n                  . \n                    http:\/\/link.aip.org\/link\/?SMM\/35\/68\/1\n                    \n                  .","DOI":"10.1137\/0135006"},{"key":"81_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. 2013;8:27.","journal-title":"Algorithms Mol Biol"},{"key":"81_CR25","doi-asserted-by":"publisher","unstructured":"Reuter J, Mathews D. RNAstructure: software for RNA secondary structure prediction and analysis. BMC Bioinformatics. 2010;11(1):129. doi:\n                    10.1186\/1471-2105-11-129\n                    \n                  . \n                    http:\/\/www.biomedcentral.com\/1471-2105\/11\/129\n                    \n                  .","DOI":"10.1186\/1471-2105-11-129"},{"key":"81_CR26","doi-asserted-by":"crossref","unstructured":"Salari R, M\u00f6hl M, Will S, Sahinalp S, Backofen R. Time and space efficient RNA\u2013RNA interaction prediction via sparse folding. In: RECOMB; 2010. p. 473\u201390","DOI":"10.1007\/978-3-642-12683-3_31"},{"key":"81_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 JB, Mainville S, Cedergreen R. Fast algorithms to determine RNA secondary structures containing multiple loops. In: Sankoff D, Kruskal JB, editors. Time warps, string edits and macromolecules: the theory and practice of sequence comparison. Boston: Addison-Wesley; 1983. p. 93\u2013120."},{"issue":"150","key":"81_CR28","first-page":"40","volume":"246","author":"I Tinoco","year":"1973","unstructured":"Tinoco I, Borer P, Dengler B, Levine M, Uhlenbec O, Crothers D, Gralla J. Improved estimation of secondary structure in ribonucleic-acids. Nature. 1973;246(150):40\u20131.","journal-title":"Nature"},{"key":"81_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 MS, Smith TF. RNA secondary structure: a complete mathematical analysis. Math Biosc. 1978;42:257\u201366.","journal-title":"Math Biosc"},{"issue":"6","key":"81_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 CBZ, Ziv-Ukelson M. A study of accessible motifs and RNA folding complexity. J Comput Biol. 2007;14(6):856\u201372.","journal-title":"J Comput Biol"},{"key":"81_CR31","first-page":"995","volume-title":"Bansal N","author":"R Williams","year":"2007","unstructured":"Williams R. Matrix-vector multiplication in sub-quadratic time: (some preprocessing required). In: Pruhs K, Stein C, editors. Bansal N. SIAM: SODA; 2007. p. 995\u20131001."},{"key":"81_CR32","doi-asserted-by":"publisher","unstructured":"Williams R. Faster all-pairs shortest paths via circuit complexity. In: Symposium on theory of computing. STOC: New York; 2014. p. 664\u201373. doi:\n                    10.1145\/2591796.2591811\n                    \n                  . \n                    http:\/\/doi.acm.org\/10.1145\/2591796.2591811","DOI":"10.1145\/2591796.2591811"},{"key":"81_CR33","doi-asserted-by":"publisher","unstructured":"Xia T, SantaLucia J, Burkard M, Kierzek R, Schroeder S, Jiao X, Cox C, Turner D. Thermodynamic parameters for an expanded nearest-neighbor model for formation of RNA duplexes with watson-crick base pairs. Biochemistry. 1998;37(42):14,719\u201314,735. doi:\n                    10.1021\/bi9809425\n                    \n                  . \n                    http:\/\/pubs.acs.org\/doi\/abs\/10.1021\/bi9809425","DOI":"10.1021\/bi9809425"},{"key":"81_CR34","doi-asserted-by":"crossref","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: WABI; 2010. p. 65\u201377","DOI":"10.1007\/978-3-642-15294-8_6"},{"key":"81_CR35","doi-asserted-by":"crossref","unstructured":"Ziv-Ukelson M, Gat-Viks I, Wexler Y, Shamir R. A faster algorithm for RNA Co-folding. In: Proceedings of the 8th International workshop on algorithms in bioinformatics. Waterville: WABI; 2008. p. 174\u201385","DOI":"10.1007\/978-3-540-87361-7_15"},{"key":"81_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, editor. Mathematical methods for DNA sequences. Boca Raton: CRC Press, Inc.; 1989. p. 159\u201384."},{"key":"81_CR37","doi-asserted-by":"publisher","unstructured":"Zuker M. Mfold web server for nucleic acid folding and hybridization prediction. Nucleic Acids Res. 2003;31(13):3406\u20133415. doi:\n                    10.1093\/nar\/gkg595\n                    \n                  . \n                    http:\/\/nar.oxfordjournals.org\/content\/31\/13\/3406.full.pdf+html","DOI":"10.1093\/nar\/gkg595"},{"issue":"4","key":"81_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. 1984;46(4):591\u2013621.","journal-title":"Bull Math Biol"},{"issue":"1","key":"81_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. 1981;9(1):133\u201348.","journal-title":"Nucleic Acids Res"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-016-0081-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/s13015-016-0081-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-016-0081-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-016-0081-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,14]],"date-time":"2020-05-14T13:00:49Z","timestamp":1589461249000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-016-0081-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,5]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,12]]}},"alternative-id":["81"],"URL":"https:\/\/doi.org\/10.1186\/s13015-016-0081-9","relation":{},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,8,5]]},"assertion":[{"value":"15 December 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 June 2016","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 August 2016","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"22"}}