Proposta de Implementação do Algoritmo Smith-Waterman em FPGA
Smith-Waterman, FPGA, Hardware, Array Sistólico
Em bioinformática, o alinhamento é uma técnica essencial para encontrar semelhanças entre sequências biológicas. Normalmente, o alinhamento é realizado com o algoritmo Smith-Waterman (SW), uma conhecida técnica de alinhamento de sequências de alta precisão baseada em programação dinâmica. No entanto, dado o grande volume de dados em bancos de dados biológicos e seu aumento exponencial contínuo, o processamento de dados em alta velocidade é necessário. Portanto, este trabalho propõe um projeto de hardware paralelo para o algoritmo SW com uma estrutura de array sistólico para acelerar as etapas de Forward e Backtracking. Para tanto, a arquitetura calcula e armazena os caminhos no estágio Forward para pré-organizar o alinhamento, o que reduz a complexidade do estágio Backtracking. O Backtracking começa a partir da posição de pontuação máxima na matriz e gera o caminho de alinhamento de sequência SW ideal. A arquitetura foi validada em Field-Programmable Gate Array (FPGA), e análises de síntese mostraram que o projeto proposto atinge até 79,5 Giga Cell Updates por Segundo (GCPUS).