Abstract
We investigate four variants of the longest common subsequence problem. Given two sequences X, Y and a constrained pattern P of lengths m, n, and ρ, respectively, the generalized constrained longest common subsequence (GC-LCS) problems are to find a longest common subsequence of X and Y including (or excluding) P as a subsequence (or substring). We propose new dynamic programming algorithms for solving the GC-LCS problems in O(mn ρ) time. We also consider the case where the number of constrained patterns is arbitrary.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aho AV, Hirschberg DS, Ullman JD (1976) Bounds on the complexity of the longest common subsequence problem. J ACM 23:1–12
Apostolico A, Guerra C (1987) The longest common subsequence problem revisited. Algorithmica 2:315–336
Arslan AN, Eǧecioǧlu O (2005) Algorithms for the constrained longest common subsequence problems. Int J Found Comput Sci 16(6):1099–1109
Bergroth L, Hakonen H, Raita T (2000) A survey of longest common subsequence algorithms. In: Proceedings of the 7th international symposium on string processing and information retrieval (SPIRE’00), pp 39–48
Bonizzoni P, Vedova GD, Dondi R, Fertin G, Rizzi R, Vialette S (2007) Exemplar longest common subsequence. IEEE Trans Comput Biol Bioinform 4(4):535–543
Chao KM, Zhang L (2009) Sequence comparison: theory and methods. Springer, Berlin
Chin FYL, Santis AD, Ferrara AL, Ho NL, Kim SK (2004) A simple algorithm for the constrained longest common sequence problems. Inf Process Lett 90:175–179
Chin FYL, Ho NL, Lam TW, Wong PWH (2005) Efficient constrained multiple sequence alignment with performance guarantee. J Bioinform Comput Biol 3(1):1–18
Cormen TH, Leiserson CE, Rivest RL, Stein C (2001). In: Introduction to algorithms, 2nd edn. MIT Press/McGraw-Hill, New York, pp 350–355.
Gotthilf Z, Hermelin D, Lewenstein M (2008) Constrained LCS: hardness and approximation. In: Proceedings of the 19th annual symposium on combinatorial pattern matching (CPM’08), pp 255–262
Gusfield D (1997) Algorithms on strings, trees, and sequences. Cambridge University Press, Cambridge
Hirschberg DS (1975) A linear space algorithm for computing maximal common subsequences. Commun ACM 18:341–343
Hirschberg DS (1977) Algorithms for the longest common subsequence problem. J ACM 24:664–675
Hunt JW, Szymanski TG (1977) A fast algorithm for computing longest common subsequence. Commun ACM 20(5):350–353
Iliopoulos CS, Rahman MS (2008) New efficient algorithms for the LCS and constrained LCS problems. Inf Process Lett 106:13–18
Maier D (1978) The complexity of some problems on subsequences and supersequence. J ACM 25:322–336
Masek WJ, Paterson MS (1980) A faster algorithm computing string edit distances. J Comput Syst Sci 20:18–31
Pevzner PA (2000) Computational molecular biology: An algorithmic approach. MIT Press, Cambridge
Rahman MS, Iliopoulos CS (2007) A new efficient algorithm for computing the longest common subsequence. In: Proceedings of the 3rd international conference on algorithmic aspects in information and management (AAIM’07), pp 82–90
Tang CY, Lu CL, Chang MD, Tsai YT, Sun YJ, Chao KM, Chang JM, Chiou YH, Wu CM, Chang HT, Chou WI (2003) Constrained multiple sequence alignment tool development and its application to RNase family alignment. J Bioinform Comput Biol 1(2):267–287
Tsai YT (2003) The constrained longest common subsequence problem. Inf Process Lett 88:173–176
van Emde Boas P (1977) Preserving order in a forest in less than logarithmic time and linear space. Inf Process Lett 6:80–82
van Emde Boas P, Kaas R, Zijlstra E (1977) Design and implementation of an efficient priority queue. Math Syst Theory 10:99–127
Wagner RA, Fischer MJ (1974) The string-to-string correction problem. J ACM 21(1):168–173
Author information
Authors and Affiliations
Corresponding author
Additional information
This research was supported in part by NSC grants NSC 95-2221-E-002-126-MY3 and NSC 97-2221-E-002-097-MY3 from the National Science Council, Taiwan.
Rights and permissions
About this article
Cite this article
Chen, YC., Chao, KM. On the generalized constrained longest common subsequence problems. J Comb Optim 21, 383–392 (2011). https://doi.org/10.1007/s10878-009-9262-5
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-009-9262-5