Implementação e Avaliação de Desempenho do LCS Paralelo em Cluster Multicore

Encontrar a maior subsequência comum (LCS) entre duas sequências é uma técnica muito utilizada para o alinhamento de sequências de DNA. Através da programação dinâmica se consegue a solução exata para o LCS, com complexidade de tempo e espaço O(m x n), onde m e n são os tamanhos das sequências. Algoritmos paralelos são fundamentais, tanto pelo tempo de processamento, quanto pela quantidade de memória necessária para processar sequências grandes. Logo, o objetivo deste trabalho é implementar e avaliar quatro versões paralelas do LCS para máquinas com memória distribuída, otimizando o paralelismo entre nós e também dentro de cada nó e buscando uso homogêneo de memória nos nós de processamento.