Avaliação de estratégias Alignment-free para determinar o fator de pruning em comparação paralela de sequências

Abstract

A Bioinformática tem como uma de suas principais operações a comparação entre se- quências biológicas. Através de métodos exatos baseados no alinhamento, são obtidos

resultados ótimos, porém o tempo para obtenção desses alinhamentos é muito grande. Com a adição da técnica de block pruning, o tempo pode ser bastante reduzido. Porém, no block pruning a área de poda é obtida ao longo da execução do alinhamento. Para determinar o tempo de execução de uma comparação com pruning antes do alinhamento existe uma regressão multi-linear. No entanto, essa fórmula requer que o fator de block pruning seja conhecido antes da execução da comparação, o que não acontece. O presente trabalho de graduação tem como objetivo analisar algoritmos que fazem a comparação sem se basear no alinhamento, alignment-free, e que são executados rapidamente, com o objetivo de utilizá-los para gerar os valores de block pruning antes do alinhamento das sequências. Os resultados da análise de diferentes algoritmos mostraram que a ferramenta ALF-N2 (ALignment-Free framework), através de seu algoritmo N2, apresenta resultados

satisfatórios para a geração de uma correlação entre o fator de block pruning e a simila- ridade entre as sequências por meio do alignment-free. Usando a estratégia proposta no

presente trabalho de graduação, conseguimos obter taxas de block pruning com muito boa acurácia, apresentando erros de até 7,0% para sequências pequenas e 3,7% para sequências maiores.