Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, Programa de Pós-Graducação em Informática, 2016. / Submitted by Fernanda Percia França (fernandafranca@bce.unb.br) on 2016-05-06T16:17:35Z No. of bitstreams: 1 2016_GabrielHelenoGonçalvesdaSilva.pdf: 2295730 bytes, checksum: c2d410a25e9d24795e425e4c29970712 (MD5) / Rejected by Raquel Viana(raquelviana@bce.unb.br), reason: A pedido do cliente. on 2016-05-12T17:27:55Z (GMT) / Submitted by Fernanda Percia França (fernandafranca@bce.unb.br) on 2016-05-12T17:33:17Z No. of bitstreams: 1 2016_GabrielHelenoGonçalvesdaSilva.pdf: 2295730 bytes, checksum: c2d410a25e9d24795e425e4c29970712 (MD5) / Approved for entry into archive by Raquel Viana(raquelviana@bce.unb.br) on 2016-05-16T17:20:02Z (GMT) No. of bitstreams: 1 2016_GabrielHelenoGonçalvesdaSilva.pdf: 2295730 bytes, checksum: c2d410a25e9d24795e425e4c29970712 (MD5) / Made available in DSpace on 2016-05-16T17:20:02Z (GMT). No. of bitstreams: 1 2016_GabrielHelenoGonçalvesdaSilva.pdf: 2295730 bytes, checksum: c2d410a25e9d24795e425e4c29970712 (MD5) / A comparação de sequências biológicas é uma operação importante na Bioinformática, que é realizada frequentemente. Os algoritmos exatos para comparação de sequências obtêm o resultado ótimo calculando uma ou mais matrizes de programação dinâmica.Estes algoritmos têm complexidade de tempo O(mn), onde m e n são os tamanhos das sequências. Fickettpropôs um algoritmo que é capaz de reduzir a complexidade paraO(kn), onde k é a faixa decomputação e representa a quantidade de diagonais da matrizefetivamente calculadas. Nessa dissertação de mestrado, propomos e avaliamos oFickett-CUDAlign, uma estratégia paralela que divide a comparação de sequências emmúltiplas comparações de subsequências e calcula uma faixa de Fickett apropriada paracada comparação de sequência (bloco). Com estaabordagem, nós reduzimos potencialmenteo número de células calculadas, quando comparada ao Fickett, que usa uma únicafaixa para toda a comparação. Nossa estratégia multi-bloco ajustável foi programada emC/C++ e pthreadse foi integrada ao estágio 4 do CUDAlign, uma ferramenta do estadoda arte para comparações ótimas de sequências biológicas. O Fickett-CUDAlign foi usadopara comparar sequências reais de DNA cujo tamanho variou de 10KBP (Milhares dePares de Base) a 47MBP (Milhões de Pares de Base),alcançando um speedup de 59,60xna comparação 10MBP x 10MBP, quando comparado aoestágio 4 do CUDAlign. Nestecaso, o tempo de execução foi reduzido de 53,56 segundos para 0,90 segundo. ________________________________________________________________________________________________ ABSTRACT / Biological sequence comparison is an important task in Bioinformatics, which is frequently performed. The exact algorithms for sequence comparison obtain the optimal result by calculating one or more dynamic programming matrices. These algorithms have O(mn) time complexity, where m and n are the sizes of the sequences. Fickett proposed an algorithm which is able to reduce time complexity to O(kn), where k is the computation band and represents the amount of matrix diagonals actually calculated. In this MSc Dissertation, we propose and evaluate Fickett-CUDAlign, a parallel strategy that splits a pairwise sequence comparison in multiple comparisons of subsequences and calculates an appropriate Fickett band to each subsequence comparison (block). With this approach, we potentially reduce the number of cells calculated, when compared to Fickett, which uses a unique band to the whole comparison. Our adjustable multi-block strategy was programmed in C/C++ and pthreads and was integrated to the stage 4 of CUDAlign, a state-of-the-art tool for optimal biological sequence comparison. Fickett-CUDAlign was used to compare real DNA sequences whose sizes ranged from 10KBP (Thousands of Base Pairs) to 47MBP (Millions of Base Pairs), reaching a speedup of 59.60x in the 10MBP x 10MBP comparison, when compared to CUDAlign’s stage 4. In this case, the execution time was reduced from 53.56 seconds to 0.90 second.