Comparação Sequência-Família em GPU

Abstract

Durante as últimas décadas o volume de informações biológicas em algumas bases de dados cresceu em um ritmo quase exponencial. Ferramentas como o HMMER podem encontrar sequências biológicas homólogas a uma família de sequências modelada estatisticamente por um profile HMM utilizando o algoritmo de Viterbi. Dada a complexidade quadrática desse algoritmo, esse procedimento pode consumir longos tempos de execução dependendo da quantidade de sequências, do tamanho do profile HMM e do hardware utilizado. Esse trabalho descreve o desenvolvimento de uma solução em GPU, de alto desempenho, para o problema de determinar se uma nova sequência biológica é homóloga a uma família de sequências conhecida. A solução implementada alcançou desempenho compatível ou superior ao HMMER.

ABSTRACT - Over the past few decades the amount of biological data in some databases grew up in an almost exponential rate. Tools such as HMMER use the Viterbi algorithm to find biological sequences that are homologue to a family of sequences represented by a statistical model called profile HMM. Due to the quadratic time complexity of the Viterbi algorithm, this search procedure can demand long execution times depending on database size, profile HMM length, and hardware used. The purpose of this project is to design a high performance GPU solution for the problem of finding out if a new biological sequence is homologue to a known family of sequences. The implemented solution reached a performance compatible or superior to HMMER.