{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T20:27:30Z","timestamp":1761596850787},"reference-count":17,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[2004,6,1]],"date-time":"2004-06-01T00:00:00Z","timestamp":1086048000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,18]],"date-time":"2013-07-18T00:00:00Z","timestamp":1374105600000},"content-version":"vor","delay-in-days":3334,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Discrete Algorithms"],"published-print":{"date-parts":[[2004,6]]},"DOI":"10.1016\/s1570-8667(03)00080-7","type":"journal-article","created":{"date-parts":[[2004,5,8]],"date-time":"2004-05-08T08:09:36Z","timestamp":1084003776000},"page":"257-270","source":"Crossref","is-referenced-by-count":31,"title":["The longest common subsequence problem for arc-annotated sequences"],"prefix":"10.1016","volume":"2","author":[{"given":"Tao","family":"Jiang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guohui","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":"78","reference":[{"key":"10.1016\/S1570-8667(03)00080-7_BIB001","series-title":"Proceedings of 6th Annual Symposium on Combinatorial Pattern Matching (CPM'95)","first-page":"1","article-title":"Computing similarity between RNA strings","volume":"vol. 937","author":"Bafna","year":"1995"},{"key":"10.1016\/S1570-8667(03)00080-7_BIB002","doi-asserted-by":"crossref","unstructured":"V. Bafna, S. Muthukrishnan, R. Ravi, Computing similarity between RNA strings, Technical Report 96-30, DIMACS, 1996","DOI":"10.1007\/3-540-60044-2_30"},{"key":"10.1016\/S1570-8667(03)00080-7_BIB003","doi-asserted-by":"crossref","first-page":"804","DOI":"10.1137\/S0097539796302531","article-title":"Free bits, PCPs and non-approximability\u2014towards tight results","volume":"27","author":"Bellare","year":"1998","journal-title":"SIAM J. Comput"},{"key":"10.1016\/S1570-8667(03)00080-7_BIB004","series-title":"Proceedings of the 4th International Workshop on Algorithms and Data Structures (WADS'95)","first-page":"449","article-title":"On approximation properties of the independent set problem for degree 3 graphs","volume":"vol. 955","author":"Berman","year":"1995"},{"key":"10.1016\/S1570-8667(03)00080-7_BIB005","first-page":"389","article-title":"RNAling program: alignment of RNA sequences using both primary and secondary structures","volume":"10","author":"Corpet","year":"1994","journal-title":"Computer Applications in the Biosciences"},{"key":"10.1016\/S1570-8667(03)00080-7_BIB006","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/S0166-218X(97)00023-1","article-title":"A special case for subset interconnection designs","volume":"78","author":"Du","year":"1997","journal-title":"Discrete Appl. Math"},{"key":"10.1016\/S1570-8667(03)00080-7_BIB007","unstructured":"P.A. Evans, Algorithms and complexity for annotated sequence analysis, PhD Thesis, University of Victoria, 1999"},{"key":"10.1016\/S1570-8667(03)00080-7_BIB008","series-title":"Proceedings of 10th Annual Symposium on Combinatorial Pattern Matching (CPM'99)","first-page":"270","article-title":"Finding common subsequences with arcs and pseudoknots","volume":"vol. 1645","author":"Evans","year":"1999"},{"key":"10.1016\/S1570-8667(03)00080-7_BIB009","series-title":"IEEE Proceedings of the 40th Annual Conference of Foundations of Computer Science (FOCS'99)","first-page":"512","article-title":"Algorithmic aspects of protein structure similarity","author":"Goldman","year":"1999"},{"key":"10.1016\/S1570-8667(03)00080-7_BIB010","unstructured":"D.S. Hirschberg, The longest common subsequence problem, PhD Thesis, Princeton University, 1975"},{"key":"10.1016\/S1570-8667(03)00080-7_BIB011","series-title":"Proceedings of the Second Annual International Conference on Computational Molecular Biology (RECOMB'98)","first-page":"153","article-title":"A polyhedral approach to RNA sequence structure alignment","author":"Lenhof","year":"1998"},{"key":"10.1016\/S1570-8667(03)00080-7_BIB012","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1016\/S0022-0000(02)00004-1","article-title":"The longest common subsequence problem for sequences with nested arc annotations","volume":"65","author":"Lin","year":"2002","journal-title":"J. Comput. System Sci"},{"key":"10.1016\/S1570-8667(03)00080-7_BIB013","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","article-title":"Optimization, approximation, and complexity classes","volume":"43","author":"Papadimitriou","year":"1991","journal-title":"J. Comput. System Sci"},{"key":"10.1016\/S1570-8667(03)00080-7_BIB014","doi-asserted-by":"crossref","first-page":"810","DOI":"10.1137\/0145048","article-title":"Simultaneous solution of the RNA folding, alignment, and protosequence problems","volume":"45","author":"Sankoff","year":"1985","journal-title":"SIAM J. Appl. Math"},{"key":"10.1016\/S1570-8667(03)00080-7_BIB015","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","article-title":"Identification of common molecular subsequences","volume":"147","author":"Smith","year":"1981","journal-title":"J. Mol. Biol"},{"key":"10.1016\/S1570-8667(03)00080-7_BIB016","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1145\/321796.321811","article-title":"The string-to-string correction problem","volume":"21","author":"Wagner","year":"1974","journal-title":"J. ACM"},{"key":"10.1016\/S1570-8667(03)00080-7_BIB017","series-title":"Proceedings of 10th Annual Symposium on Combinatorial Pattern Matching (CPM'99)","first-page":"281","article-title":"Computing similarity between RNA structures","volume":"vol. 1645","author":"Zhang","year":"1999"}],"container-title":["Journal of Discrete Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1570866703000807?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1570866703000807?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2023,4,28]],"date-time":"2023-04-28T16:01:06Z","timestamp":1682697666000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S1570866703000807"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,6]]},"references-count":17,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2004,6]]}},"alternative-id":["S1570866703000807"],"URL":"https:\/\/doi.org\/10.1016\/s1570-8667(03)00080-7","relation":{},"ISSN":["1570-8667"],"issn-type":[{"value":"1570-8667","type":"print"}],"subject":[],"published":{"date-parts":[[2004,6]]}}}