Comparação Paralela Exata de Seqüências Biológicas Longas com Uso Limitado de Memória

AUTOR(ES)
DATA DE PUBLICAÇÃO

2006

RESUMO

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.

ASSUNTO(S)

sequence alignment parallel programming bioinformática ciencia da computacao programação paralela bioinformatics alinhamento de seqüências

ACESSO AO ARTIGO

Documentos Relacionados