Título: Programação por Restrições aplicada a Problemas de Rearranjo de Genomas

Resumo:

O processo evolutivo foi o principal responsável pela diferenciação entre os seres vivos e uma das teorias contemporâneas acerca do modo como ocorre esse processo afirma que, durante o curso da evolução, mudanças genéticas aconteceram, criando diferentes espécies de seres vivos. Muitas dessas mudanças são devido a mutações pontuais que alteram a cadeia de DNA, impedindo que a informação seja expressa, ou que seja expressa de um modo diferente. A comparação de sequência é o método mais usual de se caracterizar a ocorrência de mutações pontuais, sendo um dos problemas mais abordados em Biologia Computacional. O interesse em fazer tal comparação é encontrar a distância de edição.
A distância de edição é uma medida capaz de estimar a distância evolutiva entre duas cadeias, mas não possui a informação de quais operações globais foram utilizadas para a transformação de uma sequência em outra. Estas operações globais são os chamados Rearranjos de Genomas, que podem ser, por exemplo, reversões, transposições, fissões e fusões. Um conceito de distância pode ser definido para qualquer classe de rearranjo como sendo o menor número de operações pertencentes a essa classe que são necessários para transformar um genoma em outro. Por exemplo, chama-se distância de reversão o menor número de reversões necessárias para transformar um genoma em outro e a distância de transposição é o menor número de transposições. Este trabalho segue a linha de pesquisa utilizada por Dias e Dias e nós apresentaremos modelos de Programação por Restrições para ordenação por reversões e ordenação por reversões e transposições, baseados na teoria do Problema de Satisfação de Restrições e na teoria do Problema de Otimização com Restrições. Nós fizemos comparações com os modelos de Programação por Restrições para ordenação por transposições, descrito por Dias e Dias, ordenação por reversões e ordenação por reversões e transposições com os modelos de Programação Linear Inteira para os mesmos problemas descritos por Dias e Souza.