{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,5]],"date-time":"2025-01-05T09:40:26Z","timestamp":1736070026145,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540294016"},{"type":"electronic","value":"9783540316619"}],"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\/11567752_1","type":"book-chapter","created":{"date-parts":[[2005,11,3]],"date-time":"2005-11-03T06:56:50Z","timestamp":1131001010000},"page":"1-36","source":"Crossref","is-referenced-by-count":7,"title":["What Makes the Arc-Preserving Subsequence Problem Hard?"],"prefix":"10.1007","author":[{"given":"Guillaume","family":"Blin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guillaume","family":"Fertin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Romeo","family":"Rizzi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"St\u00e9phane","family":"Vialette","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"1_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/3-540-45452-7_10","volume-title":"Combinatorial Pattern Matching","author":"J. Alber","year":"2002","unstructured":"Alber, J., Gramm, J., Guo, J., Niedermeier, R.: Towards optimally solving the longest common subsequence problem for sequences with nested arc annotations in linear time. In: Apostolico, A., Takeda, M. (eds.) CPM 2002. LNCS, vol.\u00a02373, pp. 99\u2013114. Springer, Heidelberg (2002)"},{"issue":"2-3","key":"1_CR2","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":"1_CR3","first-page":"138","volume":"19","author":"B. Billoud","year":"2000","unstructured":"Billoud, B., Guerrucci, M.-A., Masselot, M., Deutsch, J.S.: Cirripede phylogeny using a novel approach: Molecular morphometrics. Molecular Biology and Evolution\u00a019, 138\u2013148 (2000)","journal-title":"Molecular Biology and Evolution"},{"key":"1_CR4","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-Anolls, G.: Tracing the evolution of RNA structure in ribosomes. Nucl. Acids. Res.\u00a030, 2575\u20132587 (2002)","journal-title":"Nucl. Acids. Res."},{"key":"1_CR5","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1006\/jmbi.1999.3084","volume":"292","author":"W. Chaia","year":"1999","unstructured":"Chaia, W., Stewart, V.: RNA Sequence Requirements for NasR-mediated, Nitrate-responsive Transcription Antitermination of the Klebsiella oxytoca M5al nasF Operon Leader. Journal of Molecular Biology\u00a0292, 203\u2013216 (1999)","journal-title":"Journal of Molecular Biology"},{"key":"1_CR6","unstructured":"Evans, P.: Algorithms and Complexity for Annotated Sequence Analysis. PhD thesis, U. Victoria (1999)"},{"key":"1_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1007\/3-540-48452-3_20","volume-title":"Combinatorial Pattern Matching","author":"P. Evans","year":"1999","unstructured":"Evans, P.: Finding common subsequences with arcs and pseudoknots. In: Crochemore, M., Paterson, M. (eds.) CPM 1999. LNCS, vol.\u00a01645, pp. 270\u2013280. Springer, Heidelberg (1999)"},{"key":"1_CR8","doi-asserted-by":"publisher","first-page":"1070","DOI":"10.1093\/nar\/27.4.1070","volume":"27","author":"A.D. Farris","year":"1999","unstructured":"Farris, A.D., Koelsch, G., Pruijn, G.J., van Venrooij, W.J., Harley, J.B.: Conserved features of Y RNAs revealed by automated phylogenetic secondary structure analysis. Nucl. Acids. Res.\u00a027, 1070\u20131078 (1999)","journal-title":"Nucl. Acids. Res."},{"key":"1_CR9","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness.","author":"M. Garey","year":"1979","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":"1_CR10","doi-asserted-by":"crossref","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)","DOI":"10.1109\/SFFCS.1999.814624"},{"key":"1_CR11","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":"1_CR12","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":"1_CR13","doi-asserted-by":"publisher","first-page":"4910","DOI":"10.1093\/nar\/24.24.4910","volume":"24","author":"K. Hellendoorn","year":"1996","unstructured":"Hellendoorn, K., Michiels, P.J., Buitenhuis, R., Pleij, C.W.: Protonatable hairpins are conserved in the 5\u2019-untranslated region of tymovirus RNAs. Nucl. Acids. Res.\u00a024, 4910\u20134917 (1996)","journal-title":"Nucl. Acids. Res."},{"key":"1_CR14","doi-asserted-by":"publisher","first-page":"3825","DOI":"10.1093\/nar\/26.16.3825","volume":"26","author":"L. Hofacker","year":"1998","unstructured":"Hofacker, L., Fekete, M., Flamm, C., Huynen, M.A., Rauscher, S., Stolorz, P.E., Stadler, P.F.: Automatic detection of conserved RNA structure elements in complete RNA virus genomes. Nucl. Acids. Res.\u00a026, 3825\u20133836 (1998)","journal-title":"Nucl. Acids. Res."},{"key":"1_CR15","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":"1_CR16","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":"1_CR17","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"},{"key":"1_CR18","doi-asserted-by":"publisher","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., van Venrooij, W.J., Pruijn, G.J.M.: Conserved features of Y RNAs: a comparison of experimentally derived secondary structures. Nucl. Acids. Res.\u00a028, 610\u2013619 (2000)","journal-title":"Nucl. Acids. Res."},{"key":"1_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/3-540-45452-7_6","volume-title":"Combinatorial Pattern Matching","author":"S. Vialette","year":"2002","unstructured":"Vialette, S.: Pattern matching over 2-intervals sets. In: Apostolico, A., Takeda, M. (eds.) CPM 2002. LNCS, vol.\u00a02373, pp. 53\u201363. Springer, Heidelberg (2002)"},{"issue":"2-3","key":"1_CR20","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":"1_CR21","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1093\/oxfordjournals.molbev.a004066","volume":"19","author":"H.-Y. Wang","year":"2002","unstructured":"Wang, H.-Y., Lee, S.-C.: Secondary structure of mitochondrial 12S rRNA among fish and its phylogenetic applications. Molecular Biology and Evolution\u00a019, 138\u2013148 (2002)","journal-title":"Molecular Biology and Evolution"},{"key":"1_CR22","doi-asserted-by":"publisher","first-page":"4698","DOI":"10.1093\/nar\/28.23.4698","volume":"28","author":"J. Wuyts","year":"2000","unstructured":"Wuyts, J., De Rijk, P., Van de Peer, Y., Pison, G., Rousseeuw, P., De Wachter, R.: Comparative analysis of more than 3000 sequences reveals the existence of two pseudoknots in area V4 of eukaryotic small subunit ribosomal RNA. Nucl. Acids. Res.\u00a028, 4698\u20134708 (2000)","journal-title":"Nucl. Acids. Res."},{"key":"1_CR23","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":"1_CR24","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","Transactions on Computational Systems Biology II"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11567752_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,5]],"date-time":"2025-01-05T09:08:08Z","timestamp":1736068088000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11567752_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540294016","9783540316619"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/11567752_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}