FPGA architectures for biological sequence comparison in linear space / Arquiteturas em FPGA para comparação de sequências em espaço linear

AUTOR(ES)

Jan Mendonça Corrêa

DATA DE PUBLICAÇÃO

2008

RESUMO

The alignment of biological sequences is one of the more basic operations in bioinformatics. Its purpose is to find the similarity between sequences. The solution to this problem generally involves sequence comparison through dynamic programming. This kind of comparison yields optimal results but has quadratic time complexity thus justifying its hardware acceleration in FPGA. In this thesis, linear space wavefront architectures were designed in FPGA for three different algorithms. The first algorithm was Smith-Waterman. It was implemented in a wavefront array and utilized to accelerate the initial phase of a sequence alignment algorithm. This architecture was able to retrieve the largest score and its position in linear space. It was synthesized in FPGA and the best result was 246,9 times faster than software, showing the appropriateness of the architecture. Also, an architecture to retrieve the optimal DIALIGN score in linear space was designed. The results were up to 383,41 times better than software. The retrieval of the optimal alignment for DIALIGN needs quadratic space. Therefore, a variant for the DIALIGN dynamic programming algorithm was proposed to retrieve the alignment in linear space. This variant was implemented in hardware and the results were up to 141,38 times faster than the software implementation.

ASSUNTO(S)

engenharia eletrica comparação de seqüências bioinformática fpga

Documentos Relacionados

• Exploração do espaço de projeto de arquiteturas reconfiguráveis em arranjos
• Paralelização automática de laços para arquiteturas multicore
• Plataforma de serviços de infra-estrutura para arquiteturas de mobilidade
• Exploração do paralelismo em arquiteturas para processamento de imagens e vídeo
• Simulação compilada para arquiteturas descritivas em ArchC