Estratégia paralela para alinhamento múltiplo de sequências com algoritmo genético multi-ilha

AUTOR(ES)

Lídia Araujo Miranda

DATA DE PUBLICAÇÃO

2009

RESUMO

O Alinhamento Múltiplo de Sequências genéticas (AMS) é executado milhares de vezes ao dia por cientistas, a fim de identificar regiões de semelhança entre três ou mais sequências. Os alinhamentos múltiplos assim obtidos são usados na resolução de problemas complexos, como a determinação do histórico evolutivo das espécies. Por se tratar de um problema NP-completo, geralmente são utilizadas soluções heurísticas para a sua resolução. Dentre soluções adotadas, destaca-se o Algoritmo Genético (AG), que é um método iterativo não-determinístico, baseado nos princípios da Evolução das Espécies de Darwin. Apesar de apresentar soluções boas para o AMS, os algoritmos genéticos demandam um alto poder de processamento, que se traduz em um alto tempo de execução. Por essa razão, algumas estratégias paralelas foram propostas na literatura para acelerar a obtenção de alinhamentos múltiplos com AGs, geralmente utilizando a estratégia da ilha como base de paralelização. A presente dissertação de mestrado propõe e avalia uma estratégia paralela que utiliza Algoritmo Genético para o Alinhamento Múltiplo de Sequências, inspirada no modelo Multi-ilha. De maneira diferente das abordagens para AMS existentes na literatura, a estratégia proposta utiliza 3 Super Ilhas, onde cada Super Ilha implementa um modelo tradicional de ilhas. Os resultados obtidos com bases reais de proteínas mostram que a estratégia proposta é capaz de encontrar alinhamentos múltiplos de melhor qualidade em menor tempo, quando comparada com a estratégia de ilha tradicional.

ASSUNTO(S)

ciencia da computacao algoritmo paralelo island injection multiple sequence alignment genetic algorithm alinhamento múltiplo de sequências algoritmo genético injeção de ilhas parallel algorithm

Documentos Relacionados

• Estratégia distribuída híbrida em cluster multicore heterogêneo para alinhamento múltiplo de sequencias biológicas com o dialign-tx
• Alinhamento múltiplo progressivo de sequências de proteínas
• Algoritmo Q-learning como estratégia de exploração e/ou explotação para metaheurísticas GRASP e algoritmo genético
• Multi-objective genetic algorithms applied to protein sequence alignment.
• Alinhamento múltiplo de proteínas via algoritmo genético baseado em tipos abstratos de dados.