Bit-Parallel Algorithm for the Constrained Longest Common Subsequence Problem

• Autorzy: Deorowicz S.
• Języki publikacji: EN

Abstrakty

EN

The problem of finding a constrained longest common subsequence (CLCS) for the sequences A and B with respect to the sequence P was introduced recently. Its goal is to find a longest subsequence C of A and B such that P is a subsequence of C. Most of the algorithms solving the CLCS problem are based on dynamic programming. Bit-parallelism is a technique of using single bits in a machine word for concurrent computation. We propose the first bit-parallel algorithm computing a CLCS and/or its length which outperforms the other known algorithms in terms of speed.

Słowa kluczowe

EN

constrained longest common subsequence; longest common subsequence; dynamic programming; bit-parallel algorithm

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 99, nr 4
• Strony: 409--433
• Opis fizyczny: Bibliogr. 31 poz., tab., wykr.

Twórcy

autor

Deorowicz S.

• Silesian University of Technology, Akademicka 16, 44-100 Gliwice, Poland,

Bibliografia

• [1] Allison, L., Dix, T.: A bit-string longest common subsequence algorithm, Information Processing Letters, 23, 1986, 305-310.
• [2] Apostolico, A.: General pattern matchings, chapter 13, Handbook of Algorithms and Theory of Computation, Atallah, M.J., 1998.
• [3] Arslan, A., Ěgecioglu, O.: Algorithms for the constrained longest common subsequence problems, International Journal of Foundations of Computer Science, 16(6), 2005, 1099-1109.
• [4] Baeza-Yates, R., G.H., G.: A new approach to text searching, Communications of the ACM, 35(10), 1992, 74-82.
• [5] Bergroth, L., Hakonen, H., Raita, T.: A survey of longest common subsequence algorithms, Proceedings of 7th International Symposium on String Processing Information Retrieval (SPIRE), Curu˜na, Spain, 2000.
• [6] Chin, F., De Santis, A., Ferrara, A., Ho, N., Kim, S.: A simple algorithm for the constrained sequence problems, Information Processing Letters, 90, 2004, 175-179.
• [7] Chin, F., Ho, N., Lam, T., Wong, P.: Efficient Constrained Multiple Sequence Alignment with Performance Guarantee, Journal of Bioinformatics and Computational Biology, 3(1), 2005, 1-18.
• [8] Chrochemore, M., Landau, G., Ziv-Ukelson, M.: A sub-quadratic sequence alignment algorithm for unrestricted cost matrices, SIAM Journal of Computing, 32(6), 2003, 1654-1673.
• [9] Crochemore,M., Iliopoulos, C., Pinzon, Y., Reid, J.: A fast and practical bit-vector algorithm for the longest common subsequence problem, Information Processing Letters, 80, 2001, 279-285.
• [10] Deorowicz, S.: Fast Algorithm for Constrained Longest Common Subsequence Problem, Theoretical and Applied Informatics, 19(2), 2007, 91-102.
• [11] Deorowicz, S., Obstój, J.: Constrained Longest Common Subsequence Computing Algorithms in Practice, Accepted for publication in Computing and Informatics, 2010, (http://sun.aei.polsl.pl/~sdeor/pub/tr_do2009.pdf).
• [12] Dömölki, B.: An algorithm for syntactical analysis, Computational Linguistics, 3, 1964, 29-46.
• [13] Gotoh, O., Yamada, S., Yada, T.: Multiple Sequence Alignment, in: Handbook of Computational Molecular Biology (S. Aluru, Ed.), chapter 3, Chapman & Hall/CRC, 2006.
• [14] Gusfield, D.: Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology, Cambridge University Press, 1997.
• [15] Hirschberg, D.: An information-theoretic lower bound for the longest common subsequence problem, Information Processing Letters, 7(1), 1978, 40-41.
• [16] Hunt, J., Szymanski, T.: A fast algorithm for computing longest common subsequences, Communications of the ACM, 20(5), 1977, 350-353.
• [17] Hyyrö, H.: Bit-Parallel LCS-length Computation Revisited, Proceedings of the 15th Australian Workshop on Combinatorial Algorithms (AWOCA), University of Sydney, Australia, 2004.
• [18] Iliopoulos, C. S., Rahman, M. S.: New Efficient Algorithms for LCS and Constrained LCS Problem, Information Processing Letters, 106(1), 2008, 13-18.
• [19] Kuo, S., Cross, G.: An Improved Algorithm to Find the Length of the Longest Common Subsequence of Two Strings, ACM SIGIR Forum, 23(3-4), 1989, 89-99.
• [20] Levenshtein, V.: Binary codes capable of correcting deletions, insertions, and reversals, Problems in Information Transmission, 1, 1965, 8-17.
• [21] Lu, C., Huang, Y.: AMemory-EfficientAlgorithm forMultiple Sequence Alignmentwith Constraints, Bioinformatics, 21(1), 2005, 20-30.
• [22] Maier, D.: The Complexity of Some Problems on Subsequences and Supersequences, Journal of the ACM, 25(2), 1978, 322-336.
• [23] Masek, W., Paterson, M.: A faster algorithm computing string edit distances, Journal of Computer System Science, 20(1), 1980, 18-31.
• [24] Peng, C.-L.: An Approach for Solving the Constrained Longest Common Subsequence Problem, Master Thesis, Department of Computer Science and Engineering, National Sun Yat-sen University, Taiwan, 2003, http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/getfile?URN=etd-0828103-125439&filename=etd-0828103-125439.pdf.
• [25] Peng, Z., Ting, H.: Time and Space Efficient Algorithms for Constrained Sequence Alignment, Proceedings of the Implementation and Application of Automata, 9th International Conference (CIAA), 2004.
• [26] Shyu, S., Tsai, C.-Y.: Finding the longest common subsequence for multiple biological sequences by ant colony optimization, Computers and Operations Research, 36(1), 2009, 73-91.
• [27] Tank, C., Lu, C., Chang, M.-T., Tsai, Y.-T., Sun, Y.-J., Chao, K.-M., Chang, J.-M., Chiou, Y.-H., Wu, C.-M., Chang, H.-T., Chou, W.-I.: Constrained multiple sequence alignment tool development and its application to RNase family alignment, Proceedings of the first IEEE Computer Society Bioinformatics Conference (CSB 2002), 2002.
• [28] Tsai, Y.-T.: The constrained common subsequence problem, Information Processing Letters, 88, 2003, 173-176.
• [29] Wang, Q., Korkin, D., Shang, Y.: Efficient dominant point algorithms for the multiple longest common subsequence (MLCS) problem, Proceedings of the 21st International Joint Conference on Artificial Intelligence (H. Kitano, Ed.), Pasadena, California, USA, 2009.
• [30] Wang, W.-L.: Longest Common Subsequence with Constraints, Master Thesis, Department of Computer Science and Information Engineering National Chi-NanUniversity, R. O. C., June 2006, http://alg.csie.ncnu.edu.tw/or/WLWang2006.pdf.
• [31] Wong, C., Chandra, A.: Bounds for the string editing problem, Journal of the ACM, 23(1), 1976, 13-16.