Computing a Longest Common Palindromic Subsequence

• Autorzy: Chowdhury, S. R. , Hasan, M. M. , Iqbal, S. , Rahman, M. S.
• Języki publikacji: EN

Abstrakty

EN

The longest common subsequence (LCS) problem is a classic and well-studied problem in computer science. Palindrome is a word which reads the same forward as it does backward. The longest common palindromic subsequence (LCPS) problem is a variant of the classic LCS problem which finds a longest common subsequence between two given strings such that the computed subsequence is also a palindrome. In this paper, we study the LCPS problem and give two novel algorithms to solve it. To the best of our knowledge, this is the first attempt to study and solve this problem.

Słowa kluczowe

EN

longest common subsequence; palindrome; dynamic programming; range query

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 129, nr 4
• Strony: 329--340
• Opis fizyczny: Bibliogr. 17 poz.

Twórcy

autor

Chowdhury, S. R.

• AℓEDA group, Department of CSE, Bangladesh University of Engineering & Technology Dhaka - 1000, Bangladesh,

autor

Hasan, M. M.

• AℓEDA group, Department of CSE, Bangladesh University of Engineering & Technology Dhaka - 1000, Bangladesh,

autor

Iqbal, S.

• AℓEDA group, Department of CSE, Bangladesh University of Engineering & Technology Dhaka - 1000, Bangladesh,

autor

Rahman, M. S.

• AℓEDA group, Department of CSE, Bangladesh University of Engineering & Technology Dhaka - 1000, Bangladesh,

Bibliografia

• [1] Bentley, J. L., Friedman, J. H.: Data Structures for Range Searching, ACM Comput. Surv., 11, December 1979, 397–409, ISSN 0360-0300.
• [2] Breslauer, D., Galil, Z.: Finding all periods and initial palindromes of a string in parallel, Algorithmica, 14, October 1995, 355 – 366.
• [3] Chen, K.-Y., Hsu, P.-H., Chao, K.-M.: IdentifyingApproximate Palindromes in Run-Length Encoded Strings, Proceedings of 21st International Symposium, ISAAC 2010, Jeju, Korea, December 15-17, 2010, 2010.
• [4] Choi, C.: DNA palindromes found in cancer, Genome Biology, 6, 2005, ISSN 1465-6906.
• [5] van Emde Boas, P.: Preserving order in a forest in less than logarithmic time, Proceedings of the 16th Annual Symposium on Foundations of Computer Science, IEEE Computer Society,Washington, DC, USA, 1975.
• [6] Galil, Z.: Real-time algorithms for string-matching and palindrome recognition, Proceedings of the eighth annual ACM symposium on Theory of computing, 1976.
• [7] Gusfield, D.: Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, Cambridge University Press, New York, 1997.
• [8] Hsu, P.-H., Chen, K.-Y., Chao, K.-M.: Finding All Approximate Gapped Palindromes, Proceedings of 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009., 2009.
• [9] I, T., Shunsuke, I., Masayuki, T.: Palindrome Pattern Matching, Proceedings of 22nd Annual Symposium, CPM 2011, Palermo, Italy, June 27-29, 2011., 2011.
• [10] Iliopoulos, C., Rahman, M.: A New Efficient Algorithm for Computing the Longest Common Subsequence, Theory of Computing Systems, 45, 2009, 355–371, ISSN 1432-4350.
• [11] Kolpakov, R., Kucherov, G.: Searching for gapped palindromes, Theoretical Computer Science, November 2009, 5365 – 5373.
• [12] Lange, J., Skaletsky, H., van Daalen, S. K.M., Embry, S. L., Korver, C.M., Brown, L. G., Oates, R. D., Silber, S., Repping, S., Page, D. C.: Isodicentric Y Chromosomes and Sex Disorders as Byproducts of Homologous Recombination that Maintains Palindromes, Cell, 138, September 2009, 855–869.
• [13] Manacher,G.: A new Linear-TimeOn-Line Algorithmfor Finding the Smallest Initial Palindrome of a String, Journal of the ACM, 22, July 1975, 346 – 351.
• [14] Martnek, T., Lexa, M.: Hardware acceleration of approximate palindromes searching, Proceedings of The International Conference on Field-Programmable Technology, 2008.
• [15] Matsubara, W., Inenaga, S., Ishino, A., Shinohara, A., Nakamura, T., Hashimoto, K.: Efficient algorithms to compute compressed longest common substrings and compressed palindromes, Theoretical Computer Science, 410, March 2009, 900–913.
• [16] Porto, A. H. L., Barbosa, V. C.: Finding Approximate Palindromes in Strings, Pattern Recognition, 2002.
• [17] Tanaka, H., Bergstrom, D. A., Yao, M.-C., Tapscott, S. J.: Large DNA palindromes as a common form of structural chromosome aberrations in human cancers, Human Cell, 19(1), 2006, 17–23, ISSN 1749-0774

Identyfikatory

DOI

10.3233/FI-2014-974