Novas abordagens para o problema do alinhamento múltiplo de sequências

Autor(es)

André Atanasio Maranhão Almeida

• Tipo de documento: Tese de Doutorado
• Imprenta: Campinas, SP.
• Instituição: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
• Data de defesa: 2013-02-21

Membros da banca

Zanoni Dias; Guilherme Pimentel Telles; Orlando Lee; Felipe Rodrigues da Silva; Maria Emilia Machado Telles Walter

• Orientador: Zanoni Dias

Resumo

Alinhamento de seqüências é, reconhecidamente, uma das tarefas de maior importância em bioinformática. Tal importância origina-se no fato de ser uma operação básica utilizada por diversos outros procedimentos na área, como busca em bases de dados, visualização do efeito da evolução em uma família de proteínas, construção de árvores filogenéticas e identificação de motifs preservados. Seqüências podem ser alinhadas aos pares, problema para o qual já se conhece algoritmo exato com complexidade de tempo O(l2), para seqüências de comprimento l. Pode-se também alinhar simultaneamente três ou mais seqüências, o que é chamado de alinhamento múltiplo de seqüências (MSA, do inglês Multiple Sequence Alignment ). Este, que é empregado em tarefas como detecção de padrões para caracterizar famílias protéicas e predição de estruturas secundárias e terciárias de proteínas, é um problema NP - Difícil. Neste trabalho foram desenvolvidos métodos heurísticos para alinhamento múltiplo de seqüências de proteína. Estudaram-se as principais abordagens e métodos existentes e foi realizada uma série de implementações e avaliações. Em um primeiro momento foram construídos 342 alinhadores múltiplos utilizando a abordagem progressiva. Esta, que é uma abordagem largamente utilizada para construção de MSAs, consiste em três etapas. Na primeira delas é computada a matriz de distâncias. Em seguida, uma árvore guia é gerada com base na matriz e, finalmente, o MSA é construído através de alinhamentos de pares, cuja ordem é definida pela árvore. Os alinhadores desenvolvidos combinam diferentes métodos aplicados a cada uma das etapas. Para a computação das matrizes de distâncias foram desenvolvidos dois métodos, que são capazes também de gerar alinhamentos de pares de seqüências. Um deles constrói o alinhamento com base em alinhamentos locais e o outro utiliza uma função logarítmica para a penalização de gaps. Foram utilizados ainda outros métodos disponíveis numa ferramenta chamada PHYLIP. Para a geração das árvores guias, foram utilizados os métodos clássicos UPGMA e Neighbor Joining. Usaram-se implementações disponíveis em uma ferramenta chamada R. Já para a construção do alinhamento múltiplo, foram implementados os métodos seleção por bloco único e seleção do par mais próximo. Estes, que se destinam a seleção xiii do par de alinhamentos a agrupar no ciclo corrente, são comumente utilizados para tal tarefa. Já para o agrupamento de um par de alinhamentos, foram implementados 12 métodos inspirados em métodos comumente utilizados - alinhamento de consensos e alinhamento de perfis. Foram feitas todas as combinações possíveis entre esses métodos, resultando em 342 alinhadores. Eles foram avaliados quanto à qualidade dos alinhamentos que geram e avaliou-se também o desempenho dos métodos, utilizados em cada etapa. Em seguida foram realizadas avaliações no contexto de alinhamento baseado em consistência. Nesta abordagem, considera-se MSA ótimo aquele que estão de acordo com a maioria dos alinhamentos ótimos para os n(n ? 1)/2 alinhamentos de pares contidos no MSA. Alterações foram realizadas em um alinhador múltiplo conhecido, MUMMALS, que usa a abordagem. As modificações foram feitas no método de contagem k-mer, assim como, em outro momento, substituiu-se a parte inicial do algoritmo. Foram alterados os métodos para computação da matriz de distâncias e para geração da árvore guia por outros que foram bem avaliados nos testes realizados para a abordagem progressiva. No total, foram implementadas e avaliadas 89 variações do algoritmo original do MUMMALS e, apesar do MUMMALS já produzir alinhamentos de alta qualidade, melhoras significativas foram alcançadas. O trabalho foi concluído com a implementação e a avaliação de algoritmos iterativos. Estes se caracterizam pela dependência de outros alinhadores para a produção de alinhamentos iniciais. Ao alinhador iterativo cabe a tarefa de refinar tais alinhamentos através de uma série de ciclos até que haja uma estabilização na qualidade dos alinhamentos. Foram implementados e avaliados dois alinhadores iterativos não estocásticos, assim como um algoritmo genético (GA) voltado para a geração de MSAs. Nesse algoritmo genético, implementado na forma de um ambiente parametrizável para execução de algoritmos genéticos para MSA, chamado ALGAe, foram realizadas diversas experiências que progressivamente elevaram a qualidade dos alinhamentos gerados. No ALGAe foram incluídas outras abordagens para construção de alinhamentos múltiplos, tais como baseada em blocos, em consenso e em modelos. A primeira foi aplicada na geração de indivíduos para a população inicial. Foram implementados alinhadores baseados em blocos usando duas abordagens distintas e, para uma delas, foram implementadas cinco variações. A segunda foi aplicada na definição de um operador de cruzamento, que faz uso da ferramenta M-COFFEE para realizar alinhamentos baseados em consenso a partir de indivíduos da população corrente do GA, e a terceira foi utilizada para definir uma função de aptidão, que utiliza a ferramenta PSIPRED para predição das estruturas secundárias das seqüências. O ALGAe permite a realização de uma grande variedade de novas avaliações (AU)

• Processo FAPESP: 07/08020-0 - Novas abordagens para o problema do alinhamento múltiplo de seqüências
• Beneficiário: André Atanasio Maranhão Almeida
• Modalidade de apoio: Bolsas no Brasil - Doutorado