Alinhamento Múltiplo de Seqüências Baseado em Coberturas de Conjuntos

Nesta tese estudamos a aplicação das coberturas de um conjunto de resíduos ao problema do alinhamento de um conjunto de seqüências. Definimos um novo método para construir uma matriz de substituição, baseado nas relações físico-químicas dos resíduos induzidas pela cobertura. O desempenho da matriz obtida pelo método, que mede o grau de sucesso da matriz em auxiliar os algoritmos de alinhamento duplo a alinhar corretamente um conjunto de pares de seqüências, foi comparável ao desempenho das matrizes mais importantes da literatura. Também definimos uma nova heurística para construir um alinhamento múltiplo destas seqüências, que é baseada em uma nova estrutura de dados, chamada de uma árvore de conjuntos de sufixos. Esta árvore é uma generalização da árvore de sufixos destas seqüências, e é baseada nas relações entre os resíduos induzidas pela cobertura. O desempenho desta heurística, que mede a precisão da heurística em encontrar o melhor alinhamento das seqüências de cada uma das famílias de uma base, é comparável ao desempenho das heurísticas mais relevantes da literatura que estudamos. A árvore possui um número exponencial de vértices no pior caso, mas, para algumas coberturas da literatura, este número de vértices é polinomial no caso médio. Além disso, ao avaliarmos a heurística, notamos que somente precisamos construir uma versão reduzida da árvore, que possui um número polinomial de vértices no pior caso.