{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T11:22:22Z","timestamp":1780053742591,"version":"3.54.0"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2008,3,4]],"date-time":"2008-03-04T00:00:00Z","timestamp":1204588800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2010,2]]},"DOI":"10.1007\/s00453-008-9175-1","type":"journal-article","created":{"date-parts":[[2008,3,3]],"date-time":"2008-03-03T16:52:39Z","timestamp":1204563159000},"page":"270-280","source":"Crossref","is-referenced-by-count":4,"title":["On the Longest Common Rigid Subsequence Problem"],"prefix":"10.1007","volume":"56","author":[{"given":"Nikhil","family":"Bansal","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Moshe","family":"Lewenstein","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bin","family":"Ma","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kaizhong","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2008,3,4]]},"reference":[{"key":"9175_CR1","doi-asserted-by":"crossref","unstructured":"Adebiyi, E.F., Kaufmann, M.: Extracting common motifs under the Levenshtein measure: theory and experimentation. In: Proceedings of the Workshop on Algorithms for Bioinformatics (WABI), pp.\u00a0140\u2013156 (2002)","DOI":"10.1007\/3-540-45784-4_11"},{"key":"9175_CR2","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/S0304-3975(98)00158-3","volume":"237","author":"P. Alimonti","year":"2000","unstructured":"Alimonti, P., Kann, V.: Some APX-completeness results for cubic graphs. Theor. Comput. Sci. 237, 123\u2013134 (2000)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9175_CR3","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1007\/BF01277956","volume":"5","author":"N. Alon","year":"1995","unstructured":"Alon, N., Feige, U., Wigderson, A., Zuckerman, D.: Derandomized graph products. Comput. Complex. 5(1), 60\u201375 (1995)","journal-title":"Comput. Complex."},{"key":"9175_CR4","doi-asserted-by":"crossref","DOI":"10.1002\/0471722154","volume-title":"The Probabilistic Method","author":"N. Alon","year":"2000","unstructured":"Alon, N., Spencer, J.: The Probabilistic Method. Wiley, New York (2000)"},{"key":"9175_CR5","first-page":"399","volume-title":"Hardness of Approximations, Approximation Algorithms for NP-hard Problems","author":"S. Arora","year":"1996","unstructured":"Arora, S., Lund, C.: In: Hochbaum, D. (ed.) Hardness of Approximations, Approximation Algorithms for NP-hard Problems, pp. 399\u2013446. PWS, Boston (1996)"},{"issue":"39","key":"9175_CR6","doi-asserted-by":"crossref","first-page":"24034","DOI":"10.1016\/S0021-9258(19)51043-2","volume":"269","author":"C. Cheadle","year":"1994","unstructured":"Cheadle, C., Ivashchenko, Y., South, V., Searfoss, G., French, S., Howk, R., Ricca, G., Jaye, M.: Identification of a src sh3 domain binding motif by screening a random phage display library. J. Biol. Chem. 269(39), 24034\u201324039 (1994)","journal-title":"J. Biol. Chem."},{"issue":"5","key":"9175_CR7","doi-asserted-by":"crossref","first-page":"1122","DOI":"10.1137\/S009753979223842X","volume":"24","author":"T. Jiang","year":"1995","unstructured":"Jiang, T., Li, M.: On the approximation of shortest common supersequence and longest common subsequences. SIAM J. Comput. 24(5), 1122\u20131139 (1995)","journal-title":"SIAM J. Comput."},{"key":"9175_CR8","doi-asserted-by":"crossref","unstructured":"Keich, U., Pevzner, P.A.: Finding motifs in the twilight zone. In: Proceedings of the Sixth Annual International Conference on Computational Biology, pp. 195\u2013204 (2002)","DOI":"10.1145\/565196.565222"},{"issue":"1","key":"9175_CR9","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/S0890-5401(03)00057-9","volume":"185","author":"J.K. Lanctot","year":"2003","unstructured":"Lanctot, J.K., Li, M., Ma, B., Wang, S., Zhang, L.: Distinguishing string selection problems. Inf. Comput. 185(1), 41\u201355 (2003). Early version appeared in SODA\u201999","journal-title":"Inf. Comput."},{"key":"9175_CR10","doi-asserted-by":"crossref","unstructured":"Li, M., Ma, B., Wang, L.: Finding similar regions in many strings. In: Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing (STOC), Atlanta, May 1999, pp. 473\u2013482 (1999)","DOI":"10.1145\/301250.301376"},{"issue":"1","key":"9175_CR11","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1006\/jcss.2002.1823","volume":"65","author":"M. Li","year":"2002","unstructured":"Li, M., Ma, B., Wang, L.: Finding similar regions in many sequences. J. Comput. Syst. Sci. 65(1), 73\u201396 (2002). Early version appeared in STOC\u201999","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"9175_CR12","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1145\/506147.506150","volume":"49","author":"M. Li","year":"2002","unstructured":"Li, M., Ma, B., Wang, L.: On the closest string and substring problems. J. ACM 49(2), 157\u2013171 (2002). Early versions appeared in STOC\u201999 and CPM\u201900","journal-title":"J. ACM"},{"key":"9175_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/3-540-45123-4_10","volume-title":"Combinatorial Pattern Matching, 11th Annual Symposium CPM","author":"B. Ma","year":"2000","unstructured":"Ma, B.: A polynomial time approximation scheme for the closest substring problem. In: Giancarlo, R., Sankoff, D. (eds.) Combinatorial Pattern Matching, 11th Annual Symposium CPM, Montreal, Canada, June 21\u201323 2000. Lecture Notes in Computer Science, vol. 1848, pp. 99\u2013107. Springer, Berlin (2000)"},{"key":"9175_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1007\/11496656_2","volume-title":"Combinatorial Pattern Matching, 16th Annual Symposium CPM","author":"B. Ma","year":"2005","unstructured":"Ma, B., Zhang, K.: On the longest common rigid subsequence problem. In: Apostolico, A., Crochemore, M., Park, K. (eds.) Combinatorial Pattern Matching, 16th Annual Symposium CPM, Jeju Island, Korea, June 19\u201322 2005. Lecture Notes in Computer Science, vol. 3537, pp. 11\u201320. Springer, Berlin (2005)"},{"key":"9175_CR15","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1145\/322063.322075","volume":"25","author":"D. Maier","year":"1978","unstructured":"Maier, D.: The complexity of some problems on subsequences and supersequences. J. ACM 25, 322\u2013336 (1978)","journal-title":"J. ACM"},{"key":"9175_CR16","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43, 425\u2013440 (1991)","journal-title":"J. Comput. Syst. Sci."},{"key":"9175_CR17","doi-asserted-by":"crossref","unstructured":"Rajasekaran, S., Balla, S., Huang, C.: Exact algorithms for planted motif challenge problems. In: Proceedings of the 3rd Asia Pacific Bioinformatics Conference, pp.\u00a0249\u2013259 (2005)","DOI":"10.1142\/9781860947322_0025"},{"key":"9175_CR18","doi-asserted-by":"crossref","unstructured":"Rajasekaran, S., Balla, S., Huang, C., Thapar, V., Gryk, M., Maciejewski, M., Schiller, M.: Exact algorithms for motif search. In: Proceedings of the 3rd Asia Pacific Bioinformatics Conference, pp.\u00a0239\u2013248 (2005)","DOI":"10.1142\/9781860947322_0024"},{"issue":"1","key":"9175_CR19","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1093\/bioinformatics\/14.1.55","volume":"14","author":"I. Rigoutsos","year":"1998","unstructured":"Rigoutsos, I., Floratos, A.: Combinatorial pattern discovery in biological sequences: the teiresias algorithm. Bioinformatics 14(1), 55\u201367 (1998)","journal-title":"Bioinformatics"},{"issue":"4","key":"9175_CR20","doi-asserted-by":"crossref","first-page":"1183","DOI":"10.1073\/pnas.86.4.1183","volume":"86","author":"G. Stormo","year":"1999","unstructured":"Stormo, G., Hartzell, G.W.: Identifying protein-binding sites from unaligned DNA fragments. Proc. Natl. Acad. Sci. USA 86(4), 1183\u20131187 (1999)","journal-title":"Proc. Natl. Acad. Sci. USA"},{"issue":"4","key":"9175_CR21","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1007\/BF02459500","volume":"46","author":"M. Waterman","year":"1984","unstructured":"Waterman, M., Arratia, R., Galas, D.J.: Pattern recognition in several sequences: consensus and alignment. Bull. Math. Biol. 46(4), 515\u2013527 (1984)","journal-title":"Bull. Math. Biol."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9175-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-008-9175-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9175-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,5]],"date-time":"2021-09-05T03:56:44Z","timestamp":1630814204000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-008-9175-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,3,4]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,2]]}},"alternative-id":["9175"],"URL":"https:\/\/doi.org\/10.1007\/s00453-008-9175-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,3,4]]}}}