Disk-Assited Parallel A* : estratégia de movimentação de dados memória-disco para o alinhamento múltiplo ótimo de sequências

Abstract

O alinhamento múltiplo de sequências (MSA) é uma operação muito frequente em Bioinformática, sendo executada dezenas de milhares de vezes por dia em todo o mundo. Várias estratégias paralelas foram propostas para acelerar a produção de resultados do MSA com A*, dentre elas o Parallel A* que, apesar de obter resultados mais rápido, requer grande quantidade de memória, o que inviabiliza o uso desse tipo de algoritmo para conjuntos com um número razoável de sequências com padrões complexos. O presente trabalho de graduação propõe e avalia uma estratégia de movimentação de dados entre memória e disco para o Parallel A* com o intuito de permitir a solução de instâncias do MSA que exijam mais memória que o disponível no ambiente de execução. Os resultados experimentais obtidos em 2 ambientes de testes mostram que a estratégia proposta permitiu a solução de instâncias do MSA que não eram finalizadas nos ambientes de testes por uso excessivo de memória, contudo, com um incremento considerável no tempo de execução.