Algoritmo Linear para Detecção de Unidades de Repetição em Tandem Arrays
Resumo
A detecção de repetições é relevante em diversas áreas, como em genética, compressão de dados e processamento de texto. Neste artigo é abordada uma solução para o problema de identificar a menor sequência repetida em uma string. Tandem arrays são um grupo especial de string formadas pelas repetições de strings menores não-vazias. O algoritmo analisado neste artigo tem enfoque na detecção da menor unidade de repetição de um tandem array em tempo linear, em relação ao tamanho da string de entrada. Também é feito uma validação da funcionalidade do algoritmo.
Palavras-chave:
Avaliação, Medição e Predição de Desempenho, Ciência de Dados e Computação de Alto Desempenho
Referências
Aho, A. V. (1990). Chapter 5 - algorithms for finding patterns in strings. In Van Leeuwen, J., editor, Algorithms and Complexity, Handbook of Theoretical Computer Science, pages 255–300. Elsevier, Amsterdam.
C. S. Góes, A. (2005). Análise de regiões polimórficas do DNA com o objetivo de estabelecer vínculos genéticos, identificar restos mortais ou realizar perícias criminais. Revista do Biomedico, 65:22–23.
Knuth, D. E., Morris, Jr., J. H., and Pratt, V. R. (1977). Fast pattern matching in strings. SIAM Journal on Computing, 6(2):323–350.
Mala, F. and Ali, R. (2022). The big-O of mathematics and computer science. Journal of Applied Mathematics and Computation, 6:1–3.
Nakamura, A., Saito, T., Takigawa, I., Kudo, M., and Mamitsuka, H. (2013). Fast algorithms for finding a minimum repetition representation of strings and trees. Discrete Applied Mathematics, 161(10):1556–1575.
Peterson, L. L. and Davie, B. S. (2022). 7 - end-to-end data. In Peterson, L. L. and Davie, B. S., editors, Computer Networks (Sixth Edition), The Morgan Kaufmann Series in Networking, pages 554–605. Morgan Kaufmann, 6th edition edition.
Sokol, D., Benson, G., and Tojeira, J. (2007). Tandem repeats over the edit distance. Bioinformatics, 23(2):e30–e35.
C. S. Góes, A. (2005). Análise de regiões polimórficas do DNA com o objetivo de estabelecer vínculos genéticos, identificar restos mortais ou realizar perícias criminais. Revista do Biomedico, 65:22–23.
Knuth, D. E., Morris, Jr., J. H., and Pratt, V. R. (1977). Fast pattern matching in strings. SIAM Journal on Computing, 6(2):323–350.
Mala, F. and Ali, R. (2022). The big-O of mathematics and computer science. Journal of Applied Mathematics and Computation, 6:1–3.
Nakamura, A., Saito, T., Takigawa, I., Kudo, M., and Mamitsuka, H. (2013). Fast algorithms for finding a minimum repetition representation of strings and trees. Discrete Applied Mathematics, 161(10):1556–1575.
Peterson, L. L. and Davie, B. S. (2022). 7 - end-to-end data. In Peterson, L. L. and Davie, B. S., editors, Computer Networks (Sixth Edition), The Morgan Kaufmann Series in Networking, pages 554–605. Morgan Kaufmann, 6th edition edition.
Sokol, D., Benson, G., and Tojeira, J. (2007). Tandem repeats over the edit distance. Bioinformatics, 23(2):e30–e35.
Publicado
23/04/2025
Como Citar
LAGO, Luiz H. B.; RIGHI, Bruna da Silva.
Algoritmo Linear para Detecção de Unidades de Repetição em Tandem Arrays. In: ESCOLA REGIONAL DE ALTO DESEMPENHO DA REGIÃO SUL (ERAD-RS), 25. , 2025, Foz do Iguaçu/PR.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2025
.
p. 9-12.
ISSN 2595-4164.
DOI: https://doi.org/10.5753/eradrs.2025.6665.
