Submitted by Alice Araujo (alice.caraujo@ufpe.br) on 2018-05-02T22:57:02Z
No. of bitstreams: 1
TESE Antonyus Pyetro do Amaral Ferreira.pdf: 4460667 bytes, checksum: 221231feaf54c8b316330bd4925f36e7 (MD5) / Made available in DSpace on 2018-05-02T22:57:02Z (GMT). No. of bitstreams: 1
TESE Antonyus Pyetro do Amaral Ferreira.pdf: 4460667 bytes, checksum: 221231feaf54c8b316330bd4925f36e7 (MD5)
Previous issue date: 2016-06-16 / CNPQ / A comparação de cadeias de DNA é um problema clássico em biologia molecular. Uma aplicação forense dessas comparações é usada no problema de identificação pessoal. Por exemplo, nos EUA, o sistema CODIS dispõe, hoje em dia, de 14,5 milhões de perfis de DNA armazenados em seu banco de dados. Visando acelerar essa recorrente tarefa da consulta em banco de dados similares ao CODIS, este trabalho apresenta implementações em software e em hardware digital do algoritmo de Needleman-Wunsch, que representa uma técnica global ótima para se medir a similaridade entre cadeias de DNA. Implementações em Multi-Threads, SIMD (Single Instruction Multiple Data) e OpenCL são investigadas para a plataforma dos GPPs (General Purpose Processors). A infraestrutura de OpenCL também foi usada para analisar o desempenho das GPUs (Graphics Processing Units) para essa tarefa. Adicionalmente, uma arquitetura de hardware digital customizada explorou o paralelismo dos FPGAs (Field Programmable Gate Arrays), buscando-se otimizar o uso dos recursos de hardware e a banda de memória. Os experimentos foram conduzidos usando um banco de DNA sintético com 8 milhões de indivíduos, em que cada um deles é representado por 15 sequências do tamanho de 240 nucleotídeos. Nesse caso de uso, a implementação em um único FPGA Stratix IV, rodando a 280MHz atingiu o maior speed-up de 1885x, em comparação com a implementação canônica em software. Como resultados secundários, as versões em OpenCL (GPU e GPP) e a versão SIMD obtiveram menores tempos de execução comparados com os softwares SWIPE e FASTA que são amplamente utilizados na área. / The comparison of DNA sequences is a classic problem in molecular biology. A forensic application of this comparison is used in the personal identification problem. For instance, in the USA, the CODIS system has today 14.5 million DNA profiles stored on its database. In order to accelerate the recurrent task to query into similar databases, this work presents implementations in software and hardware of the Needleman-Wunsch algorithm, that represents an optimal global technique for measuring similarity between DNA sequences. Multi-threaded, SIMD (Single Instruction Multiple Data), and OpenCL implementations were investigated in a GPP (General Purpose Processor) platform. The OpenCL infrastructure was also used to analyze the performance of GPUs (Graphics Processing Units) for this task. Additionally, a customized digital hardware architecture explored the parallelism of the FPGAs (Field Programmable Gate Arrays), optimizing the use of hardware resources and memory bandwidth. The experiments were conducted using a synthetic DNA database with 8 million individuals, in which, each of them are represented as 15 sequences with length of 240 nucleotides. In this case study the implementation in a single Stratix IV FPGA, running at 280MHz achieved the highest speed-up of 1885x, in comparison with the canonic software implementation. As collateral results, the OpenCL (GPU and CPU) and SIMD versions outperformed consolidated software implementations like SWIPE and FASTA.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.ufpe.br:123456789/24530 |
| Date | 16 June 2016 |
| Creators | FERREIRA, Antonyus Pyetro do Amaral |
| Contributors | http://lattes.cnpq.br/4235825596747458, LIMA, Manoel Eusebio de |
| Publisher | Universidade Federal de Pernambuco, Programa de Pos Graduacao em Ciencia da Computacao, UFPE, Brasil |
| Source Sets | IBICT Brazilian ETDs |
| Language | Breton |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Source | reponame:Repositório Institucional da UFPE, instname:Universidade Federal de Pernambuco, instacron:UFPE |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0019 seconds