Comparação paralela exata de seqüências biológicas longas com uso limitado de memória

Abstract

O alinhamento de seqüências biológicas é um método muito importante usado pela biologia computacional para relacionar organismos e compreender os processos evolutivos envolvidos entre eles. O algoritmo de Smith-Waterman, método exato para obtenção de alinhamentos locais ótimos entre seqüências de DNA (ácido desoxirribonucleico), possui complexidade O(n2) tanto de espaço quanto de tempo. Esta complexidade é um obstáculo à comparação de seqüências muito longas. O BLAST é uma ferramenta capaz de produzir alinhamentos locais em curto espaço de tempo e baixo custo de memória. No entanto, a sensibilidade dos resultados produzidos é baixa em comparação aos métodos exatos, devido às heurísticas utilizadas no BLAST. A programação paralela é utilizada para lidar com problemas computacionais que demandam muito tempo de processamento. Clusters de computadores provêm alto poder computacional a baixo custo. Entretanto, para se ter benefícios com o uso de clusters, os problemas precisam ser adaptados antes de serem resolvidos sobre tal plataforma computacional. A presente dissertação propõe uma estratégia paralela exata para a comparação de seqüências longas de DNA em um espaço limitado de memória. A estratégia proposta foi implementada em um cluster de estações de trabalho, atingindo speedups muito bons para seqüências maiores que 50Kbp e sendo capaz de produzir alinhamentos locais ótimos para seqüências de mais de 3 milhões de pares de bases. ____________________________________________________________________________________________ ABSTRACT

Biological sequence alignment is a very important method used by computational biology to relate organisms and understand the evolutionary processes involved between them. The Smith-Waterman algorithm, an exact method used to obtain optimal local alignments between DNA (deoxyribonucleic acid) sequences, has O(n2) space and time complexity. This complexity is an obstacle to the comparison of very long sequences. BLAST is a tool capable of producing local alignments in short time at a low memory cost. However, the results produced have a low sensibility when compared to exact methods, due to the heuristics used in BLAST. Parallel programming is used to deal with high processing time demanding computational problems. Clusters of computers provide high computational power at low cost. However, in order to have benefits with the use of clusters, the problems must be adapted before being solved on such computational platform. The present dissertation proposes an exact parallel strategy to the comparison of long DNA sequences in limited memory space. The proposed strategy was implemented in a cluster of workstations, reaching very good speedups for sequences longer than 50Kbp and being able to produce optimal local alignments for sequences with over 3 million base pairs.