{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,30]],"date-time":"2024-03-30T14:10:19Z","timestamp":1711807819652},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2010,9,16]],"date-time":"2010-09-16T00:00:00Z","timestamp":1284595200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2012,2]]},"DOI":"10.1007\/s00453-010-9451-8","type":"journal-article","created":{"date-parts":[[2010,9,15]],"date-time":"2010-09-15T15:10:06Z","timestamp":1284563406000},"page":"209-223","source":"Crossref","is-referenced-by-count":0,"title":["Fast Arc-Annotated Subsequence Matching in Linear Space"],"prefix":"10.1007","volume":"62","author":[{"given":"Philip","family":"Bille","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Inge Li","family":"G\u00f8rtz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,9,16]]},"reference":[{"issue":"2\u20133","key":"9451_CR1","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/j.tcs.2003.10.026","volume":"312","author":"J. Alber","year":"2004","unstructured":"Alber, J., Gramm, J., Guo, J., Niedermeier, R.: Computing the similarity of two sequences with nested arc annotations. Theor. Comput. Sci. 312(2\u20133), 337\u2013358 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"9451_CR2","doi-asserted-by":"crossref","unstructured":"Backofen, R., Bernhart, S.H.H., Flamm, C., Fried, C., Fritzsch, G., Hackerm\u00fcller, J., Hertel, J., Hofacker, I.L.L., Missal, K., Mosig, A., Prohaska, S.J.J., Rose, D., Stadler, P.F.F., Tanzer, A., Washietl, S., Will, S.: RNAs everywhere: genome-wide annotation of structured rnas. J. Exp. Zool., Part B Mol. Dev. Evol., 1\u201325 (2007)","DOI":"10.1002\/jez.b.21130"},{"key":"9451_CR3","doi-asserted-by":"crossref","unstructured":"Backofen, R., Landau, G.M., M\u00f6hl, M., Tsur, D., Weimann, O.: Fast RNA structure alignment for crossing input structures. In: Proc. 20th CPM (2009)","DOI":"10.1007\/978-3-642-02441-2_21"},{"key":"9451_CR4","series-title":"LNCS","first-page":"1","volume-title":"Proc. 6th CPM","author":"V. Bafna","year":"1995","unstructured":"Bafna, V., Muthukrishnan, S., Ravi, R.: Computing similarity between RNA strings. In: Proc. 6th CPM. LNCS, vol. 937, pp. 1\u201316. Springer, Berlin (1995)"},{"key":"9451_CR5","series-title":"LNCS","first-page":"66","volume-title":"Proc. 32nd ICALP","author":"P. Bille","year":"2005","unstructured":"Bille, P., G\u00f8rtz, I.L.: The tree inclusion problem: optimal space and faster. In: Proc. 32nd ICALP. LNCS, vol. 3580, pp. 66\u201377. Springer, Berlin (2005)"},{"key":"9451_CR6","series-title":"LNCS","first-page":"291","volume-title":"Proc. 13th SPIRE","author":"G. Blin","year":"2006","unstructured":"Blin, G., Touzet, H.: How to compare arc-annotated sequences: The alignment hierarchy. In: Proc. 13th SPIRE. LNCS, pp. 291\u2013303. Springer, Berlin (2006)"},{"key":"9451_CR7","doi-asserted-by":"crossref","unstructured":"Blin, G., Fertin, G., Rizzi, R., Vialette, S.: What makes the Arc-Preserving Subsequence Problem hard? In: Trans. Comput. Sys. Bio. II, pp. 1\u201336 (2005). Announced at ICCS 2005","DOI":"10.1007\/11567752_1"},{"key":"9451_CR8","series-title":"Natural Computing Series","volume-title":"Algorithmic Aspects of Bioinformatics","author":"H.-J. B\u00f6ckenhauer","year":"2007","unstructured":"B\u00f6ckenhauer, H.-J., Bongartz, D.: Algorithmic Aspects of Bioinformatics. Natural Computing Series. Springer, New York (2007)"},{"key":"9451_CR9","doi-asserted-by":"crossref","first-page":"370","DOI":"10.1006\/jagm.1997.0899","volume":"26","author":"W. Chen","year":"1998","unstructured":"Chen, W.: More efficient algorithm for ordered tree inclusion. J. Algorithms 26, 370\u2013385 (1998)","journal-title":"J. Algorithms"},{"issue":"2","key":"9451_CR10","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1016\/j.ipl.2006.05.008","volume":"100","author":"P. Damaschke","year":"2006","unstructured":"Damaschke, P.: A remark on the subsequence problem for arc-annotated sequences with pairwise nested arcs. Inf. Process. Lett. 100(2), 64\u201368 (2006)","journal-title":"Inf. Process. Lett."},{"key":"9451_CR11","unstructured":"Evans, P.: Algorithms and complexity for annotated sequence analysis. PhD thesis, University of Victoria (1999)"},{"issue":"4","key":"9451_CR12","doi-asserted-by":"crossref","first-page":"1070","DOI":"10.1093\/nar\/27.4.1070","volume":"27","author":"A. Farris","year":"1999","unstructured":"Farris, A., Koelsch, G., Pruijn, G., van Venrooij, W., Harley, J.: Conserved features of Y RNAs revealed by automated phylogenetic secondary structure analysis. Nucl. Acids Res. 27(4), 1070\u20131078 (1999)","journal-title":"Nucl. Acids Res."},{"issue":"1","key":"9451_CR13","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1145\/1125994.1125997","volume":"2","author":"J. Gramm","year":"2006","unstructured":"Gramm, J., Guo, J., Niedermeier, R.: Pattern matching for arc-annotated sequences. ACM Trans. Algorithms 2(1), 44\u201365 (2006). Announced at FSTTCS 2002","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"9451_CR14","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D. Harel","year":"1984","unstructured":"Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM J. Comput. 13(2), 338\u2013355 (1984)","journal-title":"SIAM J. Comput."},{"issue":"24","key":"9451_CR15","doi-asserted-by":"crossref","first-page":"4910","DOI":"10.1093\/nar\/24.24.4910","volume":"24","author":"K. Hellendoorn","year":"1996","unstructured":"Hellendoorn, K., Michiels, P., Buitenhuis, R., Pleij, C.: Protonatable hairpins are conserved in the 5\u2032-untranslated region of tymovirus RNAs. Nucl. Acids Res. 24(24), 4910\u20134917 (1996)","journal-title":"Nucl. Acids Res."},{"issue":"5","key":"9451_CR16","doi-asserted-by":"crossref","first-page":"1221","DOI":"10.1093\/nar\/28.5.1221","volume":"28","author":"V. Juan","year":"2000","unstructured":"Juan, V., Crain, C., Wilson, C.: Evidence for evolutionarily conserved secondary structure in the H19 tumor suppressor RNA. Nucl. Acids Res. 28(5), 1221\u20131227 (2000)","journal-title":"Nucl. Acids Res."},{"key":"9451_CR17","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/11605126_2","volume-title":"Federation over the Web","author":"T. Kida","year":"2006","unstructured":"Kida, T.: Faster pattern matching algorithm for arc-annotated sequences. In: Federation over the Web. LNCS, vol. 3847, pp. 25\u201339. Springer, Berlin (2006)"},{"key":"9451_CR18","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1137\/S0097539791218202","volume":"24","author":"P. Kilpel\u00e4inen","year":"1995","unstructured":"Kilpel\u00e4inen, P., Mannila, H.: Ordered and unordered tree inclusion. SIAM J. Comput. 24, 340\u2013356 (1995)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9451_CR19","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1016\/S0022-0000(02)00004-1","volume":"65","author":"G. Lin","year":"2002","unstructured":"Lin, G., Chen, Z.-Z., Jiang, T., Wen, J.: The longest common subsequence problem for sequences with nested arc annotations. J. Comput. Syst. Sci. 65(3), 465\u2013480 (2002)","journal-title":"J. Comput. Syst. Sci."},{"key":"9451_CR20","series-title":"LNCS","first-page":"37","volume-title":"Proc. 16th FSTTCS","author":"I. Munro","year":"1996","unstructured":"Munro, I.: Tables. In: Proc. 16th FSTTCS. LNCS, vol. 1180, pp. 37\u201342. Springer, Berlin (1996)"},{"issue":"2","key":"9451_CR21","doi-asserted-by":"crossref","first-page":"610","DOI":"10.1093\/nar\/28.2.610","volume":"28","author":"S.W.M. Teunissen","year":"2000","unstructured":"Teunissen, S.W.M., Kruithof, M.J.M., Farris, A.D., Harley, J.B., v. Venrooij, W.J., Pruijn, G.J.M.: Conserved features of Y RNAs: a comparison of experimentally derived secondary structures. Nucl. Acids Res. 28(2), 610\u2013619 (2000)","journal-title":"Nucl. Acids Res."},{"issue":"2\u20133","key":"9451_CR22","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/j.tcs.2003.08.010","volume":"312","author":"S. Vialette","year":"2004","unstructured":"Vialette, S.: On the computational complexity of 2-interval pattern matching problems. Theor. Comput. Sci. 312(2\u20133), 223\u2013249 (2004). Announced at CPM 2002","journal-title":"Theor. Comput. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9451-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-010-9451-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9451-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,30]],"date-time":"2024-03-30T13:50:30Z","timestamp":1711806630000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9451-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,9,16]]},"references-count":22,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2012,2]]}},"alternative-id":["9451"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9451-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,9,16]]}}}