Fast algorithm for the constrained longest common subsequence problem

• Autorzy: Deorowicz S.

Warianty tytułu

PL

Szybki algorytm dla znalezienia najdłuższego kluczowego wspólnego podciągu

• Języki publikacji: EN

Abstrakty

EN

The problem of finding the 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 the longest subsequence of A and B such that P is a subsequence of it. The best known algorithms for its solving require time of order of a product of the sequence lengths. We introduce a novel approach in which time and space complexities depend also on the number of matches between A, B, and P. The time complexity is better for typical parameter settings and never worse.

PL

Problem wyznaczania najdłuższego wspólnego podciągu ciągów A i B, którego podciągiem jest podciąg P (CLCS) pojawił się˛ literaturze stosunkowo niedawno. Złożoności obliczeniowe najlepszych znanych algorytmów są˛ iloczynem długości wszystkich ciągów. W niniejszej pracy przedstawione jest nowy algorytm rozwiązywania tego problemu, dla którego złożoność´ obliczeniowa zależy od liczby dopasować pomiędzy ciągami A, B i P. Złożoność´ ta jest zwykle lepsza (a nigdy gorsza) niż najlepszych znanych do tej pory algorytmów.

Słowa kluczowe

EN

longest common subsequence; constrained longest common subsequence; string matching

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Theoretical and Applied Informatics
• Rocznik: 2007
• Tom: Vol. 19, No. 2
• Strony: 91--102
• Opis fizyczny: Bibliogr. 13 poz., rys.

Twórcy

autor

Deorowicz S.

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

Bibliografia

• [1] Arslan A.N., Eğecioğlu Ö.: Algorithms for the constrained longest common subsequence problems. International Journal of Foundations of Computer Science. 16(6), pp. 1099-1109, 2005.
• [2] Apostolico A.: General patternmatchings. Chapter in Handbook of Algorithms and Theory of Computation, M.J. Atallah (Editor), Chapter 13, 1998.
• [3] Bergroth L., Hakonen H., Raita T.: A survey of longest common subsequence algorithms. In Proceedings of 7th International Symposiumon String Processing Information Retrieval (SPIRE), Curuña, Spain, pp. 39-48, 2000.
• [4] Chin F.Y.L., Ho N.L., Lam T.W.,Wong P.W.H., ChanM.Y.: Efficient ConstrainedMultiple Sequence Alignment with Performance Guarantee. Journal of Bioinformatics and Computational Biology, 3(1), pp. 1-18, 2005.
• [5] Chin F.Y.L., De Santis A., Ferrara A.L., Ho N.L., Kim S.K.: A simple algorithm for the constrained sequence problems. Information Processing Letters, 90, pp. 175-179, 2004.
• [6] Gusfield D.: Algorithms on strings, trees, and sequences. Cambridge University Press, USA (1999).
• [7] He D., Arslan A.N.: A Space-Efficient Algorithm for the Constrained Pairwise Sequence Alignment Problem. Genome Informatics, 16(2), pp. 237-246, 2005.
• [8] Hirschberg D.S.: Algorithms for the longest common subsequence problem. Journal of the ACM, 24, pp. 664-675, 1977.
• [9] Hunt J.W., Szymanski T.G.: A fast algorithm for computing longest common subsequences. Communications of the ACM 20(5), (1977), pp. 350-353.
• [10] Navarro G.: A Guided Tour to Approximate String Matching. ACM Computing Surveys,33(1), pp. 31-88, 2001.
• [11] Peng Ch.-L.: An Approach for Solving the Constrained Longest Common Subsequence Problem. Master’s 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
• [12] Tsai Y.-T.: The constrained common subsequence problem. Information Processing Letters, 88, pp. 173-176, 2003.
• [13] Tank C.Y., Lu C.L., ChangM.D.-T., Tsai Y.-T., Sun Y.-J., Chao K.-M., Chang J.-M., Chiou Y.-H., Wu C.-M., Chang H.-T., ChouW.-I.: Constrained multiple sequence alignment tool development and its application to RNase family alignment. In Proceedings of the first IEEE Computer Society Bioinformatics Conference (CSB 2002), pp. 127-137, 2002.