Tese (doutorado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2015. / Submitted by Albânia Cézar de Melo (albania@bce.unb.br) on 2016-01-21T13:09:08Z No. of bitstreams: 1 2015_EdansFlaviusOliveiraSandes.pdf: 8651626 bytes, checksum: eb6970a8085ba3a4dc141481620451c6 (MD5) / Approved for entry into archive by Patrícia Nunes da Silva(patricia@bce.unb.br) on 2016-05-15T13:57:40Z (GMT) No. of bitstreams: 1 2015_EdansFlaviusOliveiraSandes.pdf: 8651626 bytes, checksum: eb6970a8085ba3a4dc141481620451c6 (MD5) / Made available in DSpace on 2016-05-15T13:57:40Z (GMT). No. of bitstreams: 1 2015_EdansFlaviusOliveiraSandes.pdf: 8651626 bytes, checksum: eb6970a8085ba3a4dc141481620451c6 (MD5) / O alinhamento de sequências biológicas é uma das operações mais importantes em Bioinformática, sendo executado milhares de vezes a cada dia ao redor do mundo. Os algoritmos exatos existentes para este fim possuem complexidade quadrática de tempo. Logo, quando a comparação é realizada com sequências muito longas, tais como no escopo do genoma humano, matrizes na ordem de petabytes devem ser calculadas, algo considerado inviável pela maioria dos pesquisadores. O principal objetivo desta tese de Doutorado é propor e avaliar algoritmos e otimizações que permitam que o alinhamento ótimo de sequências muito longas de DNA seja obtido em tempo reduzido em plataformas de alto desempenho. Os algoritmos propostos utilizam técnicas paralelas de dividir e conquistar com complexidade de memória reduzida mantendo a complexidade quadrática do tempo de execução. O CUDAlign, em suas versões 2.0, 2.1, 3.0 e 4.0, é a principal contribuição desta tese, onde os algoritmos propostos estão integrados na mesma ferramenta, permitindo a recuperação eficiente do alinhamento ótimo entre duas sequências longas de DNA em múltiplas GPUs (Graphics Processing Unit) da NVIDIA. As otimizações propostas neste trabalho permitem que o nível máximo de paralelismo seja mantido durante quase todo o processamento. No cálculo do alinhamento em uma GPU, as otimizações Orthogonal Execution, Balanced Partition e Block Pruning foram propostas, aumentando o desempenho no cálculo da matriz e descartando áreas que não contribuem para o alinhamento ótimo. A análise formal do Block Pruning mostra que sua eficácia depende de vários fatores, tais como a similaridade entre as sequências e a forma de processamento da matriz. No cálculo do alinhamento com várias GPUs, a otimização Incremental Speculative Traceback é proposta para acelerar a obtenção do alinhamento utilizando valores especulados com alta taxa de acerto. Também são propostos métodos de balanceamento dinâmico de carga que se mostraram eficientes em ambientes simulados. A arquitetura de software chamada de Multi-Platform Architecture for Sequence Aligners (MASA) foi proposta para facilitar a portabilidade do CUDAlign para diferentes plataformas de hardware ou software. Com esta arquitetura, foi possível portar o CUDAlign para plataformas de hardware como CPUs e Intel Phi e utilizando plataformas de software como OpenMP e OmpSs. Nesta tese, sequências reais são utilizadas para validar a eficácia dos algoritmos e otimizações nas várias arquiteturas suportadas. Por meio do desempenho das ferramentas implementadas, avançou-se o estado da arte para permitir o alinhamento, em tempo viável, de todos os cromossomos homólogos do homem e do chimpanzé, utilizando algoritmos exatos de comparação de sequências com um desempenho de até 10,35 TCUPS (Trilhões de Células Atualizadas por Segundo). Até onde sabemos, esta foi a primeira vez que tal tipo de comparação foi realizada com métodos exatos. / Biological sequence alignment is one of the most important operations in Bioinformatics, executing thousands of times every day around the world. The exact algorithms for this purpose have quadratic time complexity. So when the comparison involves very long sequences, such as in the human genome, matrices with petabytes must be calculated, and this is still considered unfeasible by most researchers. The main objective of this Thesis is to propose and evaluate algorithms and optimizations that produce the optimal alignment of very long DNA sequences in a short time using high-performance computing platforms. The proposed algorithms use parallel divide-and-conquer techniques with reduced memory complexity, whilst with quadratic time complexity. CUDAlign, in its versions 2.0, 2.1, 3.0 and 4.0, is the main contribution of this Thesis. The proposed algorithms are integrated into the same tool, allowing efficient retrieval of the optimal alignment between two long DNA sequences using multiple GPUs (Graphics Processing Unit) from NVIDIA. The proposed optimizations maintain the maximum parallelism during most of the processing time. To accelerate the matrix calculation in a single GPU, the Orthogonal Execution, Balanced Partition and Block Pruning optimizations were proposed, increasing the performance of the matrix computation and discarding areas that do not contribute to the optimal alignment. The formal analysis of Block Pruning shows that its effectiveness depends on factors such as the sequences similarity and the matrix processing order. During the alignment computation with multiple GPUs, the Incremental Speculative Traceback optimization is proposed to accelerate the alignment retrieval, using speculated values with high accuracy rate. A dynamic load balancing method has also been proposed and its effectiveness has been shown in simulated environments. Finally, the software architecture called Multi-Platform Architecture for Sequence aligners (MASA) was proposed to simplify the portability of CUDAlign to different hardware and software platforms. With this architecture, it was possible to port CUDAlign to hardware platforms such as CPU and Intel Phi, and using software platforms such as OpenMP and OmpSs. In this Thesis, real sequences are used to validate the effectiveness of the proposed algorithms and optimizations in several supported architectures. Our proposed tools were able to advance the state-of-the-art of sequence alignment algorithms, allowing a fast retrieval of all human and chimpanzee homologous chromosomes, using exact algorithms at an unprecedented rate of up to 10.35 TCUPS (Trillions of Cells Updated Per Second). As far as we know, this was the first time that this type of comparison was carried out with exact sequence comparison algorithms.

Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2007. / Submitted by Rosane Cossich Furtado (rosanecossich@gmail.com) on 2010-01-04T21:40:52Z No. of bitstreams: 1 2007_FabioViniciusPintoSilva.pdf: 1375531 bytes, checksum: 2272e318dce7e1284d2d2eb04367db52 (MD5) / Approved for entry into archive by Carolina Campos(carolinacamposmaia@gmail.com) on 2010-01-05T17:08:01Z (GMT) No. of bitstreams: 1 2007_FabioViniciusPintoSilva.pdf: 1375531 bytes, checksum: 2272e318dce7e1284d2d2eb04367db52 (MD5) / Made available in DSpace on 2010-01-05T17:08:01Z (GMT). No. of bitstreams: 1 2007_FabioViniciusPintoSilva.pdf: 1375531 bytes, checksum: 2272e318dce7e1284d2d2eb04367db52 (MD5) Previous issue date: 2007-09-17 / 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. _______________________________________________________________________________ ABSTRACT / To find and to visualize similarities between DNA sequences allow to deepen the knowledgement on genomas of organisms in Molecular Biology. With the number of available sequences for consultation in some data bases growing exponentially , a challenge for the computer science appears. It is to construct computing systems with enough performance to allow to compare genomics sequences in skillful time for the research and at a viable cost. Frequently heuristical solutions are used, due to the great computational time necessary to the use of exact solutions. Exact solutions currently presents quadratic time complexity in conventionals computers, making difficult its practical use for sequences of length as of real applications. The main objective of this work is to make possible the use of exact algorithms for comparison of genomics sequences, by speeding up the attainment of its results. A systolic arrangement of elements of processing in reconfigurable hardware is proposed. This way, the potential parallelism of the algorithm of dynamic programming of Smith-Waterman is explored, reducing its time complexity from quadratic to linear. Is also proposed a solution to minimize the problem of communication bottleneck, waited in a “naive” implementation. Besides the proposed system, the prototipation made in FPGA is described, including an analysis of the performance gotten.