Desenvolvimento de hardware reconfigurável dedicado para suporte ao alinhamento de seqüencias

AUTOR(ES)
DATA DE PUBLICAÇÃO

2007

RESUMO

Encontrar e visualizar semelhanças entre seqüências de DNA permite aprofundar o conhecimento sobre genomas de organismos em Biologia Molecular. Com o número de seqüências disponíveis para consulta em alguns bancos de dados crescendo exponencialmente, surge um desafio para a ciência da computação. É o de construir sistemas de informática com desempenho suficiente para permitir comparar seqüências genômicas em tempo hábil para a pesquisa e com um custo viável. Freqüentemente são usadas soluções heurísticas, devido ao grande tempo computacional necessário para o uso de soluções exatas. Soluções exatas atualmente apresentam complexidade de tempo quadrática em computadores convencionais, dificultando seu uso prático para seqüências de comprimento como as de aplicações reais. O principal objetivo deste trabalho é viabilizar o uso de algoritmos exatos para comparação de seqüências genômicas, acelerando a obtenção de seus resultados. É proposto um arranjo sistólico de elementos de processamento em hardware reconfigurável. Assim, é explorado o paralelismo potencial do algoritmo de programação dinâmica de Smith-Waterman, reduzindo sua complexidade de tempo de quadrática para linear. É proposta uma solução para minimizar o problema de gargalo de comunicação, esperado por uma implementação "ingênua" da solução. Além do sistema proposto, a prototipação realizada em FPGA é descrita, incluindo uma análise do desempenho obtido.

ASSUNTO(S)

comparação de sequências programação dinâmica sequence comparison fpga hardware alinhamento de sequências arquiteturas sistólicas arquiteturas reconfiguráveis sequence alignment smith-waterman dynamic programming

ACESSO AO ARTIGO

Documentos Relacionados