{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:40:00Z","timestamp":1725496800834},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540653851"},{"type":"electronic","value":"9783540493815"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/3-540-49381-6_36","type":"book-chapter","created":{"date-parts":[[2007,12,3]],"date-time":"2007-12-03T01:47:50Z","timestamp":1196646470000},"page":"338-347","source":"Crossref","is-referenced-by-count":1,"title":["Approximation and Exact Algorithms for RNA Secondary Structure Prediction and Recognition of Stochastic Context-Free Languages"],"prefix":"10.1007","author":[{"given":"Tatsuya","family":"Akutsu","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,3,29]]},"reference":[{"key":"36_CR1","first-page":"173","volume-title":"Genome Informatics 1997","author":"T. Akutsu","year":"1997","unstructured":"Akutsu, T.: DP Algorithms for RNA Secondary Structure Prediction with Pseudoknots. In: Genome Informatics 1997. Universal Academy Press, Tokyo(1997) 173\u2013179"},{"key":"36_CR2","unstructured":"Alon, N., Galil, Z., Margalit, O.: On the Exponent of the All Pairs Shortest Path Problem. In: Proc. 32nd IEEE Symp. Found. Comput. Sci. (1991) 569\u2013575"},{"key":"36_CR3","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","volume":"9","author":"D. Coppersmith","year":"1990","unstructured":"Coppersmith, D., Winograd, S.: Matrix Multiplication via Arithmetic Progression. J. Symbolic Computation 9 (1990) 251\u2013280","journal-title":"J. Symbolic Computation"},{"key":"36_CR4","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1145\/146637.146656","volume":"39","author":"D. Eppstein","year":"1992","unstructured":"Eppstein, D., Galil, Z., Giancarlo, R., Italiano, G.F.: Sparse Dynamic Programming II: Convex and Concave Cost Functions. J. ACM 39 (1992) 546\u2013567","journal-title":"J. ACM"},{"key":"36_CR5","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1137\/0205006","volume":"5","author":"M.L. Fredman","year":"1976","unstructured":"Fredman, M.L.: New Bounds on the Complexity of the Shortest Path Problem. SIAM Journal on Computing 5 (1976) 83\u201389","journal-title":"SIAM Journal on Computing"},{"key":"36_CR6","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1093\/nar\/10.1.265","volume":"10","author":"M. Kanehisa","year":"1982","unstructured":"Kanehisa, M., Goad, W.B.: Pattern Recognition in Nucleic Acid Sequences II: an Efficient Method for Finding Locally Stable Secondary Structures. Nucleic Acids Research 10 (1982) 265\u2013277","journal-title":"Nucleic Acids Research"},{"key":"36_CR7","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1016\/0196-6774(91)90016-R","volume":"12","author":"L.L. Larmore","year":"1991","unstructured":"Larmore, L.L., Schieber, B.: On-line Dynamic Programming with Applications to the Prediction of RNA Secondary Structure. J. Algorithms 12 (1991) 490\u2013515","journal-title":"J. Algorithms"},{"key":"36_CR8","doi-asserted-by":"publisher","first-page":"5112","DOI":"10.1093\/nar\/22.23.5112","volume":"22","author":"Y. Sakakibara","year":"1994","unstructured":"Sakakibara, Y., Brown, M., Hughey, E., Mian, I.S., Sjl\/:olander, K., Underwood, R.C., Haussler, D.: Stochastic Context-Free Grammars for tRNA Modeling. Nucleic Acids Research 22 (1994) 5112\u20135120","journal-title":"Nucleic Acids Research"},{"key":"36_CR9","volume-title":"Introduction to Computational Molecular Biology","author":"J. Setubal","year":"1997","unstructured":"Setubal, J., Meidanis, J.: Introduction to Computational Molecular Biology. PWS Pub. Co., Boston (1997)"},{"key":"36_CR10","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0020-0190(92)90200-F","volume":"43","author":"T. Takaoka","year":"1992","unstructured":"Takaoka, T.: A New Upper Bound on the Complexity of All Pairs Shortest Path Problem. Information Processing Letters 43 (1992) 195\u2013199","journal-title":"Information Processing Letters"},{"key":"36_CR11","unstructured":"Tamaki, H., Tokuyama, T.: Algorithms for Maximum Subarray Problem Based on Matrix Multiplication. In: Proc. 9th ACM-SIAM Symp. Disc. Alg. (1998) 446\u2013452"},{"key":"36_CR12","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1146\/annurev.bb.17.060188.001123","volume":"17","author":"D.H. Turner","year":"1988","unstructured":"Turner, D.H., Sugimoto, N., Freier, S.M.: RNA Structure Prediction. Ann. Rev. Biophys. Biophys. Chem. 17 (1988) 167\u2013192","journal-title":"Ann. Rev. Biophys. Biophys. Chem."},{"key":"36_CR13","first-page":"67","volume-title":"Proc. Genome Informatics Workshop VI","author":"Y. Uemura","year":"1995","unstructured":"Uemura, Y., Hasegawa, A., Kobayashi, S., Yokomori, T.: Grammatically Modeling and Predicting RNA Secondary Structures. In: Proc. Genome Informatics Workshop VI. Universal Academy Press, Tokyo (1995) 67\u201376"},{"key":"36_CR14","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1016\/S0022-0000(75)80046-8","volume":"10","author":"L.G. Valiant","year":"1975","unstructured":"Valiant, L.G.: General Context-Free Recognition in Less Than Cubic Time. Journal of Computer and System Sciences 10 (1975) 308\u2013315","journal-title":"Journal of Computer and System Sciences"},{"key":"36_CR15","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/0025-5564(78)90099-8","volume":"41","author":"M.S. Waterman","year":"1978","unstructured":"Waterman, M.S., Smith, T.F.: RNA Secondary Structure: a Complete Mathematical Analysis. Math. Biosciences 41 (1978) 257\u2013266","journal-title":"Math. Biosciences"},{"key":"36_CR16","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1016\/0196-8858(86)90025-4","volume":"7","author":"M.S. Waterman","year":"1986","unstructured":"Waterman, M.S., Smith, T.F.: Rapid Dynamic Programming Algorithms for RNA Secondary Structure. Advances in Applied Mathematics 7 (1986) 455\u2013464","journal-title":"Advances in Applied Mathematics"},{"key":"36_CR17","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":"Waterman, M.S.: Introduction to Computational Biology. Capman & Hall, London (1995)"},{"key":"36_CR18","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 for Large RNA Sequences Using Thermodynamics and Auxiliary Information. Nucleic Acids Research 9 (1981) 133\u2013148","journal-title":"Nucleic Acids Research"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-49381-6_36","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,26]],"date-time":"2019-02-26T00:19:12Z","timestamp":1551140352000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-49381-6_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540653851","9783540493815"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-49381-6_36","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1998]]}}}