| Título: | Alinhamento paralelo de sequências biológicas com poda agilizada em GPU |
| Autor(es): | Pinho, Matheus Augusto Silva |
| Orientador(es): | Melo, Alba Cristina Magalhães Alves de |
| Assunto: | Sequência biológica
Unidades de Processamento Gráfico (GPUs)
Poda (Computação)
Bioinformática |
| Data de apresentação: | 14-Fev-2023 |
| Data de publicação: | 12-Dez-2023 |
| Referência: | PINHO, Matheus Augusto Silva. Alinhamento paralelo de sequências biológicas com poda agilizada em GPU. 2023. 57 f., il. Trabalho de Conclusão de Curso (Bacharelado em Engenharia da Computação) — Universidade de Brasília, Brasília, 2023. |
| Resumo: | A comparação de sequências biológicas é uma das principais tarefas da Bioinformática, existindo uma gama de algoritmos exatos que usam programação dinâmica para este fim. Estes algoritmos apresentam complexidade quadrática no tempo O(n2) e, dependendo do tamanho das sequências, podem consumir muito tempo de execução. Para amenizar este problema, foram propostas ferramentas paralelas. Este trabalho de graduação propõe e avalia o Módulo de Alinhamento com Poda Agilizada (APA) que, integrado à ferramenta
paralela MASA-CUDAlign para uma GPU, modifica a otimização de descarte de blocos (Block Pruning), buscando agilizar a poda e aumentar área de descarte da matriz de programação dinâmica. Com esse fim, optou-se por utilizar o alinhador heurístico BLAST para a geração de um escore inicial a ser inserido automaticamente no MASA-CUDAlign, que originalmente iniciava o processamento com escore zero. Para os testes, foram utilizados pares de sequências de DNA de tamanho 3M, 5M, 7M, 10M, 23M e 40M. Os resultados obtidos evidenciam uma melhora no desempenho para comparações de sequências grandes
e semelhantes. |
| Abstract: | The comparison of biological sequences is one of the main tasks in Bioinformatics. There is a range of exact algorithms that use dynamic programming for this purpose. These algorithms have quadratic complexity in time O(n2) and can take a lot of execu tion time depending on the size of the sequences. To alleviate this problem, parallel tools have been proposed. This Undergraduate Project presents the Quick Pruning Alignment Module, which integrated to the one GPU MASA-CUDAlign parallel tool, modifies the Block Pruning optimization strategy, seeking to speed up pruning and increase the the dy namic programming matrix’s discart area. For this purpose, the heuristic aligner BLAST is used to generate an initial score to be automatically inserted into MASA-CUDAlign, which originally started computing with a score of 0. For tests, pairs of 3M, 5M, 7M,
10M, 23M and 40M DNA sequences were used. The results show an improvement in performance for comparisons of large and similar sequence. |
| Informações adicionais: | Trabalho de Conclusão de Curso (graduação) — Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2023. |
| Licença: | A concessão da licença deste item refere-se ao termo de autorização impresso assinado pelo autor que autoriza a Biblioteca Digital da Produção Intelectual Discente da Universidade de Brasília (BDM) a disponibilizar o trabalho de conclusão de curso por meio do sítio bdm.unb.br, com as seguintes condições: disponível sob Licença Creative Commons 4.0 International, que permite copiar, distribuir e transmitir o trabalho, desde que seja citado o autor e licenciante. Não permite o uso para fins comerciais nem a adaptação desta. |
| Aparece na Coleção: | Engenharia da Computação
|
Todos os itens na BDM estão protegidos por copyright. Todos os direitos reservados.
