BDBComp
Parceria:
SBC
Alinhamento de Sequencias de DNA em Aglomerados de Computadores

Daniela Saccol PeranconiGerson G. H. Cavalheiro

O algoritmo de Smith-Waterman [SMI 81], baseado em programac¸~ao din^amica,´e considerado o mais sensitivo para alinhamento de seq¨u^encias biol´ogicas (DNA ouprote´?nas), apresentando os melhores resultados. No entanto, as grandes necessidadescomputacionais deste algoritmo, no que se refere a utilizac¸~ao de mem´oria e tempo deprocessamento, limitam sua utilizac¸~ao. O algoritmo manipula uma matriz de dados, detamanho (n+1) (m+1), onde cada c´elula cont´em a similaridade entre um elemento deuma seq¨u^encia X, de tamanho n, e um elemento de uma seq¨u^encia Y, de tamanho m. Amatriz ´e preenchida de cima para baixo e da esquerda para a direita, em um processode inundac¸~ao, com o elemento (i, j) necessitando de tr^es valores previamente calculados:(i-1, j), (i-1, j-1) e (i, j-1).Para a obtenc¸~ao de uma implementac¸~ao concorrente eficiente para este algoritmo,´e necess´ario considerar as depend^encias de dados do m´etodo de programac¸~ao din^amica.Al´em disso, ´e preciso definir a granularidade adequada ao problema, de forma a evitarum n´umero muito grande de tarefas concorrentes para que o custo necess´ario `assincronizac¸ ~oes entre elas n~ao sobreponha o potencial ganho de uma execuc¸~ao paralela.Uma soluc¸~ao ao problema de granularidade ´e dividir a matriz de similaridades em blocosretangulares de elementos, aumentando a granularidade do c´alculo e diminuindo on´umero de tarefas criadas [MAR 01].

http://www.lbd.dcc.ufmg.br/colecoes/erad-rs/2005/0015.pdf

Caso o link acima esteja inválido, faça uma busca pelo texto completo na Web: Buscar na Web

Biblioteca Digital Brasileira de Computação - Contato: bdbcomp@lbd.dcc.ufmg.br
     Mantida por:
LBD