Problemas de Distâncias de Rearranjos de Genomas

Resumo

Um modo de comparar dois genomas é computar uma distância entre eles. Idealmente, essa distância deve refletir as divergências evolucionárias entre ambos. Os fenômenos responsáveis pelas diferenciações entre os seres-vivos são as mutações ocorridas no material genético. Os eventos de mutação mais comuns afetam pontualmente o genoma, inserindo, removendo ou substituindo nucleotídeos. Entretanto, eventos de mutações globais, os chamados rearranjos de genomas, afetam grandes trechos do genoma e são um desafio para a teoria da computação, pois, na maioria dos casos, computar uma distância entre genomas na presença de operações globais resulta em problemas NP-Completos. Este projeto de pesquisa foca em heurísticas, algoritmos e provas formais para problemas NP-Completos ou com complexidade indefinida em rearranjo de genomas. Alguns tópicos de pesquisa serão específicos para certas classes de operações como, por exemplo, reversões ou transposições. Outros tópicos focam na distância entre os genomas usando mais de uma operação de rearranjo como, por exemplo, distância entre genomas quando reversões e transposições são permitidas. Uma distância precisa e calculável rapidamente possui diversas aplicações. Por exemplo, dado um grupo de genomas, é possível calcular a distância para cada par de genomas e armazenar os valores em uma matriz de distâncias. Essa matriz de distância pode ser usada como entrada para a geração de uma árvore filogenética.