Estratégias de otimização para alinhamento múltiplo paralelo exato de sequências biológicas

Abstract

O Alinhamento Múltiplo de Sequências (MSA) é um método utilizado na bioinformática para a análise de relações evolutivas e funcionais entre sequências biológicas. No entanto, encontrar o alinhamento matematicamente ótimo é um problema NP-Completo, tornando os algoritmos exatos inviáveis para a maioria dos conjuntos de dados práticos. A ferramenta PA-Star, uma implementação paralela do algoritmo de busca A*, representa um avanço ao garantir a otimalidade da solução. Contudo, dentre outros fatores, sua eficiência é limitada pela função heurística h2,all (baseada em pares de sequências), cujo cálculo sequencial representa um gargalo e cuja precisão resulta em uma poda pouco agressiva do espaço de busca. Este trabalho propõe otimizações para o PA-Star, focando na substituição da heurística h2,all por uma função mais robusta, a h3,all (baseada em trios de sequências), e na paralelização de sua etapa de cálculo. A hipótese central é que a h3,all, apesar do maior custo computacional para sua obtenção, fornecerá um limite inferior mais preciso, resultando em uma poda mais eficaz do espaço de busca e, consequentemente, em uma redução do tempo de execução total. Como resultado, espera-se aprimorar o desempenho da ferramenta, permitindo que o PA-Star resolva instâncias mais complexas do problema de MSA de forma ótima e em tempo hábil.