Artículo
Barenbaum, P.; Becher, V.; Deymonnaz, A.; Halsband, M.; Heiber, P.A. "Efficient repeat finding in sets of strings via suffix arrays" (2013) Discrete Mathematics and Theoretical Computer Science. 15(2):59-70
Estamos trabajando para incorporar este artículo al repositorio
Consulte la política de Acceso Abierto del editor
Abstract:
We consider two repeat finding problems relative to sets of strings: (a) Find the largest substrings that occur in every string of a given set; (b) Find the maximal repeats in a given string that occur in no string of a given set. Our solutions are based on the suffix array construction, requiring O(m) memory, where m is the length of the longest input string, and O(n log m) time, where n is the the whole input size (the sum of the length of each string in the input). The most expensive part of our algorithms is the computation of several suffix arrays. We give an implementation and experimental results that evidence the efficiency of our algorithms in practice, even for very large inputs. © 2013 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France.
Registro:
| Documento: | Artículo |
| Título: | Efficient repeat finding in sets of strings via suffix arrays |
| Autor: | Barenbaum, P.; Becher, V.; Deymonnaz, A.; Halsband, M.; Heiber, P.A. |
| Filiación: | Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Argentina CONICET Argentina, Argentina |
| Palabras clave: | Longest maximal substring; Repeats; Stringology; Suffix array; Expensive parts; Input string; Maximal repeats; Maximal substring; Repeats; Stringology; Sub-strings; Suffix arrays; Algorithms; Indexing (of information) |
| Año: | 2013 |
| Volumen: | 15 |
| Número: | 2 |
| Página de inicio: | 59 |
| Página de fin: | 70 |
| Título revista: | Discrete Mathematics and Theoretical Computer Science |
| Título revista abreviado: | Discrete Math. Theor. Comput. Sci. |
| ISSN: | 14627264 |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v15_n2_p59_Barenbaum |
Referencias:
- Abouelhoda, M.I., Kurtz, S., Ohlebusch, E., Replacing suffix trees with enhanced suffix arrays (2004) Journal of Discrete Algorithms, 2 (1), pp. 53-86
- Babenko, M., Starikovskaya, T., Computing longest common substrings via suffix arrays (2008) LNCS, 5010, p. 6475. , CSR 2008, Heidelberg. Springer-Verlag Berlin
- Becher, V., Deymonnaz, A., Heiber, P., Efficient computation of all perfect repeats in genomic sequences of up to half a gigabyte, with a case study on the human genome (2009) Bioinformatics (Oxford, England), 25 (14). , July
- Becher, V., Deymonnaz, A., Heiber, P., (2012) Efficient Repeat Finding Via Suffix Arrays, , manuscript, arXiv:1304.0528
- Gusfield, D., (1997) Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, , Cambridge University Press
- Kasai, T., Lee, G., Arimura, H., Arikawa, S., Park, K., Linear-time longest-common-prefix computation in suffix arrays and its applications (2001) Lecture Notes In Computer Science, (2089), pp. 181-192. , Combinatorial Pattern Matching
- Larsson, N.J., Sadakane, K., Faster suffix sorting (2007) Theoretical Computer Science, 387 (3), pp. 258-272. , DOI 10.1016/j.tcs.2007.07.017, PII S0304397507005257, The Burrows-Wheaker Transform
- Manber, U., Myers, G., Suffix arrays: A new method for on-line string searches (1993) SIAM Journal on Computing, 22 (5), pp. 935-948
- (1990) SODA '90: Proc. 1st Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 319-327. , San Francisco
- Simon, J., Smyth, P.W.F., Turpin, A.H., A taxonomy of suffix array construction algorithms (2007) ACM Computing Surveys, 39 (2), p. 4
Citas:
---------- APA ----------
Barenbaum, P., Becher, V., Deymonnaz, A., Halsband, M. & Heiber, P.A. (2013) . Efficient repeat finding in sets of strings via suffix arrays. Discrete Mathematics and Theoretical Computer Science, 15(2), 59-70.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v15_n2_p59_Barenbaum [ ]
---------- CHICAGO ----------
Barenbaum, P., Becher, V., Deymonnaz, A., Halsband, M., Heiber, P.A. "Efficient repeat finding in sets of strings via suffix arrays" . Discrete Mathematics and Theoretical Computer Science 15, no. 2 (2013) : 59-70.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v15_n2_p59_Barenbaum [ ]
---------- MLA ----------
Barenbaum, P., Becher, V., Deymonnaz, A., Halsband, M., Heiber, P.A. "Efficient repeat finding in sets of strings via suffix arrays" . Discrete Mathematics and Theoretical Computer Science, vol. 15, no. 2, 2013, pp. 59-70.Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v15_n2_p59_Barenbaum [ ]
---------- VANCOUVER ----------
Barenbaum, P., Becher, V., Deymonnaz, A., Halsband, M., Heiber, P.A. Efficient repeat finding in sets of strings via suffix arrays. Discrete Math. Theor. Comput. Sci. 2013;15(2):59-70.Available from: https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v15_n2_p59_Barenbaum [ ]
