Utilize este link para identificar ou citar este item: http://bdm.unb.br/handle/10483/17768
Arquivos neste item:
Arquivo Descrição TamanhoFormato 
2017_AndressaSousaDaSilveira_tcc.pdf3,84 MBAdobe PDFver/abrir
Título: Comparação de sequências biológicas longas em FPGA usando particionamento
Autor(es): Silveira, Andressa Sousa da
Orientador(es): Melo, Alba Cristina Magalhães Alves de
Assunto: Bioinformática
FPGAs (Field Programmable Gate Arrays)
Data de apresentação: 3-Fev-2017
Data de publicação: 8-Ago-2017
Referência: SILVEIRA, Andressa Sousa da. Comparação de sequências biológicas longas em FPGA usando particionamento. 2017. xii, 50 f., il. Trabalho de conclusão de curso (Bacharelado em Engenharia da Computação)—Universidade de Brasília, Brasília, 2017.
Resumo: 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).
Abstract: An important operation in Bioinformatics is the biological sequence comparison, which has as result the best score that determines how similar are two sequences. The best score is obtained with the computation of the dynamic programming matrix by exact algorithms, whose complexities are O(mn), where m and n are the size of the sequences. Solutions in FPGA for biological sequence comparison reached great performances, however these solutions require a few thousand characters of the sequences being compared at a time, in other words, the comparison must be partitioned. The objective of this graduation work is to propose, implement and evaluate a solution in FPGA for the biological sequence comparison with partitioning. Two partitioning circuits (v.1 and v.2) were proposed, where circuit v.1 receives the intermediate column, row and diagonal from the dynamic programming matrix, computes a part of the matrix and produces the score. In the same way, the circuit v.2 receives the intermediate column, row and diagonal from the dynamic programming matrix, computes a part of the matrix and produces the score, last column, row and diagonal of the computed partition of the matrix. The experimental results show a great occupation of the FPGA with processing elements. Besides, the execution of the partitioning circuit v.1 in the XtremeData XD2000iTM for the biological sequence comparison with both sequences having 20 characters present very satisfactory times (up to 948μs).
Informações adicionais: Trabalho de conclusão de curso (graduação)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2017.
Aparece na Coleção:Engenharia da Computação



Este item está licenciado na Licença Creative Commons Creative Commons