Comparação de sequências biológicas longas em FPGA usando particionamento

Abstract

Uma importante operação da Bioinformática é a comparação de sequências biológicas, que tem como resultado o escore ótimo determinando o grau de similaridade entre duas sequências. O escore ótimo é obtido por meio de algoritmos exatos que calculam uma matriz de programação dinâmica, possuindo complexidade quadrática O(mn), onde m e n são os tamanhos das sequências. As soluções em FPGA para a comparação de sequências biológicas atingiram altíssimo desempenho, porém essas soluções exigem que poucos milhares de caracteres das sequências sejam comparados a cada vez, ou seja, a comparação deve ser particionada. O objetivo do presente trabalho de graduação é propor, implementar e avaliar uma solução em FPGA para a comparação exata de sequências biológicas com particionamento. Foram propostos dois circuitos de particionamento (v.1 e v.2), onde o circuito v.1 recebe a coluna, linha e diagonal intermediárias da matriz de programação dinâmica, calcula uma parte da matriz e produz o escore. O circuito v.2, da mesma maneira, recebe a coluna, linha e diagonal intermediárias da matriz de programação dinâmica, calcula uma parte da matriz e produz o escore, linha, coluna e diagonal finais da partição da matriz que foi calculada. Os resultados experimentais mostram uma boa ocupação do FPGA com elementos de processamento. Além disso, a execução do circuito de particionamento v.1 na plataforma XD2000i para a comparação de sequências biológicas de 20 caracteres cada apresenta tempos bastante satisfatórios (até 948μs).