Estratégias de Otimização em GPU para Análise de Sequências Biológicas

Abstract

Uma importante tarefa na área de Bioinformática é comparar uma sequência em relação a uma família de sequências e, dependendo do resultado obtido, incluir essa sequência na família em questão. HMMer [17, 18] é um conjunto de ferramentas bastante utilizado para realizar essa tarefa e aplica um algoritmo denominado algoritmo de Viterbi. Existem implementações do HMMer buscando ganhos de desempenho nas mais variadas plataformas. Entretanto, o tamanho das bases de sequências biológicas vem crescendo muito nos últimos anos, fazendo com que a comparação de sequências utilizando essas bases de dados se torne cada vez mais custosa em termos de tempo de processamento. Poucas implementações utilizam como plataforma de execução a GPU e avaliam esse dispositivo, que possui grande capacidade computacional e evoluiu muito nos últimos anos. Assim, este trabalho apresenta o desenvolvimento de soluções em GPU para o algoritmo de Viterbi aplicado à análise de sequências biológicas e avalia as maneiras mais eficientes de utilizar os recursos disponíveis nessa plataforma. O acelerador proposto alcança um ótimo desempenho, com speedup médio de 48,82 e máximo de 102,83, em relação ao HMMer2 executado em um computador convencional. O desempenho obtido também é superior ao alcançado por outros aceleradores em GPU descritos na literatura.

Comparing a biological sequence to a family of sequences and, depending on the results, including this sequence into the family is an important task in Bioinformatics. HMMer [17, 18] is a set of tools widely used to perform this task and applies an algorithm called Viterbi algorithm. There are several implementations of the Viterbi algorithm that try to achieve performance gains on several different platforms. However, the size of biological sequence databases has been growing exponentially recently, making the comparison process more computationally demanding. A GPU is a hardware device with a high capability of parallel processing that has evolved very much lately, nevertheless, just a few implementations of the Viterbi algorithm use and evaluate it for this problem. This work presents the development of solutions to the Viterbi algorithm applied to biological sequence analysis on GPUs and evaluate the most efficient ways to use their resources. The accelerator proposed achieves speedups up to 102,83 and on average 48,82, with respect to HMMer’s execution on a general purpose computer. The performance achieved is higher than the ones achieved by other accelerators described in the literature.