{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T23:45:52Z","timestamp":1725493552023},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540422877"},{"type":"electronic","value":"9783540482246"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-48224-5_37","type":"book-chapter","created":{"date-parts":[[2007,10,28]],"date-time":"2007-10-28T06:29:04Z","timestamp":1193552944000},"page":"444-455","source":"Crossref","is-referenced-by-count":5,"title":["The Longest Common Subsequence Problem for Sequences with Nested Arc Annotations"],"prefix":"10.1007","author":[{"given":"Guo-Hui","family":"Lin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhi-Zhong","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tao","family":"Jiang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianjun","family":"Wen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,7,4]]},"reference":[{"key":"37_CR1","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/BF01934985","volume":"25","author":"S. Arnborg","year":"1985","unstructured":"S. Arnborg. Efficient algorithms for combinatorial problems on graphs with bounded decomposability: a survey. BIT, 25:2\u201323, 1985.","journal-title":"BIT"},{"key":"37_CR2","series-title":"Lect Notes Comput Sci","first-page":"1","volume-title":"Proceedings of 6th Annual Symposium on Combinatorial Pattern Matching (CPM\u201995)","author":"V. Bafna","year":"1995","unstructured":"V. Bafna, S. Muthukrishnan, and R. Ravi. Computing similarity between RNA strings. In Proceedings of 6th Annual Symposium on Combinatorial Pattern Matching (CPM\u201995), LNCS 937, pages 1\u201316, 1995."},{"key":"37_CR3","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B.S. Baker","year":"1994","unstructured":"B.S. Baker. Approximation algorithms for NP-complete problems on planar graphs. Journal of the ACM, 41:153\u2013180, 1994.","journal-title":"Journal of the ACM"},{"key":"37_CR4","unstructured":"T.C. Biedl, P. Bose, E.D. Demaine, and A. Lubiw. Efficient algorithms for Peterson\u2019s matching theorem. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201999), pages 130\u2013139, 1999."},{"key":"37_CR5","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/PL00009182","volume":"19","author":"T.C. Biedl","year":"1997","unstructured":"T.C. Biedl, G. Kant, and M. Kaufmann. On triangulating planar graphs under the four-connectivity constraint. Algorithmica, 19:427\u2013446, 1997.","journal-title":"Algorithmica"},{"key":"37_CR6","series-title":"Technical Report RUU-CS-88-14","volume-title":"Planar graphs with bounded treewidth","author":"H.L. Bodlaender","year":"1988","unstructured":"H.L. Bodlaender. Planar graphs with bounded treewidth. Technical Report RUU-CS-88-14, Department of Computer Science, Utrecht University, The Netherlands, March 1988."},{"key":"37_CR7","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"H.L. Bodlaender. A linear time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25:1305\u20131317, 1996.","journal-title":"SIAM Journal on Computing"},{"key":"37_CR8","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1006\/jagm.1997.0894","volume":"26","author":"Z.-Z. Chen","year":"1998","unstructured":"Z.-Z. Chen. Efficient approximation schemes for maximization problems on K 3,3-free or K 5-free graphs. Journal of Algorithms, 26:166\u2013187, 1998.","journal-title":"Journal of Algorithms"},{"key":"37_CR9","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1137\/0608002","volume":"8","author":"F.R.K. Chung","year":"1987","unstructured":"F.R.K. Chung, F.T. Leighton, and A.L. Rosenberg. Embedding graphs in books: a graph layout problem with applications to VLSI design. SIAM Journal on Algebraic and Discrete Methods, 8:33\u201358, 1987.","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"key":"37_CR10","first-page":"389","volume":"10","author":"F. Corpet","year":"1994","unstructured":"F. Corpet and B. Michot. RNAling program: alignment of RNA sequences using both primary and secondary structures. Computer Applications in the Biosciences, 10:389\u2013399, 1994.","journal-title":"Computer Applications in the Biosciences"},{"key":"37_CR11","unstructured":"P.A. Evans. Algorithms and Complexity for Annotated Sequence Analysis. PhD thesis, University of Victoria, 1999."},{"key":"37_CR12","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1137\/0601025","volume":"1","author":"M.R. Garey","year":"1980","unstructured":"M.R. Garey, D.S. Johnson, G.L. Miller, and C.H. Papadimitriou. The complexity of coloring circular arcs and chords. SIAM Journal on Algebraic and Discrete Methods, 1:216\u2013227, 1980.","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"key":"37_CR13","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M.R. Garey","year":"1976","unstructured":"M.R. Garey, D.S. Johnson, and L. Stockmeyer. Some simplified NP-complete graph problems. Theoretical Computer Science, 1:237\u2013267, 1976.","journal-title":"Theoretical Computer Science"},{"key":"37_CR14","doi-asserted-by":"crossref","unstructured":"D. Goldman, S. Istrail, and C.H. Papadimitriou. Algorithmic aspects of protein structure similarity. In IEEE Proceedings of the 40th Annual Conference of Foundations of Computer Science (FOCS\u201999), pages 512\u2013521, 1999.","DOI":"10.1109\/SFFCS.1999.814624"},{"key":"37_CR15","doi-asserted-by":"crossref","unstructured":"D. Gusfield. Algorithms on Strings, Trees, and Sequences. Cambridge, 1997.","DOI":"10.1017\/CBO9780511574931"},{"key":"37_CR16","unstructured":"D.S. Hirschberg. The Longest Common Subsequence Problem. PhD thesis, Princeton University, 1975."},{"key":"37_CR17","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1007\/3-540-45123-4_15","volume-title":"Proceedings of the 11th Annual Symposium on Combinatorial Pattern Matching (CPM 2000)","author":"T. Jiang","year":"2000","unstructured":"T. Jiang, G.-H. Lin, B. Ma, and K. Zhang. The longest common subsequence problem for arc-annotated sequences. In Proceedings of the 11th Annual Symposium on Combinatorial Pattern Matching (CPM 2000), LNCS 1848, pages 154\u2013165, 2000. Full paper accepted by Journal of Discrete Algorithms."},{"key":"37_CR18","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), pages 153\u2013159, 1998.","DOI":"10.1145\/279069.279109"},{"key":"37_CR19","doi-asserted-by":"crossref","unstructured":"M. Li, B. Ma, and L. Wang. Near optimal multiple sequence alignment within a band in polynomial time. In ACM Proceedings of the 32nd Annual Symposium on Theory of Computing (STOC\u201900), pages 425\u2013434, 2000.","DOI":"10.1145\/335305.335354"},{"key":"37_CR20","doi-asserted-by":"crossref","unstructured":"G.-H. Lin, Z.-Z. Chen, T. Jiang, and J.-J. Wen. The longest common subsequence problem for sequences with nested arc annotations, February 2001. Manuscript.","DOI":"10.1007\/3-540-48224-5_37"},{"key":"37_CR21","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/BF02392606","volume":"15","author":"J. Peterson","year":"1891","unstructured":"J. Peterson. Die theorie der regul\u00e4ren graphs (the theory of regular graphs). Acta Mathematica, 15:193\u2013220, 1891.","journal-title":"Acta Mathematica"},{"key":"37_CR22","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:810\u2013825, 1985.","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"37_CR23","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","volume":"147","author":"T.F. Smith","year":"1981","unstructured":"T.F. Smith and M.S. Waterman. Identification of common molecular subsequences. Journal of Molecular Biology, 147:195\u2013197, 1981.","journal-title":"Journal of Molecular Biology"},{"key":"37_CR24","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:168\u2013173, 1974.","journal-title":"Journal of the ACM"},{"key":"37_CR25","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/0022-0000(89)90032-9","volume":"38","author":"M. Yannakakis","year":"1989","unstructured":"M. Yannakakis. Embedding planar graphs in four pages. Journal of Computer and System Sciences, 38:36\u201367, 1989.","journal-title":"Journal of Computer and System Sciences"},{"key":"37_CR26","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/3-540-48452-3_21","volume-title":"Proceedings of 10th Annual Symposium on Combinatorial Pattern Matching (CPM\u201999)","author":"K. Zhang","year":"1999","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, pages 281\u2013293, 1999."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48224-5_37","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,4]],"date-time":"2019-05-04T02:28:21Z","timestamp":1556936901000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48224-5_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540422877","9783540482246"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/3-540-48224-5_37","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}