{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T00:24:36Z","timestamp":1761611076493,"version":"3.41.0"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"2-3","license":[{"start":{"date-parts":[[1999,7,1]],"date-time":"1999-07-01T00:00:00Z","timestamp":930787200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1999,7,1]],"date-time":"1999-07-01T00:00:00Z","timestamp":930787200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Combinatorial Optimization"],"published-print":{"date-parts":[[1999,7]]},"DOI":"10.1023\/a:1009898029639","type":"journal-article","created":{"date-parts":[[2002,12,22]],"date-time":"2002-12-22T23:53:29Z","timestamp":1040601209000},"page":"321-336","source":"Crossref","is-referenced-by-count":20,"title":["Approximation and Exact Algorithms for RNA Secondary Structure Prediction and Recognition of Stochastic Context-free Languages"],"prefix":"10.1007","volume":"3","author":[{"given":"Tatsuya","family":"Akutsu","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"211435_CR1","doi-asserted-by":"crossref","first-page":"3035","DOI":"10.1093\/nar\/18.10.3035","volume":"18","author":"J.P. Abrahams","year":"1990","unstructured":"J.P. Abrahams, M. Berg, E. Batenburg, and C. Pleij, \u201cPrediction of RNA secondary structure, including pseudoknotting by computer simulation,\u201d Nucleic Acids Research, vol. 18, pp. 3035-3044, 1990.","journal-title":"Nucleic Acids Research"},{"key":"211435_CR2","first-page":"173","volume-title":"Genome Informatics 1997","author":"T. Akutsu","year":"1997","unstructured":"T. Akutsu, \u201cDP algorithms for RNA secondary structure prediction with pseudoknots,\u201d Genome Informatics 1997, Universal Academy Press: Tokyo, 1997, pp. 173-179."},{"key":"211435_CR3","unstructured":"N. Alon, Z. Galil, and O. Margalit, \u201cOn the exponent of the all pairs shortest path problem,\u201d in Proc. 32nd IEEE Symp. Foundations of Computer Science, IEEE, 1991, pp. 569-575."},{"key":"211435_CR4","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","volume":"9","author":"D. Coppersmith","year":"1990","unstructured":"D. Coppersmith and S. Winograd, \u201cMatrix multiplication via arithmetic progression,\u201d J. Symbolic Computation, vol. 9, pp. 251-280, 1990.","journal-title":"J. Symbolic Computation"},{"key":"211435_CR5","doi-asserted-by":"crossref","unstructured":"D. Eppstein, Z. Galil, and R. Giancarlo, \u201cSpeeding up dynamic programming,\u201d in Proc. 29th IEEE Symp. Foundations of Computer Science, IEEE, 1988, pp. 488-496.","DOI":"10.1109\/SFCS.1988.21965"},{"key":"211435_CR6","doi-asserted-by":"crossref","first-page":"546","DOI":"10.1145\/146637.146656","volume":"39","author":"D. Eppstein","year":"1992","unstructured":"D. Eppstein, Z. Galil, R. Giancarlo, and G.F. Italiano, \u201cSparse dynamic programming II: Convex and concave cost functions,\u201d J. ACM, vol. 39, pp. 546-567, 1992.","journal-title":"J. ACM"},{"key":"211435_CR7","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1137\/0205006","volume":"5","author":"M.L. Fredman","year":"1976","unstructured":"M.L. Fredman, \u201cNew bounds on the complexity of the shortest path problem,\u201d SIAM Journal on Computing, vol. 5, pp. 83-89, 1976.","journal-title":"SIAM Journal on Computing"},{"key":"211435_CR8","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0304-3975(92)90135-3","volume":"92","author":"Z. Galil","year":"1992","unstructured":"Z. Galil and K. Park, \u201cDynamic programming with convexity, concavity and sparsity,\u201d Theoretical Computer Science, vol. 92, pp. 49-76, 1992.","journal-title":"Theoretical Computer Science"},{"key":"211435_CR9","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1093\/nar\/10.1.265","volume":"10","author":"M. Kanehisa","year":"1982","unstructured":"M. Kanehisa and W.B. Goad, \u201cPattern recognition in nucleic acid sequences II: An efficient method for finding locally stable secondary structures,\u201d Nucleic Acids Research, vol. 10, pp. 265-277, 1982.","journal-title":"Nucleic Acids Research"},{"key":"211435_CR10","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1016\/0196-6774(91)90016-R","volume":"12","author":"L.L. Larmore","year":"1991","unstructured":"L.L. Larmore and B. Schieber, \u201cOn-line dynamic programming with applications to the prediction of RNA secondary structure,\u201d Journal of Algorithms, vol. 12, pp. 490-515, 1991.","journal-title":"Journal of Algorithms"},{"key":"211435_CR11","doi-asserted-by":"crossref","first-page":"5112","DOI":"10.1093\/nar\/22.23.5112","volume":"22","author":"Y. Sakakibara","year":"1994","unstructured":"Y. Sakakibara, M. Brown, E. Hughey, I.S. Mian, K. Sjl\u00f6lander, R.C. Underwood, and D. Haussler, \u201cStochastic context-free grammars for tRNA modeling,\u201d Nucleic Acids Research, vol. 22, pp. 5112-5120, 1994.","journal-title":"Nucleic Acids Research"},{"key":"211435_CR12","volume-title":"Introduction to Computational Molecular Biology","author":"J. Setubal","year":"1997","unstructured":"J. Setubal and J. Meidanis, Introduction to Computational Molecular Biology, PWS Pub. Co.: Boston, 1997."},{"key":"211435_CR13","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0020-0190(92)90200-F","volume":"43","author":"T. Takaoka","year":"1992","unstructured":"T. Takaoka, \u201cA new upper bound on the complexity of all pairs shortest path problem,\u201d Information Processing Letters, vol. 43, pp. 195-199, 1992.","journal-title":"Information Processing Letters"},{"key":"211435_CR14","unstructured":"H. Tamaki and T. Tokuyama, \u201cAlgorithms for maximum subarray problem based on matrix multiplication,\u201d in Proc. 9th ACM-SIAM Symp. Discrete Algorithms, ACM, 1998, pp. 446-452."},{"key":"211435_CR15","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1146\/annurev.bb.17.060188.001123","volume":"17","author":"D.H. Turner","year":"1988","unstructured":"D.H. Turner, N. Sugimoto, and S.M. Freier, \u201cRNA structure prediction,\u201d Ann. Rev. Biophys. Chem., vol. 17, pp. 167-192, 1988.","journal-title":"Ann. Rev. Biophys. Chem."},{"key":"211435_CR16","first-page":"67","volume-title":"Proc. Genome Informatics Workshop VI","author":"Y. Uemura","year":"1995","unstructured":"Y. Uemura, A. Hasegawa, S. Kobayashi, and T. Yokomori, \u201cGrammatically modeling and predicting RNA secondary structures,\u201d in Proc. Genome Informatics Workshop VI, Universal Academy Press: Tokyo, 1995, pp. 67-76."},{"key":"211435_CR17","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1016\/S0022-0000(75)80046-8","volume":"10","author":"L.G. Valiant","year":"1975","unstructured":"L.G.Valiant, \u201cGeneral context-free recognition in less than cubic time,\u201d Journal of Computer and System Sciences, vol. 10, pp. 308-315, 1975.","journal-title":"Journal of Computer and System Sciences"},{"key":"211435_CR18","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/0025-5564(78)90099-8","volume":"41","author":"M.S. Waterman","year":"1978","unstructured":"M.S.Waterman and T.F. Smith, \u201cRNAsecondary structure:Acomplete mathematical analysis,\u201d Math. Biosciences, vol. 41, pp. 257-266, 1978.","journal-title":"Math. Biosciences"},{"key":"211435_CR19","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1016\/0196-8858(86)90025-4","volume":"7","author":"M.S. Waterman","year":"1986","unstructured":"M.S.Waterman and T.F. Smith, \u201cRapid dynamic programming algorithms forRNAsecondary structure,\u201d Advances in Applied Mathematics, vol. 7, pp. 455-464, 1986.","journal-title":"Advances in Applied Mathematics"},{"key":"211435_CR20","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4899-6846-3","volume-title":"Introduction to Computational Biology","author":"M.S. Waterman","year":"1995","unstructured":"M.S. Waterman, Introduction to Computational Biology, Chapman & Hall: London, 1995."},{"key":"211435_CR21","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1093\/nar\/9.1.133","volume":"9","author":"M. Zuker","year":"1981","unstructured":"M. Zuker and P. Stiegler, \u201cOptimal computer folding for largeRNAsequences using thermodynamics and auxiliary information,\u201d Nucleic Acids Research, vol. 9, pp. 133-148, 1981.","journal-title":"Nucleic Acids Research"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1009898029639.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1009898029639\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1009898029639.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,30]],"date-time":"2025-06-30T11:15:09Z","timestamp":1751282109000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1009898029639"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999,7]]},"references-count":21,"journal-issue":{"issue":"2-3","published-print":{"date-parts":[[1999,7]]}},"alternative-id":["211435"],"URL":"https:\/\/doi.org\/10.1023\/a:1009898029639","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[1999,7]]}}}