{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:00:21Z","timestamp":1725559221841},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540260431"},{"type":"electronic","value":"9783540321149"}],"license":[{"start":{"date-parts":[[2005,1,1]],"date-time":"2005-01-01T00:00:00Z","timestamp":1104537600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11428848_110","type":"book-chapter","created":{"date-parts":[[2010,7,14]],"date-time":"2010-07-14T13:44:33Z","timestamp":1279115073000},"page":"860-868","source":"Crossref","is-referenced-by-count":4,"title":["What Makes the Arc-Preserving Subsequence Problem Hard?"],"prefix":"10.1007","author":[{"given":"Guillaume","family":"Blin","sequence":"first","affiliation":[]},{"given":"Guillaume","family":"Fertin","sequence":"additional","affiliation":[]},{"given":"Romeo","family":"Rizzi","sequence":"additional","affiliation":[]},{"given":"St\u00e9phane","family":"Vialette","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2-3","key":"110_CR1","doi-asserted-by":"publisher","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. Theoretical Computer Science\u00a0312(2-3), 337\u2013358 (2004)","journal-title":"Theoretical Computer Science"},{"key":"110_CR2","doi-asserted-by":"publisher","first-page":"2575","DOI":"10.1093\/nar\/30.11.2575","volume":"30","author":"G. Caetano-Anoll\u00e9s","year":"2002","unstructured":"Caetano-Anoll\u00e9s, G.: Tracing the evolution of RNA structure in ribosomes. Nucl. Acids. Res.\u00a030, 2575\u20132587 (2002)","journal-title":"Nucl. Acids. Res."},{"key":"110_CR3","unstructured":"Evans, P.: Algorithms and Complexity for Annotated Sequence Analysis. PhD thesis, U. Victoria (1999)"},{"volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","year":"1979","author":"M. Garey","key":"110_CR4","unstructured":"Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York (1979)"},{"key":"110_CR5","unstructured":"Goldman, D., Istrail, S., Papadimitriou, C.H.: Algorithmic aspects of protein structure similarity. In: Proc. of the 40th Symposium of Foundations of Computer Science (FOCS 1999), pp. 512\u2013522 (1999)"},{"key":"110_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1007\/3-540-36206-1_17","volume-title":"FST TCS 2002: Foundations of Software Technology and Theoretical Computer Science","author":"J. Gramm","year":"2002","unstructured":"Gramm, J., Guo, J., Niedermeier, R.: Pattern matching for arc-annotated sequences. In: Agrawal, M., Seth, A.K. (eds.) FSTTCS 2002. LNCS, vol.\u00a02556, pp. 182\u2013193. Springer, Heidelberg (2002)"},{"key":"110_CR7","unstructured":"Guo, J.: Exact algorithms for the longest common subsequence problem for arc-annotated sequences. Master\u2019s Thesis, Universitat Tubingen, Fed. Rep. of Germany (2002)"},{"key":"110_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1007\/3-540-45123-4_15","volume-title":"Combinatorial Pattern Matching","author":"T. Jiang","year":"2000","unstructured":"Jiang, T., Lin, G.-H., Ma, B., Zhang, K.: The longest common subsequence problem for arc-annotated sequences. In: Giancarlo, R., Sankoff, D. (eds.) CPM 2000. LNCS, vol.\u00a01848, pp. 154\u2013165. Springer, Heidelberg (2000)"},{"key":"110_CR9","doi-asserted-by":"publisher","first-page":"1221","DOI":"10.1093\/nar\/28.5.1221","volume":"28","author":"V. Juan","year":"2000","unstructured":"Juan, V., Crain, C., Wilson, S.: Evidence for evolutionarily conserved secondary structure in the H19 tumor suppressor RNA. Nucl. Acids. Res.\u00a028, 1221\u20131227 (2000)","journal-title":"Nucl. Acids. Res."},{"key":"110_CR10","doi-asserted-by":"crossref","unstructured":"Lancia, G., Carr, R., Walenz, B., Istrail, S.: 101 optimal PDB structure alignments: a branch-and-cut algorithm for the maximum contact map overlap problem. In: Proceedings of the 5th ACM International Conference on Computational Molecular Biology (RECOMB 2001), pp. 193\u2013202 (2001)","DOI":"10.1145\/369133.369199"},{"issue":"2-3","key":"110_CR11","doi-asserted-by":"publisher","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. Theoretical Computer Science\u00a0312(2-3), 223\u2013249 (2004)","journal-title":"Theoretical Computer Science"},{"key":"110_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/3-540-48452-3_21","volume-title":"Combinatorial Pattern Matching","author":"K. Zhang","year":"1999","unstructured":"Zhang, K., Wang, L., Ma, B.: Computing the similarity between RNA structures. In: Crochemore, M., Paterson, M. (eds.) CPM 1999. LNCS, vol.\u00a01645, pp. 281\u2013293. Springer, Heidelberg (1999)"},{"key":"110_CR13","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1016\/0076-6879(89)80106-5","volume":"180","author":"M. Zuker","year":"1989","unstructured":"Zuker, M.: RNA folding. Meth. Enzymology\u00a0180, 262\u2013288 (1989)","journal-title":"Meth. Enzymology"}],"container-title":["Lecture Notes in Computer Science","Computational Science \u2013 ICCS 2005"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11428848_110","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T16:15:35Z","timestamp":1558282535000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11428848_110"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540260431","9783540321149"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/11428848_110","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}
