{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T20:37:19Z","timestamp":1757450239692,"version":"3.40.4"},"publisher-location":"Cham","reference-count":40,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319049205"},{"type":"electronic","value":"9783319049212"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-04921-2_25","type":"book-chapter","created":{"date-parts":[[2014,2,5]],"date-time":"2014-02-05T13:52:25Z","timestamp":1391608345000},"page":"308-322","source":"Crossref","is-referenced-by-count":2,"title":["Stochastic k-Tree Grammar and Its Application in Biomolecular Structure Modeling"],"prefix":"10.1007","author":[{"given":"Liang","family":"Ding","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Abdul","family":"Samad","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xingran","family":"Xue","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiuzhen","family":"Huang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Russell L.","family":"Malmberg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Liming","family":"Cai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"25_CR1","unstructured":"Achawanantakun, R., Takyar, S., Sun, Y.: Grammar string: A novel ncRNA secondary structure representation. lifesciences society org, pp. 2\u201313 (2010)"},{"key":"25_CR2","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/3-540-46154-X_7","volume-title":"Text, Speech and Dialogue","author":"A. Rozenknop","year":"2002","unstructured":"Rozenknop, A.: Gibbsian context-free grammar for parsing. In: Sojka, P., Kope\u010dek, I., Pala, K. (eds.) TSD 2002. LNCS (LNAI), vol.\u00a02448, pp. 49\u201356. Springer, Heidelberg (2002)"},{"issue":"1","key":"25_CR3","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0166-218X(89)90031-0","volume":"23","author":"S. Arnborg","year":"1989","unstructured":"Arnborg, S., Proskurowski, A.: Linear time algorithms for np-hard problems restricted to partial k-trees. Discrete Applied Mathematics\u00a023(1), 11\u201324 (1989)","journal-title":"Discrete Applied Mathematics"},{"issue":"5","key":"25_CR4","doi-asserted-by":"publisher","first-page":"1077","DOI":"10.1089\/cmb.2006.13.1077","volume":"13","author":"D. Chiang","year":"2006","unstructured":"Chiang, D., Joshi, A.K., Searls, D.B.: Grammatical representations of macromolecular structure. Journal of Computational Biology\u00a013(5), 1077\u20131100 (2006)","journal-title":"Journal of Computational Biology"},{"key":"25_CR5","doi-asserted-by":"publisher","first-page":"4289","DOI":"10.1016\/j.polymer.2007.05.018","volume":"48","author":"K.A. Dill","year":"2007","unstructured":"Dill, K.A., Lucas, A., Hockenmaier, J., Huang, L., Chiang, D., Josh, A.K.: Computational linguistics: A new tool for exploring biopolymer structures and statistical mechanics. Polymer\u00a048, 4289\u20134300 (2007)","journal-title":"Polymer"},{"key":"25_CR6","unstructured":"Ding, L., Samad, A., Li, G., Robinson, R., Xue, X., Malmberg, R., Cai, L.: Finding maximum spanning k-trees on backbone graphs in polynomial time (2013) (manuscript)"},{"key":"25_CR7","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer (1999)","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"25_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 University Press (1998)","DOI":"10.1017\/CBO9780511790492"},{"key":"25_CR9","unstructured":"Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley (2007)"},{"key":"25_CR10","unstructured":"Huang, Z., Mohebbi, M., Malmberg, R., Cai, L.: RNAv: Non-coding RNA secondary structure variation search via graph homomorphism. In: Proceedings of Computational Systems Bioinformatics Conference (CSB 2010), vol.\u00a09, pp. 56\u201369 (2010)"},{"issue":"20","key":"25_CR11","doi-asserted-by":"publisher","first-page":"2281","DOI":"10.1093\/bioinformatics\/btn393","volume":"24","author":"Z. Huang","year":"2008","unstructured":"Huang, Z., Wu, Y., Robertson, J., Feng, L., Malmberg, R., Cai, L.: Fast and accurate search for non-coding RNA pseudoknot structures in genomes. Bioinforamtics\u00a024(20), 2281\u20132287 (2008)","journal-title":"Bioinforamtics"},{"key":"25_CR12","doi-asserted-by":"crossref","unstructured":"Thiim, J.F.I.M., Mardia, M., Ferkinghoff-Borg, K., Hamelryck, J.,, T.: A probabilistic model of RNA conformational space. PLoS Comput. Biol.\u00a05(6) (2009)","DOI":"10.1371\/journal.pcbi.1000406"},{"key":"25_CR13","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1017\/CBO9780511597855.007","volume-title":"Natural Language Processing: Theoretical, Computational, and Psychological Perspectives","author":"A. Joshi","year":"1985","unstructured":"Joshi, A.: How much context-sensitivity is necessary for characterizing structural descriptions. In: Dowty, D., Karttunen, L., Zwicky, A. (eds.) Natural Language Processing: Theoretical, Computational, and Psychological Perspectives, pp. 206\u2013250. Cambridge University Press, NY (1985)"},{"key":"25_CR14","series-title":"Issues in Natural Language Processing","first-page":"31","volume-title":"The convergence of mildly context-sensitive grammar formalisms","author":"A. Joshi","year":"1991","unstructured":"Joshi, A., Vijay-Shanker, K., Weir, D.: The convergence of mildly context-sensitive grammar formalisms. Issues in Natural Language Processing, pp. 31\u201381. MIT Press, Cambridge (1991)"},{"key":"25_CR15","doi-asserted-by":"crossref","unstructured":"Jurafsky, D., Wooters, C., Segal, J., Stolcke, A., Fosler, E., Tajchaman, G., Morgan, N.: Using a stochastic context-free grammar as a language model for speech recognition. In: Proceedings of International Conference on Acoustics, Speech and Signal Processing, pp. 189\u2013192 (1995)","DOI":"10.1109\/ICASSP.1995.479396"},{"key":"25_CR16","doi-asserted-by":"crossref","unstructured":"Klein, D., Manning, C.: Accurate unlexicalized parsing. In: Proceedings of the 41st Meeting of the Association for Computational Linguistics, pp. 423\u2013430 (2003)","DOI":"10.3115\/1075096.1075150"},{"key":"25_CR17","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.\u00a031, 3423\u20133428 (2003)","journal-title":"Nucleic Acids Res."},{"key":"25_CR18","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0885-2308(90)90022-X","volume":"4","author":"K. Lari","year":"1990","unstructured":"Lari, K., Young, S.J.: The estimation of stochastic context-free grammars using the inside-outside algorithm. Computer Speech and Language\u00a04, 35\u201356 (1990)","journal-title":"Computer Speech and Language"},{"key":"25_CR19","unstructured":"Martin, D., Sigal, R., Weyuker, E.J.: Computability, complexity, and languages: Fundamentals of theoretical computer science, 2nd edn. Morgan Kaufmann (1994)"},{"issue":"4","key":"25_CR20","first-page":"536","volume":"247","author":"A.G. Murzin","year":"1995","unstructured":"Murzin, A.G., Brenner, S., Hubbard, T., Chothia, C.: Scop: A structural classification of proteins database for the investigation of sequences and structures. Journal of Molecular Biology\u00a0247(4), 536\u2013540 (1995)","journal-title":"Journal of Molecular Biology"},{"key":"25_CR21","doi-asserted-by":"publisher","first-page":"1335","DOI":"10.1093\/bioinformatics\/btp157","volume":"25","author":"E.P. Nawrocki","year":"2009","unstructured":"Nawrocki, E.P., Kolbe, D.L., Eddy, S.R.: Infernal 1.0: Inference of RNA alignments. Bioinformatics\u00a025, 1335\u20131337 (2009)","journal-title":"Bioinformatics"},{"key":"25_CR22","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1146\/annurev.bi.53.070184.001003","volume":"53","author":"H.F. Noller","year":"1984","unstructured":"Noller, H.F.: Structure of ribosomal RNA. Annual Review of Biochemistry\u00a053, 119\u2013162 (1984)","journal-title":"Annual Review of Biochemistry"},{"issue":"2-4","key":"25_CR23","first-page":"57","volume":"11","author":"H.P. Patil","year":"1986","unstructured":"Patil, H.P.: On the structure of k-trees. Journal of Combinatorics, Information and System Sciences\u00a011(2-4), 57\u201364 (1986)","journal-title":"Journal of Combinatorics, Information and System Sciences"},{"key":"25_CR24","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1261\/rna.030049.111","volume":"18","author":"E. Rivas","year":"2012","unstructured":"Rivas, E., Lang, R., Eddy, S.R.: A range of complex probabilistic models for RNA secondary structure prediction that include the nearest neighbor model and more. RNA\u00a018, 193\u2013212 (2012)","journal-title":"RNA"},{"key":"25_CR25","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, R., Mian, I.S., Sjolander, K., Underwood, R.C., Haussler, D.: Stochastic context-free grammars for tRNA modeling. Nucleic Acids Research\u00a022, 5112\u20135120 (1994)","journal-title":"Nucleic Acids Research"},{"key":"25_CR26","unstructured":"Salomaa, A.: Jewels of Formal Language Theory. Computer Science Press (1981)"},{"key":"25_CR27","doi-asserted-by":"crossref","unstructured":"S\u00e1nchez, I.A., Benedi, J.M., Linares, D.: Performance of a scfg-based language model with training data sets of increasing size. In: Proceedings of Conference on Pattern Recognition and Image Analysis, pp. 586\u2013594 (2005)","DOI":"10.1007\/11492542_72"},{"key":"25_CR28","unstructured":"Searls, D.B.: The computational linguistics of biological sequences. Artificial Intelligence and Molecular Biology, pp. 47\u2013120 (1993)"},{"key":"25_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/978-3-642-15488-1_2","volume-title":"Grammatical Inference: Theoretical Results and Applications","author":"D.B. Searls","year":"2010","unstructured":"Searls, D.B.: Molecules, languages and automata. In: Sempere, J.M., Garc\u00eda, P. (eds.) ICGI 2010. LNCS, vol.\u00a06339, pp. 5\u201310. Springer, Heidelberg (2010)"},{"key":"25_CR30","unstructured":"Sergio Caracciolo, S., Masbaum, G., Sokal, A., Sportiello, A.: A randomized polynomial-time algorithm for the spanning hypertree problem on 3-uniform hypergraphs. CoRR abs\/0812.3593 (2008)"},{"issue":"4","key":"25_CR31","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1109\/TCBB.2006.52","volume":"3","author":"Y. Song","year":"2006","unstructured":"Song, Y., Liu, C., Huang, X., Malmberg, R., Xu, Y., Cai, L.: Efficient parameterized algorithms for biopolymer structure-sequence alignment. IEEE\/ACM Transactions on Computational Biology and Bioinformatics\u00a03(4), 423\u2013431 (2006)","journal-title":"IEEE\/ACM Transactions on Computational Biology and Bioinformatics"},{"issue":"2003","key":"25_CR32","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0004-3702(02)00360-0","volume":"143","author":"N. Srebro","year":"2003","unstructured":"Srebro, N.: Maximum likelihood bounded tree-width Markov networks. Artificial Intelligence\u00a0143(2003), 123\u2013138 (2003)","journal-title":"Artificial Intelligence"},{"key":"25_CR33","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/S0304-3975(98)00090-5","volume":"210","author":"Y. Uemura","year":"1999","unstructured":"Uemura, Y., Hasegawa, A., Kobayashi, S., Yokomori, T.: Tree adjoining grammars for RNA structure prediction. Theoretical Computer Science\u00a0210, 277\u2013303 (1999)","journal-title":"Theoretical Computer Science"},{"issue":"6","key":"25_CR34","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1007\/BF01191624","volume":"27","author":"K. Vijay-Shanker","year":"1994","unstructured":"Vijay-Shanker, K., Weir, D.: The equivalence of four extensions of context-free grammars. Mathematical Systems Theory\u00a027(6), 511\u2013546 (1994)","journal-title":"Mathematical Systems Theory"},{"key":"25_CR35","doi-asserted-by":"crossref","unstructured":"Waters, C.J., MacDonald, B.A.: Efficient word-graph parsing and search with a stochastic context-free grammar. In: Proceedings of IEEE Workshop on Automatic Speech Recognition and Understanding, pp. 311\u2013318 (1997)","DOI":"10.1109\/ASRU.1997.659105"},{"issue":"4","key":"25_CR36","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1145\/1162349.1162350","volume":"53","author":"J. Xu","year":"2006","unstructured":"Xu, J., Berger, B.: Fast and accurate algorithms for protein side-chain packing. Journal of the ACM\u00a053(4), 533\u2013557 (2006)","journal-title":"Journal of the ACM"},{"key":"25_CR37","doi-asserted-by":"crossref","unstructured":"Xu, Y., Liu, Z., Cai, L., Xu, D.: Protein structure prediction by protein threading. In: Computational Methods for Protein Structure Prediction and Modeling, pp. 389\u2013430. Springer I&II (2006)","DOI":"10.1007\/978-0-387-68825-1_1"},{"issue":"3","key":"25_CR38","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1016\/j.sbi.2008.02.004","volume":"18","author":"Y.Z. Progress","year":"2008","unstructured":"Progress, Y.Z.: challenges in protein structure prediction. Current Opinions in Structural Biology\u00a018(3), 342\u2013348 (2008)","journal-title":"Current Opinions in Structural Biology"},{"key":"25_CR39","doi-asserted-by":"crossref","unstructured":"Weinberg, Z., Ruzzo, L.: Faster genome annotation of non-coding RNA families without loss of accuracy. In: Proceedings of Conference on Research in Computational Molecular Biology (RECOMB 2004), pp. 243\u2013251 (2004)","DOI":"10.1145\/974614.974647"},{"key":"25_CR40","unstructured":"Zimand, M.: The complexity of the optimal spanning hypertree problem. Technical Report, University of Rochester. Computer Science Department (2004)"}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-04921-2_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,1]],"date-time":"2025-05-01T19:39:42Z","timestamp":1746128382000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-04921-2_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319049205","9783319049212"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-04921-2_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}