{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T00:11:03Z","timestamp":1773274263521,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540228493","type":"print"},{"value":"9783540278368","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27836-8_77","type":"book-chapter","created":{"date-parts":[[2010,9,15]],"date-time":"2010-09-15T18:53:21Z","timestamp":1284576801000},"page":"919-931","source":"Crossref","is-referenced-by-count":36,"title":["Complexity of Pseudoknot Prediction in Simple Models"],"prefix":"10.1007","author":[{"given":"Rune B.","family":"Lyngs\u00f8","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"77_CR1","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1038\/418214a","volume":"418","author":"G.F. Joyce","year":"2002","unstructured":"Joyce, G.F.: The antiquity of RNA-based evolution. Nature\u00a0418, 214\u2013221 (2002)","journal-title":"Nature"},{"key":"77_CR2","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 Research\u00a09, 133\u2013148 (1981)","journal-title":"Nucleic Acids Research"},{"key":"77_CR3","doi-asserted-by":"publisher","first-page":"1602","DOI":"10.1093\/nar\/29.7.1602","volume":"29","author":"B. Felden","year":"2001","unstructured":"Felden, B., Massire, C., Westhof, E., Atkins, J.F., Gesteland, R.F.: Phylogenetic analysis of tmRNA genes within a bacterial subgroup reveals a specific structural signature. Nucleic Acids Research\u00a029, 1602\u20131607 (2001)","journal-title":"Nucleic Acids Research"},{"key":"77_CR4","doi-asserted-by":"publisher","first-page":"766","DOI":"10.1093\/nar\/30.3.766","volume":"30","author":"Y. Tanaka","year":"2002","unstructured":"Tanaka, Y., Hori, T., Tagaya, M., Sakamoto, T., Kurihara, Y., Katahira, M., Uesugi, S.: Imino proton NMR analysis of HDV ribozymes: nested double pseudoknot structure and Mg2\u2009+\u2009 ion-binding site close to the catalytic core in solution. Nucleic Acids Research\u00a030, 766\u2013774 (2002)","journal-title":"Nucleic Acids Research"},{"key":"77_CR5","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1093\/bioinformatics\/14.8.691","volume":"14","author":"J.E. Tabaska","year":"1998","unstructured":"Tabaska, J.E., Cary, R.B., Gabow, H.N., Stormo, G.D.: An RNA folding method capable of identifying pseudoknots and base triples. Bioinformatics\u00a014, 691\u2013699 (1998)","journal-title":"Bioinformatics"},{"key":"77_CR6","doi-asserted-by":"publisher","first-page":"2053","DOI":"10.1006\/jmbi.1998.2436","volume":"285","author":"E. Rivas","year":"1999","unstructured":"Rivas, E., Eddy, S.: Adynamic programming algorithm for RNA structure prediction including pseudoknots. Journal of Molecular Biology\u00a0285, 2053\u20132068 (1999)","journal-title":"Journal of Molecular Biology"},{"key":"77_CR7","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/S0166-218X(00)00186-4","volume":"104","author":"T. Akutsu","year":"2000","unstructured":"Akutsu, T.: Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots. Discrete Applied Mathematics\u00a0104, 45\u201362 (2000)","journal-title":"Discrete Applied Mathematics"},{"key":"77_CR8","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"},{"key":"77_CR9","unstructured":"Reeder, J., Giegerich, R.: From RNA folding to thermodynamic matching, including pseudoknots. Technical Report 03, Technische Fakult\u00e4t, Universit\u00e4t Bielefeld (2003)"},{"key":"77_CR10","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1089\/106652700750050862","volume":"7","author":"R.B. Lyngs\u00f8","year":"2000","unstructured":"Lyngs\u00f8, R.B., Pedersen, C.N.S.: RNA pseudoknot prediction in energy based models. Journal of Computational Biology\u00a07, 409\u2013428 (2000)","journal-title":"Journal of Computational Biology"},{"key":"77_CR11","doi-asserted-by":"crossref","unstructured":"Ieong, S., Kao, M.Y., Lam, T.W., Sung, W.K., Yiu, S.M.: Predicting RNA secondary structures with arbitrary pseudoknots by maximizing the number of stacking pairs. In: Proceedings of the 2nd Symposium on Bioinformatics and Bioengineering, pp. 183\u2013190 (2001)","DOI":"10.1109\/BIBE.2001.974428"},{"key":"77_CR12","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1006\/jmbi.1994.1493","volume":"241","author":"T.C. Gluick","year":"1994","unstructured":"Gluick, T.C., Draper, D.E.: Thermodynamics of folding a pseudoknotted mRNA fragment. Journal of Molecular Biology\u00a0241, 246\u2013262 (1994)","journal-title":"Journal of Molecular Biology"},{"key":"77_CR13","doi-asserted-by":"publisher","first-page":"911","DOI":"10.1006\/jmbi.1999.2700","volume":"288","author":"D.H. Mathews","year":"1999","unstructured":"Mathews, D.H., Sabina, J., Zuker, M., Turner, D.H.: Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structure. Journal of Molecular Biology\u00a0288, 911\u2013940 (1999)","journal-title":"Journal of Molecular Biology"},{"key":"77_CR14","volume-title":"Computational Complexity","author":"C.M. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.M.: Computational Complexity. Addison-Wesley Publishing Company, Inc., Reading (1994)"},{"key":"77_CR15","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1145\/360825.360861","volume":"18","author":"D.S. Hirschberg","year":"1975","unstructured":"Hirschberg, D.S.: A linear space algorithm for computing maximal common subsequence. Communications of the ACM\u00a018, 341\u2013343 (1975)","journal-title":"Communications of the ACM"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27836-8_77.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,2]],"date-time":"2021-05-02T23:31:06Z","timestamp":1619998266000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27836-8_77"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540228493","9783540278368"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27836-8_77","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004]]}}}