Algorithms for sorting by reversals or transpositions, with application to genome rearrangement

Autor(es)

Gustavo Rodrigues Galvão

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

Membros da banca

Zanoni Dias; Maria Emilia Machado Telles Walter; Yoshiko Wakabayashi; Eduardo Candido Xavier; Guilherme Pimentel Telles

• Orientador: Zanoni Dias

Resumo

Ao longo da evolução, eventos de rearranjo podem alterar a ordem e a orientação dos genes de um genoma. O problema de calcular a menor sequência de rearranjos que transforma um genoma em outro é um problema bastante estudado que encontra aplicações em genômica comparativa. Representando genomas como permutações, nas quais os genes aparecem como elementos, esse problema pode ser reduzido ao problema combinatório de ordenar uma permutação utilizando o menor número de rearranjos. Tal problema combinatório, referido como problema da ordenação por rearranjo, varia de acordo com os tipos de rearranjo considerados. Nesta tese, focamos nosso estudo em dois tipos de rearranjo: reversões e transposições. Muitas variações do problema da ordenação por rearranjo que envolvem esses rearranjos têm sido atacadas na literatura e, para a maior parte delas, os melhores algoritmos conhecidos são aproximações ou heurísticas. Em razão disso, apresentamos uma ferramenta, chamada GRAAu, que auxilia a avaliação dos resultados produzidos por esses algoritmos. Além disso, apresentamos uma heurística genérica que pode ser usada para melhorar as soluções produzidas por qualquer algoritmo não exato. Além de apresentar o GRAAu e a heurística de melhoria, os quais possuem um apelo mais geral, apresentamos contribuições relacionadas à variações específicas do problema da ordenação por rearranjo. Primeiro, consideramos o problema da ordenação por transposições e apresentamos resultados teóricos e práticos relacionados a três algoritmos aproximados baseados em uma abordagem alternativa ao grafo de ciclos, que é uma ferramenta padrão para atacar o problema da ordenação por rearranjo. Depois, voltamos nossa atenção à variações que envolvem rearranjos curtos. Mais precisamente, estudamos cinco variações: (i) o problema de ordenar uma permutação linear com sinal por reversões super curtas, (ii) o problema de ordenar uma permutação circular com sinal por reversões super curtas, (iii) o problema de ordenar uma permutação linear com sinal por reversões curtas, (iv) o problema de ordenar uma permutação linear com sinal por rearranjos super curtos e (v) o problema de ordenar uma permutação linear com sinal por rearranjos curtos. Apresentamos algoritmos polinomiais para os problemas (i), (ii) and (iv), um algoritmo 5-aproximado para o problema (iii) e um algoritmo 3-aproximado para o problema (v). Usamos o algoritmo desenvolvido para o problema (ii) para reconstruir a filogenia de genomas de bactérias do gênero Yersinia e comparamos os resultados com as filogenias apresentadas em trabalhos anteriores (AU)

• Processo FAPESP: 14/04718-6 - Algoritmos para o problema da ordenação por rearranjo
• Beneficiário: Gustavo Rodrigues Galvão
• Modalidade de apoio: Bolsas no Brasil - Doutorado