{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:39:56Z","timestamp":1725565196062},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642152931"},{"type":"electronic","value":"9783642152948"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15294-8_6","type":"book-chapter","created":{"date-parts":[[2010,9,10]],"date-time":"2010-09-10T08:51:46Z","timestamp":1284108706000},"page":"65-77","source":"Crossref","is-referenced-by-count":4,"title":["Reducing the Worst Case Running Times of a Family of RNA and CFG Problems, Using Valiant\u2019s Approach"],"prefix":"10.1007","author":[{"given":"Shay","family":"Zakov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dekel","family":"Tsur","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michal","family":"Ziv-Ukelson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"6_CR1","first-page":"1","volume":"308","author":"A.F.B. Consortium","year":"2007","unstructured":"Consortium, A.F.B., Backofen, R., Bernhart, S.H., Flamm, C., Fried, C., Fritzsch, G., Hackermuller, J., Hertel, J., Hofacker, I.L., Missal, K., Mosig, A., Prohaska, S.J., Rose, D., Stadler, P.F., Tanzer, A., Washietl, S., Will, S.: RNAs everywhere: genome-wide annotation of structured RNAs. J. Exp. Zoolog. B. Mol. Dev. Evol.\u00a0308, 1\u201325 (2007)","journal-title":"J. Exp. Zoolog. B. Mol. Dev. Evol."},{"key":"6_CR2","doi-asserted-by":"publisher","first-page":"6309","DOI":"10.1073\/pnas.77.11.6309","volume":"77","author":"R. Nussinov","year":"1980","unstructured":"Nussinov, R., Jacobson, A.B.: Fast algorithm for predicting the secondary structure of single-stranded RNA. PNAS\u00a077, 6309\u20136313 (1980)","journal-title":"PNAS"},{"key":"6_CR3","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":"6_CR4","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1089\/cmb.2006.13.267","volume":"13","author":"C. Alkan","year":"2006","unstructured":"Alkan, C., Karako\u00e7, E., Nadeau, J.H., Sahinalp, S.C., Zhang, K.: RNA-RNA interaction prediction and antisense RNA target search. Journal of Computational Biology\u00a013, 267\u2013282 (2006)","journal-title":"Journal of Computational Biology"},{"key":"6_CR5","doi-asserted-by":"publisher","first-page":"1105","DOI":"10.1002\/bip.360290621","volume":"29","author":"J.S. McCaskill","year":"1990","unstructured":"McCaskill, J.S.: The equilibrium partition function and base pair binding probabilities for RNA secondary structure. Biopolymers\u00a029, 1105\u20131119 (1990)","journal-title":"Biopolymers"},{"key":"6_CR6","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1186\/1748-7188-1-3","volume":"1","author":"S. Bernhart","year":"2006","unstructured":"Bernhart, S., Tafer, H., M\u00fcckstein, U., Flamm, C., Stadler, P., Hofacker, I.: Partition function and base pairing probabilities of RNA heterodimers. Algorithms for Molecular Biology\u00a01, 3 (2006)","journal-title":"Algorithms for Molecular Biology"},{"key":"6_CR7","doi-asserted-by":"crossref","unstructured":"Chitsaz, H., Salari, R., Sahinalp, S.C., Backofen, R.: A partition function algorithm for interacting nucleic acid strands. Bioinformatics\u00a025, i365\u2013i373 (2009)","DOI":"10.1093\/bioinformatics\/btp212"},{"key":"6_CR8","first-page":"126","volume-title":"INTSYS 1998: Proceedings of the IEEE International Joint Symposia on Intelligence and Systems","author":"K. Zhang","year":"1998","unstructured":"Zhang, K.: Computing similarity between RNA secondary structures. In: INTSYS 1998: Proceedings of the IEEE International Joint Symposia on Intelligence and Systems, p. 126. IEEE Computer Society, Washington (1998)"},{"key":"6_CR9","doi-asserted-by":"publisher","first-page":"810","DOI":"10.1137\/0145048","volume":"45","author":"D. Sankoff","year":"1985","unstructured":"Sankoff, D.: Simultaneous solution of the RNA folding, alignment and protosequence problems. SIAM Journal on Applied Mathematics\u00a045, 810\u2013825 (1985)","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"6_CR10","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., Sjolander, K., Underwood, R., Haussler, D.: Stochastic context-free grammers for tRNA modeling. Nucleic Acids Research\u00a022, 5112 (1994)","journal-title":"Nucleic Acids Research"},{"key":"6_CR11","first-page":"196","volume-title":"STOC","author":"R. Teitelbaum","year":"1973","unstructured":"Teitelbaum, R.: Context-free error analysis by evaluation of algebraic power series. In: STOC, pp. 196\u2013199. ACM, New York (1973)"},{"key":"6_CR12","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1186\/1471-2105-5-71","volume":"5","author":"R. Dowell","year":"2004","unstructured":"Dowell, R., Eddy, S.: Evaluation of several lightweight stochastic context-free grammars for RNA secondary structure prediction. BMC bioinformatics\u00a05, 71 (2004)","journal-title":"BMC bioinformatics"},{"key":"6_CR13","doi-asserted-by":"crossref","unstructured":"Do, C.B., Woods, D.A., Batzoglou, S.: CONTRAfold: RNA secondary structure prediction without physics-based models. Bioinformatics\u00a022, e90\u2013e98 (2006)","DOI":"10.1093\/bioinformatics\/btl246"},{"key":"6_CR14","volume-title":"Programming Languages and Their Compilers","author":"J. Cocke","year":"1970","unstructured":"Cocke, J., Schwartz, J.T.: Programming Languages and Their Compilers. Courant Institute of Mathematical Sciences, New York (1970)"},{"key":"6_CR15","unstructured":"Kasami, T.: An efficient recognition and syntax analysis algorithm for context-free languages. Technical Report AFCRL-65-758, Air Force Cambridge Res. Lab., Bedford Mass. (1965)"},{"key":"6_CR16","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0019-9958(67)80007-X","volume":"10","author":"D.H. Younger","year":"1967","unstructured":"Younger, D.H.: Recognition and parsing of context-free languages in time n 3. Information and Control\u00a010, 189\u2013208 (1967)","journal-title":"Information and Control"},{"key":"6_CR17","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/S0022-0000(75)80046-8","volume":"10","author":"L. Valiant","year":"1975","unstructured":"Valiant, L.: General context-free recognition in less than cubic time. Journal of Computer and System Sciences\u00a010, 308\u2013315 (1975)","journal-title":"Journal of Computer and System Sciences"},{"key":"6_CR18","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 progressions. J. Symb. Comput.\u00a09, 251\u2013280 (1990)","journal-title":"J. Symb. Comput."},{"key":"6_CR19","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1023\/A:1009898029639","volume":"3","author":"T. Akutsu","year":"1999","unstructured":"Akutsu, T.: Approximation and exact algorithms for RNA secondary structure prediction and recognition of stochastic context-free languages. Journal of Combinatorial Optimization\u00a03, 321\u2013336 (1999)","journal-title":"Journal of Combinatorial Optimization"},{"key":"6_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1007\/978-3-540-72847-4_12","volume-title":"Pattern Recognition and Image Analysis","author":"J. Bened\u00ed","year":"2007","unstructured":"Bened\u00ed, J., S\u00e1nchez, J.: Fast Stochastic Context-Free Parsing: A Stochastic Version of the Valiant Algorithm. In: Mart\u00ed, J., Bened\u00ed, J.M., Mendon\u00e7a, A.M., Serrat, J. (eds.) IbPRIA 2007. LNCS, vol.\u00a04477, pp. 80\u201388. Springer, Heidelberg (2007)"},{"key":"6_CR21","doi-asserted-by":"publisher","first-page":"590","DOI":"10.1145\/1250790.1250877","volume-title":"STOC 2007: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing","author":"T.M. Chan","year":"2007","unstructured":"Chan, T.M.: More algorithms for all-pairs shortest paths in weighted graphs. In: STOC 2007: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pp. 590\u2013598. ACM, New York (2007)"},{"key":"6_CR22","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1145\/357103.357112","volume":"2","author":"S.L. Graham","year":"1980","unstructured":"Graham, S.L., Harrison, M.A., Ruzzo, W.L.: An improved context-free recognizer. ACM Transactions on Programming Languages and Systems\u00a02, 415\u2013462 (1980)","journal-title":"ACM Transactions on Programming Languages and Systems"},{"key":"6_CR23","first-page":"1209","volume":"11","author":"V.L. Arlazarov","year":"1970","unstructured":"Arlazarov, V.L., Dinic, E.A., Kronod, M.A., Faradzev, I.A.: On economical construction of the transitive closure of an oriented graph. Soviet. Math. Dokl.\u00a011, 1209\u20131210 (1970)","journal-title":"Soviet. Math. Dokl."},{"key":"6_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/978-3-642-04241-6_9","volume-title":"WABI 2009","author":"Y. Frid","year":"2009","unstructured":"Frid, Y., Gusfield, D.: A simple, practical and complete O $(\\frac{n^3}{ \\log n})$ -time algorithm for RNA folding using the four-russians speedup. In: Salzberg, S.L., Warnow, T. (eds.) WABI 2009. LNCS, vol.\u00a05724, pp. 97\u2013107. Springer, Heidelberg (2009)"},{"key":"6_CR25","doi-asserted-by":"crossref","unstructured":"Klein, D., Manning, C.D.: A* parsing: Fast exact viterbi parse selection. In: HLT-NAACL, pp. 119\u2013126 (2003)","DOI":"10.3115\/1073445.1073461"},{"key":"6_CR26","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/s00453-006-1207-0","volume":"46","author":"J. Jansson","year":"2006","unstructured":"Jansson, J., Ng, S., Sung, W., Willy, H.: A faster and more space-efficient algorithm for inferring arc-annotations of RNA sequences through alignment. Algorithmica\u00a046, 223\u2013245 (2006)","journal-title":"Algorithmica"},{"key":"6_CR27","doi-asserted-by":"publisher","first-page":"856","DOI":"10.1089\/cmb.2007.R020","volume":"14","author":"Y. Wexler","year":"2007","unstructured":"Wexler, Y., Zilberstein, C.B.Z., Ziv-Ukelson, M.: A study of accessible motifs and RNA folding complexity. Journal of Computational Biology\u00a014, 856\u2013872 (2007)","journal-title":"Journal of Computational Biology"},{"key":"6_CR28","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1007\/978-3-540-87361-7_15","volume-title":"Algorithms in Bioinformatics","author":"M. Ziv-Ukelson","year":"2008","unstructured":"Ziv-Ukelson, M., Gat-Viks, I., Wexler, Y., Shamir, R.: A faster algorithm for RNA co-folding. In: Crandall, K.A., Lagergren, J. (eds.) WABI 2008. LNCS (LNBI), vol.\u00a05251, pp. 174\u2013185. Springer, Heidelberg (2008)"},{"key":"6_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/978-3-642-02441-2_22","volume-title":"Combinatorial Pattern Matching","author":"R. Backofen","year":"2009","unstructured":"Backofen, R., Tsur, D., Zakov, S., Ziv-Ukelson, M.: Sparse RNA folding: Time and space efficient algorithms. In: Kucherov, G., Ukkonen, E. (eds.) CPM 2009. LNCS, vol.\u00a05577, pp. 249\u2013262. Springer, Heidelberg (2009)"},{"key":"6_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1007\/978-3-642-12683-3_31","volume-title":"RECOMB 2010","author":"R. Salari","year":"2010","unstructured":"Salari, R., Mohl, M., Will, S., Sahinalp, S., Backofen, R.: Time and Space Efficient RNA-RNA Interaction Prediction via Sparse Folding. In: Berger, B. (ed.) RECOMB 2010. LNCS, vol.\u00a06044, pp. 473\u2013490. Springer, Heidelberg (2010)"},{"key":"6_CR31","doi-asserted-by":"publisher","first-page":"1815","DOI":"10.1093\/bioinformatics\/bti279","volume":"21","author":"J. Havgaard","year":"2005","unstructured":"Havgaard, J., Lyngso, R., Stormo, G., Gorodkin, J.: Pairwise local structural alignment of RNA sequences with sequence similarity less than 40%. Bioinformatics\u00a021, 1815\u20131824 (2005)","journal-title":"Bioinformatics"},{"key":"6_CR32","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1371\/journal.pcbi.0030065","volume":"3","author":"S. Will","year":"2007","unstructured":"Will, S., Reiche, K., Hofacker, I.L., Stadler, P.F., Backofen, R.: Inferring non-coding RNA families and classes by means of genome-scale structure-based clustering. PLOS Computational Biology\u00a03, 65 (2007)","journal-title":"PLOS Computational Biology"},{"key":"6_CR33","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1121\/1.2017061","volume":"65","author":"J.K. Baker","year":"1979","unstructured":"Baker, J.K.: Trainable grammars for speech recognition. The Journal of the Acoustical Society of America\u00a065, S132 (1979)","journal-title":"The Journal of the Acoustical Society of America"},{"key":"6_CR34","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1356052.1356053","volume":"34","author":"K. Goto","year":"2008","unstructured":"Goto, K., Geijn, R.: Anatomy of high-performance matrix multiplication. ACM Transactions on Mathematical Software (TOMS)\u00a034, 1\u201325 (2008)","journal-title":"ACM Transactions on Mathematical Software (TOMS)"},{"key":"6_CR35","unstructured":"Robinson, S.: Toward an optimal algorithm for matrix multiplication. News Journal of the Society for Industrial and Applied Mathematics\u00a038 (2005)"}],"container-title":["Lecture Notes in Computer Science","Algorithms in Bioinformatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15294-8_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,4]],"date-time":"2019-06-04T10:56:26Z","timestamp":1559645786000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15294-8_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642152931","9783642152948"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15294-8_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}