{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T05:08:12Z","timestamp":1773724092237,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":47,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540580942","type":"print"},{"value":"9783540484509","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58094-8_25","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T10:12:30Z","timestamp":1330251150000},"page":"289-306","source":"Crossref","is-referenced-by-count":11,"title":["Recent methods for RNA modeling using stochastic context-free grammars"],"prefix":"10.1007","author":[{"given":"Yasubumi","family":"Sakakibara","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Brown","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Richard","family":"Hughey","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saira","family":"Mian","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kimmen","family":"Sj\u00f6lander","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rebecca C.","family":"Underwood","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Haussler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"25_CR1","volume-title":"The Theory of Parsing, Translation and Compiling, Vol. I: Parsing","author":"A. V. Aho","year":"1972","unstructured":"A. V. Aho and J. D. Ullman. The Theory of Parsing, Translation and Compiling, Vol. I: Parsing. Prentice Hall, Englewood Cliffs, N.J., 1972."},{"key":"25_CR2","doi-asserted-by":"crossref","unstructured":"J. K. Baker. Trainable grammars for speech recognition. Speech Communication Papers for the 97th Meeting of the Acoustical Society of America, pages 547\u2013550, 1979.","DOI":"10.1121\/1.2017061"},{"key":"25_CR3","doi-asserted-by":"crossref","first-page":"3855","DOI":"10.1128\/jb.173.12.3855-3863.1991","volume":"173","author":"J. W. Brown","year":"1991","unstructured":"J. W. Brown, E. S. Haas, B. D. James, D. A. Hunt, J. S. Liu, and N. R. Pace. Phylogenetic analysis and evolution of RNase P RNA in proteobacteria. Journal of Bacteriology, 173:3855\u20133863, 1991.","journal-title":"Journal of Bacteriology"},{"key":"25_CR4","unstructured":"M. P. Brown, R. Hughey, A. Krogh, I. S. Mian, K. Sj\u00f6lander, and D. Haussler. Dirichlet mixture priors for HMMs. In preparation, 1993."},{"key":"25_CR5","first-page":"47","volume-title":"Using Dirichlet mixture priors to derive hidden Markov models for protein families","author":"M. P. Brown","year":"1993","unstructured":"M. P. Brown, R. Hughey, A. Krogh, I. S. Mian, K. Sj\u00f6lander, and D. Haussler. Using Dirichlet mixture priors to derive hidden Markov models for protein families. In L. Hunter, D. Searls, and J. Shavlik, editors, Proc. of First Int. Conf. on Intelligent Systems for Molecular Biology, pages 47\u201355, Memo Park, CA, July 1993. AAAI\/MIT Press."},{"key":"25_CR6","doi-asserted-by":"crossref","unstructured":"S. R. Eddy and R. Durbin. RNA sequence analysis using covariance models. Submitted to Nucleic Acids Research, 1994.","DOI":"10.1093\/nar\/22.11.2079"},{"key":"25_CR7","doi-asserted-by":"crossref","unstructured":"J. Engelfriet and G. Rozenberg. Graph grammars based on node rewriting: An introduction to NLC graph grammars. In E. Ehrig, H. J. Kreowski, and G. Rozenberg, editors, Lecture Notes in Computer Science, volume 532, pages 12\u201323. Springer-Verlag, 1991.","DOI":"10.1007\/BFb0017374"},{"key":"25_CR8","volume-title":"Syntactic pattern recognition and applications","author":"K. S. Fu","year":"1982","unstructured":"K. S. Fu. Syntactic pattern recognition and applications. Prentice-Hall, Englewood Cliffs, NJ, 1982."},{"key":"25_CR9","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1038\/256505a0","volume":"256","author":"G. E. Fox","year":"1975","unstructured":"G. E. Fox and C. R. Woese. 5S RNA secondary structure. Nature, 256:505\u2013507, 1975.","journal-title":"Nature"},{"key":"25_CR10","first-page":"259","volume-title":"Nucleic acid and protein sequence analysis, a practical approach","author":"M. Gouy","year":"1987","unstructured":"M. Gouy. Secondary structure prediction of RNA. In M. J. Bishop and C. R. Rawlings, editors, Nucleic acid and protein sequence analysis, a practical approach, pages 259\u2013284. IRL Press, Oxford, England, 1987."},{"key":"25_CR11","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1146\/annurev.ge.22.120188.002131","volume":"22","author":"C. Guthrie","year":"1988","unstructured":"C. Guthrie and B. Patterson. Spliceosomal snRNAs. Annual Review of Genetics, 22:387\u2013419, 1988.","journal-title":"Annual Review of Genetics"},{"key":"25_CR12","doi-asserted-by":"crossref","first-page":"5785","DOI":"10.1093\/nar\/20.21.5785","volume":"20","author":"R. R. Gutell","year":"1992","unstructured":"R. R. Gutell, A. Power, G. Z. Hertz, E. J. Putz, and G. D. Stormo. Identifying constraints on the higher-order structure of RNA: continued development and application of comparative sequence analysis methods. Nucleic Acids Research, 20:5785\u20135795, 1992.","journal-title":"Nucleic Acids Research"},{"key":"25_CR13","first-page":"792","volume-title":"Protein modeling using hidden Markov models: Analysis of globins","author":"D. Haussler","year":"1993","unstructured":"D. Haussler, A. Krogh, I. S. Mian, and K. Sj\u00f6lander. Protein modeling using hidden Markov models: Analysis of globins. In Proceedings of the Hawaii International Conference on System Sciences, volume 1, pages 792\u2013802, Los Alamitos, CA, 1993. IEEE Computer Society Press."},{"key":"25_CR14","volume-title":"Detection of correlations in tRNA sequences with structural implications","author":"T. Klinger","year":"1993","unstructured":"T. Klinger and D. Brutlag. Detection of correlations in tRNA sequences with structural implications. In Lawrence Hunter, David Searls, and Jude Shavlik, editors, First International Conference on Intelligent Systems for Molecular Biology, Menlo Park, 1993. AAAI Press."},{"key":"25_CR15","doi-asserted-by":"crossref","first-page":"1501","DOI":"10.1006\/jmbi.1994.1104","volume":"235","author":"A. Krogh","year":"1994","unstructured":"A. Krogh, M. Brown, I. S. Mian, K. Sj\u00f6lander, and D. Haussler. Hidden Markov models in computational biology: Applications to protein modeling. Journal of Molecular Biology, 235:1501\u20131531, Feb. 1994.","journal-title":"Journal of Molecular Biology"},{"key":"25_CR16","unstructured":"Allan Lapedes. Private communication, 1992."},{"key":"25_CR17","doi-asserted-by":"crossref","first-page":"3021","DOI":"10.1093\/nar\/21.13.3021","volume":"21","author":"N. Larsen","year":"1993","unstructured":"N. Larsen, G. J. Olsen, B. L. Maidak, M. J. McCaughey, R. Overbeek, T. J. Macke, T. L. Marsh, and C. R. Woese. The ribosomal database project. Nucleic Acids Research, 21:3021\u20133023, 1993.","journal-title":"Nucleic Acids Research"},{"key":"25_CR18","volume-title":"A branch-and-bound algorithm for optimal protein threading with pairwise (contact potential) amino acid interactions","author":"R. H. Lathrop","year":"1994","unstructured":"R. H. Lathrop and T. F. Smith. A branch-and-bound algorithm for optimal protein threading with pairwise (contact potential) amino acid interactions. In Proceedings of the 27th Hawaii International Conference on System Sciences, Los Alamitos, CA, 1994. IEEE Computer Society Press."},{"key":"25_CR19","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0885-2308(90)90022-X","volume":"4","author":"K. Lari","year":"1990","unstructured":"K. Lari and S. J. Young. The estimation of stochastic context-free grammars using the inside-outside algorithm. Computer Speech and Language, 4:35\u201356, 1990.","journal-title":"Computer Speech and Language"},{"key":"25_CR20","doi-asserted-by":"crossref","first-page":"578","DOI":"10.1038\/347578a0","volume":"347","author":"F. Michel","year":"1990","unstructured":"F. Michel, A. D. Ellington, S. Couture, and J. W. Szostak. Phylogenetic and genetic evidence for base-triples in the catalytic domain of group I introns. Nature, 347:578\u2013580, 1990.","journal-title":"Nature"},{"key":"25_CR21","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/0378-1119(89)90026-7","volume":"82","author":"F. Michel","year":"1989","unstructured":"F. Michel, K. Umesono, and H. Ozeki. Comparative and functional anatomy of group II catalytic introns-a review. Gene, 82:5\u201330, 1989.","journal-title":"Gene"},{"key":"25_CR22","doi-asserted-by":"crossref","first-page":"585","DOI":"10.1016\/0022-2836(90)90386-Z","volume":"216","author":"F. Michel","year":"1990","unstructured":"F. Michel and E. Westhof. Modelling of the three-dimensional architecture of group I catalytic introns based on comparative sequence analysis. Journal of Molecular Biology, 216:585\u2013610, 1990.","journal-title":"Journal of Molecular Biology"},{"key":"25_CR23","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1137\/0135006","volume":"35","author":"R. Nussinov","year":"1978","unstructured":"R. Nussinov, G. Pieczenik, J. R. Griggs, and D. J. Kleitman. Algorithms for loop matchings. SIAM Journal of Applied Mathematics, 35:68\u201382, 1978.","journal-title":"SIAM Journal of Applied Mathematics"},{"issue":"2","key":"25_CR24","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1109\/5.18626","volume":"77","author":"L. R. Rabiner","year":"1989","unstructured":"L. R. Rabiner. A tutorial on hidden Markov models and selected applications in speech recognition. Proc IEEE, 77(2):257\u2013286, 1989.","journal-title":"Proc IEEE"},{"key":"25_CR25","volume-title":"Springer Advanced Texts in Chemistry","author":"W. Saenger","year":"1984","unstructured":"W. Saenger. Principles of nucleic acid structure. Springer Advanced Texts in Chemistry. Springer-Verlag, New York, 1984."},{"key":"25_CR26","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/0890-5401(92)90003-X","volume":"97","author":"Y. Sakakibara","year":"1992","unstructured":"Y. Sakakibara. Efficient learning of context-free grammars from positive structural examples. Information and Computation, 97:23\u201360, 1992.","journal-title":"Information and Computation"},{"key":"25_CR27","doi-asserted-by":"crossref","first-page":"810","DOI":"10.1137\/0145048","volume":"45","author":"D. Sankoff","year":"1985","unstructured":"D. Sankoff. Simultaneous solution of the RNA folding, alignment and protosequence problems. SIAM J. Appl. Math., 45:810\u2013825, 1985.","journal-title":"SIAM J. Appl. Math."},{"key":"25_CR28","doi-asserted-by":"crossref","unstructured":"Y. Sakakibara, M. Brown, R. Hughey, I. S. Mian, K. Sj\u00f6lander, R. Underwood, and D. Haussler. The application of stochastic context-free grammars to folding, aligning and modeling homologous RNA sequences. Submitted for publication, 1993.","DOI":"10.1109\/HICSS.1994.323568"},{"key":"25_CR29","volume-title":"Stochastic context-free grammars for modeling RNA","author":"Y. Sakakibara","year":"1994","unstructured":"Y. Sakakibara, M. Brown, I. S. Mian, R. Underwood, and D. Haussler. Stochastic context-free grammars for modeling RNA. In Proceedings of the Hawaii International Conference on System Sciences, Los Alamitos, CA, 1994. IEEE Computer Society Press."},{"key":"25_CR30","volume-title":"Stochastic context-free grammars for modeling RNA. Technical Report UCSC-CRL-93-16","author":"Y. Sakakibara","year":"1993","unstructured":"Y. Sakakibara, M. Brown, R. Underwood, I. S. Mian, and D. Haussler. Stochastic context-free grammars for modeling RNA. Technical Report UCSC-CRL-93-16, UC Santa Cruz, Computer and Information Sciences Dept., Santa Cruz, CA 95064, 1993."},{"key":"25_CR31","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1017-7","volume-title":"The Statistical Analysis of Discrete Data","author":"T. J. Santner","year":"1989","unstructured":"T. J. Santner and D. E. Duffy. The Statistical Analysis of Discrete Data. Springer Verlag, New York, 1989."},{"key":"25_CR32","doi-asserted-by":"crossref","unstructured":"D. B. Searls and S. Dong. A syntactic pattern recognition system for DNA sequences. In Proc. 2nd Int. Conf. on Bioinformatics, Supercomputing and complex genome analysis. World Scientific, 1993. In press.","DOI":"10.1142\/9789814503655_0008"},{"key":"25_CR33","first-page":"579","volume":"80","author":"D. B. Searls","year":"1992","unstructured":"David B. Searls. The linguistics of DNA. American Scientist, 80:579\u2013591, November\u2013December 1992.","journal-title":"American Scientist"},{"key":"25_CR34","unstructured":"D. B. Searls. The computational linguistics of biological sequences. In Artificial Intelligence and Molecular Biology, chapter 2, pages 47\u2013120. AAAI Press, 1993."},{"key":"25_CR35","unstructured":"D. B. Searls. String variable grammar: a logic grammar formalism for DNA sequences, 1993. Unpublished."},{"issue":"4","key":"25_CR36","first-page":"309","volume":"6","author":"B. A. Shapiro","year":"1990","unstructured":"B. A. Shapiro and K. Zhang. Comparing multiple RNA secondary structures using tree comparisons. CABIOS, 6(4):309\u2013318, 1990.","journal-title":"CABIOS"},{"key":"25_CR37","doi-asserted-by":"crossref","first-page":"14045","DOI":"10.1016\/S0021-9258(19)85207-9","volume":"268","author":"A. J. Tranguch","year":"1993","unstructured":"A. J. Tranguch and D. R. Engelke. Comparative structural analysis of nuclear RNase P RNAs from yeast. Journal of Biological Chemistry, 268:14045\u20131455, 1993.","journal-title":"Journal of Biological Chemistry"},{"key":"25_CR38","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. RNA structure prediction. Annual Review of Biophysics and Biophysical Chemistry, 17:167\u2013192, 1988.","journal-title":"Annual Review of Biophysics and Biophysical Chemistry"},{"key":"25_CR39","first-page":"363","volume":"230","author":"I. Tinoco Jr.","year":"1971","unstructured":"I. Tinoco Jr., O. C. Uhlenbeck, and M. D. Levine. Estimation of secondary structure in ribonucleic acids. Nature, 230:363\u2013367, 1971.","journal-title":"Nature"},{"key":"25_CR40","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/BF01691346","volume":"2","author":"J. W. Thatcher","year":"1968","unstructured":"J. W. Thatcher and J. B. Wright. Generalized finite automata theory with an application to a decision problem of second-order logic. Mathematical Systems Theory, 2:57\u201381, 1968.","journal-title":"Mathematical Systems Theory"},{"key":"25_CR41","doi-asserted-by":"crossref","first-page":"765","DOI":"10.1016\/S0076-6879(88)64083-3","volume":"164","author":"M. S. Waterman","year":"1988","unstructured":"M. S. Waterman. Computer analysis of nucleic acid sequences. Methods in Enzymology, 164:765\u2013792, 1988.","journal-title":"Methods in Enzymology"},{"key":"25_CR42","unstructured":"M. S. Waterman. Consensus methods for folding single-stranded nucleic acids. In M. S. Waterman, editor, Mathematical Methods for DNA Sequences, chapter 8. CRC Press, 1989."},{"issue":"4","key":"25_CR43","doi-asserted-by":"crossref","first-page":"621","DOI":"10.1128\/MMBR.47.4.621-669.1983","volume":"47","author":"C. R. Woese","year":"1983","unstructured":"C. R. Woese, R. R. Gutell, R. Gupta, and H. F. Noller. Detailed analysis of the higher-order structure of 16S-like ribosomal ribonucleic acids. Microbiology Reviews, 47(4):621\u2013669, 1983.","journal-title":"Microbiology Reviews"},{"key":"25_CR44","first-page":"365","volume":"6","author":"S. Winker","year":"1990","unstructured":"S. Winker, R. Overbeek, C.R. Woese, G.J. Olsen, and N. Pfluger. Structure detection through automated covariance search. Computer Applications in the Biosciences, 6:365\u2013371, 1990.","journal-title":"Computer Applications in the Biosciences"},{"issue":"4","key":"25_CR45","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1002\/bies.950110406","volume":"11","author":"J. R. Wyatt","year":"1989","unstructured":"J. R. Wyatt, J. D. Puglisi, and I. Tinoco Jr. RNA folding: pseudoknots, loops and bulges. BioEssays, 11(4):100\u2013106, 1989.","journal-title":"BioEssays"},{"key":"25_CR46","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1126\/science.2468181","volume":"244","author":"M. Zuker","year":"1989","unstructured":"M. Zuker. On finding all suboptimal foldings of an RNA molecule. Science, 244:48\u201352, 1989.","journal-title":"Science"},{"key":"25_CR47","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/S0079-6603(08)60699-6","volume":"37","author":"C. Zwieb","year":"1989","unstructured":"C. Zwieb. Structure and function of signal recognition particle RNA. Progress in Nucleic Acid Research and Molecular Biology, 37:207\u2013234, 1989.","journal-title":"Progress in Nucleic Acid Research and Molecular Biology"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58094-8_25.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,31]],"date-time":"2021-12-31T00:59:46Z","timestamp":1640912386000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58094-8_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540580942","9783540484509"],"references-count":47,"URL":"https:\/\/doi.org\/10.1007\/3-540-58094-8_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994]]}}}