{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T05:14:52Z","timestamp":1737090892010,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540438625"},{"type":"electronic","value":"9783540454526"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45452-7_10","type":"book-chapter","created":{"date-parts":[[2007,5,16]],"date-time":"2007-05-16T01:55:29Z","timestamp":1179280529000},"page":"99-114","source":"Crossref","is-referenced-by-count":10,"title":["Towards Optimally Solving the Longest Common SubsequenceProblem for Sequences with Nested Arc Annotations in Linear Time"],"prefix":"10.1007","author":[{"given":"Jochen","family":"Alber","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jens","family":"Gramm","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jiong","family":"Guo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,6,21]]},"reference":[{"key":"10_CR1","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0012-365X(00)00199-0","volume":"229","author":"J. Alber","year":"2001","unstructured":"J. Alber, J. Gramm, and R. Niedermeier. Faster exact solutions for hard problems: a parameterized point of view. Discrete Mathematics, 229: 3\u201327, 2001.","journal-title":"Discrete Mathematics"},{"key":"10_CR2","first-page":"49","volume":"11","author":"H. L. Bodlaender","year":"1995","unstructured":"H. L. Bodlaender, R. G. Downey, M. R. Fellows, M. T. Hallett, and H. T. Wareham. Parameterized complexity analysis in computational biology. Computer Applications in the Biosciences, 11: 49\u201357, 1995.","journal-title":"Computer Applications in the Biosciences"},{"key":"10_CR3","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/0304-3975(94)00251-D","volume":"147","author":"H. L. Bodlaender","year":"1995","unstructured":"H. L. Bodlaender, R. G. Downey, M. R. Fellows, and H. T. Wareham. The parameterized complexity of sequence alignment and consensus. Theoretical Computer Science, 147:31\u201354, 1995.","journal-title":"Theoretical Computer Science"},{"key":"10_CR4","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/S0166-218X(00)00300-0","volume":"110","author":"P. Bonizzoni","year":"2001","unstructured":"P. Bonizzoni, G. Della Vedova, and G. Mauri. Experimenting an approximation algorithm for the LCS. Discrete Applied Mathematics, 110:13\u201324, 2001.","journal-title":"Discrete Applied Mathematics"},{"key":"10_CR5","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows. Parameterized Complexity. Springer. 1999","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"10_CR6","series-title":"PhD thesis","volume-title":"Algorithms and Complexity for Annotated Sequence Analysis","author":"P. A. Evans","year":"1999","unstructured":"P. A. Evans. Algorithms and Complexity for Annotated Sequence Analysis. PhD thesis, University of Victoria, Canada. 1999."},{"key":"10_CR7","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1007\/3-540-48452-3_20","volume-title":"Proc. of 10th CPM","author":"P. A. Evans","year":"1999","unstructured":"P. A. Evans. Finding common subsequences with arcs and pseudoknots. In Proc. of 10th CPM, number 1645 in LNCS, pages 270\u2013280, 1999. Springer."},{"key":"10_CR8","doi-asserted-by":"crossref","unstructured":"P. A. Evans and H. T. Wareham. Exact algorithms for computing pairwise alignments and 3-medians from structure-annotated sequences. In Proc. of Pacific Symposium on Biocomputing, pages 559\u2013570, 2001.","DOI":"10.1142\/9789814447362_0054"},{"key":"10_CR9","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1007\/3-540-45678-3_26","volume-title":"Proc. of 12th ISAAC","author":"M. R. Fellows","year":"2001","unstructured":"M. R. Fellows. Parameterized complexity: the main ideas and some research frontiers. In Proc. of 12th ISAAC, number 2223 in LNCS, pages 291\u2013307, 2001. Springer."},{"key":"10_CR10","doi-asserted-by":"crossref","unstructured":"D. Goldman, S. Istrail, and C. H. Papadimitriou. Algorithmic aspects of protein structure similarity. In Proc. of 40th IEEE FOCS, pages 512\u2013521, 1999.","DOI":"10.1109\/SFFCS.1999.814624"},{"key":"10_CR11","series-title":"Diploma thesis","volume-title":"Exact Algorithms for the Longest Common Subsequence Problem for Arc-Annotated Sequences","author":"J. Guo","year":"2002","unstructured":"J. Guo. Exact Algorithms for the Longest Common Subsequence Problem for Arc-Annotated Sequences. Diploma thesis, Universit\u00e4t T\u00fcbingen, Fed. Rep. of Germany. February 2002."},{"key":"10_CR12","doi-asserted-by":"crossref","unstructured":"D. Gusfield. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press. 1997.","DOI":"10.1017\/CBO9780511574931"},{"key":"10_CR13","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1007\/3-540-45123-4_15","volume-title":"Proc. of 11th CPM","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 Proc. of 11th CPM, number 1848 in LNCS, pages 154\u2013165, 2000. Springer. Full paper accepted by Journal of Discrete Algorithms."},{"key":"10_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(98)00017-6","volume":"223","author":"O. Kullmann","year":"1999","unstructured":"O. Kullmann. New methods for 3-SAT decision and worst-case analysis. Theoretical Computer Science, 223: 1\u201372, 1999.","journal-title":"Theoretical Computer Science"},{"key":"10_CR15","doi-asserted-by":"crossref","unstructured":"G. Lancia, R. Carr, B. Walenz, and S. Istrail. 101 optimal PDB structure alignments: a branch-and-cut algorithm for the maximum contact map overlap problem. In Proc. of 5th ACM RECOMB, pages 193\u2013202, 2001.","DOI":"10.1145\/369133.369199"},{"key":"10_CR16","doi-asserted-by":"crossref","unstructured":"M. Li, B. Ma, and L. Wang. Near optimal multiple alignment within a band in polynomial time. In Proc. of 32nd ACM STOC, pages 425\u2013434, 2000.","DOI":"10.1145\/335305.335354"},{"key":"10_CR17","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"444","DOI":"10.1007\/3-540-48224-5_37","volume-title":"Proc. of 28th ICALP","author":"G.-H. Lin","year":"2001","unstructured":"G.-H. Lin, Z.-Z. Chen, T. Jiang, and J. Wen. The longest common subsequence problem for sequences with nested arc annotations. In Proc. of 28th ICALP, number 2076 in LNCS, pages 444\u2013455, 2001. Springer."},{"key":"10_CR18","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/3-540-58338-6_63","volume-title":"Proc. of 19th MFCS","author":"M. Paterson","year":"1994","unstructured":"M. Paterson and V. Dancik. Longest common subsequences. In Proc. of 19th MFCS, number 841 in LNCS, pages 127\u2013142, 1994. Springer."},{"key":"10_CR19","unstructured":"D. Sankoff and J. Kruskal (eds.). Time Warps, String Edits, and Macromolecules. Addison-Wesley. 1983. Reprinted in 1999 by CSLI Publications."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45452-7_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T09:13:13Z","timestamp":1737018793000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45452-7_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540438625","9783540454526"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-45452-7_10","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}