{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,23]],"date-time":"2025-01-23T11:40:12Z","timestamp":1737632412824,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540676331"},{"type":"electronic","value":"9783540451235"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-45123-4_15","type":"book-chapter","created":{"date-parts":[[2007,11,13]],"date-time":"2007-11-13T19:59:14Z","timestamp":1194983954000},"page":"154-165","source":"Crossref","is-referenced-by-count":0,"title":["The Longest Common Subsequence Problem for Arc-Annotated Sequences"],"prefix":"10.1007","author":[{"given":"Tao","family":"Jiang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guo-Hui","family":"Lin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bin","family":"Ma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kaizhong","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,11,7]]},"reference":[{"key":"15_CR1","doi-asserted-by":"crossref","unstructured":"V. Bafna, S. Muthukrishnan and R. Ravi, Computing similarity between RNA strings, DIMACS Technical Report 96\u201330, 1996.","DOI":"10.1007\/3-540-60044-2_30"},{"key":"15_CR2","doi-asserted-by":"publisher","first-page":"804","DOI":"10.1137\/S0097539796302531","volume":"27","author":"M. Bellare","year":"1998","unstructured":"M. Bellare, O. Goldreich and M. Sudan, Free bits, PCPs and non-approximability-towards tight results, SIAM Journal on Computing, 27(1998), 804\u2013915.","journal-title":"SIAM Journal on Computing"},{"key":"15_CR3","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1007\/3-540-60220-8_84","volume-title":"Proceedings of 4th International Workshop on Algorithms and Data Structures (WADS\u201995)","author":"P. Berman","year":"1995","unstructured":"P. Berman and T. Fujito, On approximation properties of the independent set problem for degree 3 graphs, in Proceedings of 4th International Workshop on Algorithms and Data Structures (WADS\u201995), LNCS 955, pp. 449\u2013460."},{"key":"15_CR4","first-page":"389","volume":"10","author":"F. Corpet","year":"1994","unstructured":"F. Corpet and B. Minchor, RNAling program: alignment of RNA sequences using both primary and secondary structures, Computer Applications in the Bio-sciences, 10(1994), 389\u2013399.","journal-title":"Computer Applications in the Bio-sciences"},{"key":"15_CR5","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/S0166-218X(97)00023-1","volume":"78","author":"D.Z. D. Gao","year":"1997","unstructured":"D.Z. Du, Gao and W. Wu, A special case for subset interconnection designs, Discrete Applied Mathematics, 78(1997), 51\u201360.","journal-title":"Discrete Applied Mathematics"},{"key":"15_CR6","unstructured":"P.A. Evans, Algorithms and Complexity for Annotated Sequence Analysis, Ph. D Thesis, University of Victoria, 1999."},{"key":"15_CR7","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1007\/3-540-48452-3_20","volume-title":"Proceedings of 10th Annual Symposium on Combinatorial Pattern Matching (CPM\u201999)","author":"P.A. Evans","year":"1999","unstructured":"P.A. Evans, Finding common subsequences with arcs and pseudoknots, in Proceedings of 10th Annual Symposium on Combinatorial Pattern Matching (CPM\u201999), LNCS 1645, pp. 270\u2013280."},{"key":"15_CR8","doi-asserted-by":"crossref","unstructured":"D. Goldman, S. Istrail and C.H. Papadimitriou, Algorithmic aspects of protein structure similarity, Proc. IEEE 40th Annual Conference of Foundations of Computer Science (FOCS\u201999), 1999.","DOI":"10.1109\/SFFCS.1999.814624"},{"key":"15_CR9","unstructured":"D.S. Hirschberg, The longest common subsequence problem. Ph.D. Thesis, Princeton University, 1975."},{"key":"15_CR10","doi-asserted-by":"crossref","unstructured":"H. Lenhof, K. Reinert and M. Vingron, A polyhedral approach to RNA sequence structure alignment, in Proceedings of the Second Annual International Conference on Computational Molecular Biology (RECOMB\u201998), 153\u2013159.","DOI":"10.1145\/279069.279109"},{"key":"15_CR11","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C.H. Papadimitriou","year":"1991","unstructured":"C.H. Papadimitriou and M. Yannakakis, Optimization, approximation, and complexity classes, Journal of Computer and System Science, 43(1991), 425\u2013440.","journal-title":"Journal of Computer and System Science"},{"key":"15_CR12","doi-asserted-by":"publisher","first-page":"810","DOI":"10.1137\/0145048","volume":"45","author":"D. Sankoff","year":"1985","unstructured":"D. Sankoff, Simultaneous solution of the RNA folding, alignment, and protosequence problems, SIAM Journal on Applied Mathematics, 45(1985), 810\u2013825.","journal-title":"SIAM Journal on Applied Mathematics"},{"issue":"1","key":"15_CR13","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1145\/321796.321811","volume":"21","author":"R.A. Wagner","year":"1974","unstructured":"R.A. Wagner and M.J. Fischer, The string-to-string correction problem. Journal of the ACM, 21(1)(1974), 168\u2013173.","journal-title":"Journal of the ACM"},{"key":"15_CR14","series-title":"Lect Notes Comput Sci","first-page":"281","volume-title":"Proceedings of 10th Annual Symposium on Combinatorial Pattern Matching (CPM\u201999)","author":"K. Zhang","year":"1645","unstructured":"K. Zhang, L. Wang and B. Ma, Computing similarity between RNA structures, in Proceedings of 10th Annual Symposium on Combinatorial Pattern Matching (CPM\u201999), LNCS 1645, pp. 281\u2013293."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45123-4_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,22]],"date-time":"2025-01-22T08:16:40Z","timestamp":1737533800000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45123-4_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540676331","9783540451235"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-45123-4_15","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}