Arquiteturas em hardware para o alinhamento local de sequências biológicas

• Ano de defesa: 2010
• Autor(a) principal: Mallmann, Rafael Mendes
• Orientador(a): Wirth, Gilson Inacio
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Palavras-chave em Português: Microeletrônica; Aplicação dos computadores
• Palavras-chave em Inglês: DNA sequence scanning; Smith-Waterman; Edit distanve; Levenshtein distance; Dynamic programming; Systolic array; FPGA; ASIC; VLSI; Protein sequences; Query sequence; Subject sequence
• Link de acesso: http://hdl.handle.net/10183/56841

Bancos de dados biológicos utilizados para comparação e alinhamento local de sequências tem crescido de forma exponencial. Isso popularizou programas que realizam buscas nesses bancos. As implementações dos algoritmos de alinhamento de sequências Smith- Waterman e distância Levenshtein demonstraram ser computacionalmente intensivas e, portanto, propícias para aceleração em hardware. Este trabalho descreve arquiteturas em hardware dedicado prototipadas para FPGA e ASIC para acelerar os algoritmos Smith- Waterman e distância Levenshtein mantendo os mesmos resultados obtidos por softwares. Descrevemos uma nova e eficiente unidade de processamento para o cálculo do Smith- Waterman utilizando affine gap. Também projetamos uma arquitetura que permite particionar as sequências de entrada para a distância Levenshtein em um array sistólico de tamanho fixo. Nossa implementação em FPGA para o Smith-Waterman acelera de 275 a 494 vezes o algoritmo em relação a um computador com processador de propósito geral. Ainda é 52 a 113% mais rápida em relação, segundo nosso conhecimento, as mais rápidas arquiteturas recentemente publicadas.