Faster Algorithms for Computing Maximal Multirepeats in Multiple Sequences

• Autorzy: Iliopoulos C.S. , Smyth W.F. , Yusufu M.
• Języki publikacji: EN

Abstrakty

EN

A repeat in a string is a substring that occurs more than once. A repeat is extendible if every occurrence of the repeat has an identical letter either on the left or on the right; otherwise, it is maximal. A multirepeat is a repeat that occurs at least m_min times (m_min

Słowa kluczowe

EN

maximal multirepeats; repeats; gaps; biological sequences; suffix arrays

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 97, nr 3
• Strony: 311--320
• Opis fizyczny: Bibliogr. 12 poz., tab., wykr.

Twórcy

autor

Iliopoulos C.S.

autor

Smyth W.F.

autor

Yusufu M.

• Algorithms Research Group, Department of Computing & Software, McMaster University, Hamilton, Ontario, Canada L8S 4K1,

Bibliografia

• [1] A. Bakalis, Costas S. Iliopoulos, Christos Makris, Spyros Sioutas, Evangelos Theodoridis, Athanasios K. Tsakalidis, Kostas Tsichlas: Locating maximal multirepeats in multiple strings under various constraints, The Computer Journal 50-2, 2007, 178-185.
• [2] Michael Burrows, David J. Wheeler: A Block-Sorting Lossless Data Compression Algorithm, Technical Report 124, Digital Equipment Corporation, 1994.
• [3] Johannes Fischer, Volker Heun, Stefan Kramer: Optimal string mining under frequency constraints, Proc. 10th European Conf. on Principles and Practice of Knowledge Discovery in Databases, LNCS 4213, Springer-Verlag, 2006, 139-150.
• [4] Dan Gusfield: Algorithms on Strings, Trees and Sequences, Cambridge University Press, 1997.
• [5] Juha Kärkkäinen, Peter Sanders: Simple linear work suffix array construction, Proc. 30th Internat. Colloq. Automata, Languages & Programming, LNCS 2971, Springer-Verlag, 2003, 943-955.
• [6] Toru Kasai, Gunho Lee, Hiroki Arimura, Setsuo Arikawa, Kunsoo Park: Linear-time longest-common-prefix computation in suffix arrays and its applications, Proc. 12th Annual Symp. Combinatorial Pattern Matching, LNCS 2089, Springer-Verlag, 2001, 181-192.
• [7] Pang Ko, Srinivas Aluru: Space efficient linear time construction of suffix arrays, Proc. 14th Annual Symp. Combinatorial Pattern Matching, R. Baeza-Yates, E. Chávez&M. Crochemore (eds.), LNCS 2676, Springer- Verlag, 2003, 200-210.
• [8] Sau Dan Lee, Luc De Raedt: An efficient algorithm for mining string databases under constraints, Proc. KDID, LNCS 3377, Springer-Verlag, 2005, 108-129.
• [9] Giovanni Manzini: Two space saving tricks for linear time LCP computation, Proc. 9th Scandinavian Workshop on Algorithm Theory, LNCS 3111, Springer-Verlag, 2004, 372-383.
• [10] Simon J. Puglisi, W. F. Smyth, Munina Yusufu: Fast optimal algorithms for computing all the repeats in a string, Prague Stringology Conference, Jan Holub & Jan Żd'árek (eds.), 2008, 161-169.
• [11] Simon J. Puglisi, W. F. Smyth, Andrew Turpin: A taxonomy of suffix array construction algorithms, ACM Computing Surveys 39-2, Article 4, 2007.
• [12] Bill Smyth: Computing Patterns in Strings, Pearson Addison-Wesley, 2003.