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

Monografia (graduação)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2016.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.Multiple Sequence Alignment (MSA) is a common operation in Bioinformatics, executed tens of thousands of times daily all over the world. Many parallel strategies were proposed for accelerating the production of results of the Multiple Sequence Alignment (MSA) with A*, amongst them the Parallel A* (PA*) which, despite obtaining results faster, demands a great amount of memory, becoming unfeasible for some MSA instances. This undergraduate project proposes and evaluates a strategy of data movement between memory and disk for the Parallel A*, in order to allow the solution of MSA instances which demand more memory than the available on the execution environment. Experimental results obtained in 2 test environments have showed that the strategy allowed the solution of MSA instances that could not be completed on the environments used due to the excessive use of memory. This was achieved, however, with a considerable increment on the execution time