Comparação de sequências biológicas utilizando computação heterogênea com OpenCL

Monografia (graduação)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2013.O alinhamento de sequências possui uma diversidade de aplicações na bioinformática, sendo uma das mais importantes operações nessa área. Dentre os métodos de alinhamento temos os algoritmo de Smith-Waterman, que é um método baseado em programação dinâmica e que provê o melhor alinhamento entre duas sequências. Apesar de ser um método exato, ele é demorado devido a sua complexidade quadrática. Para tentar reduzir esse tempo de execução desse método várias propostas foram feitas, dentre elas temos o uso de computação heterogênea. Computação heterogênea é o termo utilizado quando o ambiente computacional é composto de diferentes tipos de elementos de processamento. O objetivo do presente Trabalho de Graduação é propor uma implementação do algoritmo de Smith-Waterman em OpenCL e testar sua utilização em CPU e GPU de forma a veri car a simplicidade de programação para múltiplos elementos de processamento e analisar possíveis ganhos em tempo de execução. _____________________________________________________________________________ ABSTRACTThe sequence alignment has a wide range of applications in bioinformatics, one of the most important operations in that area. Among alignment methods there is the Smith- Waterman algorithm, which is a method based on dynamic programming that provides the best alignment between two sequences. Although it is an exact method, it is time consuming due to its quadratic complexity. There are several proposals to try to reduce the execution period of this method, one of them is the use of heterogeneous computing. Heterogeneous computing is the strategy of deploying multiple types of processing elements within a single work ow, and allowing each to perform the tasks to which it is best suited. The goal of this work is to propose an implementation of Smith-Waterman algorithm in OpenCL and test its use in CPU and GPU in order to verify the simplicity of programming to multiple processing elements and possible gains in runtime