O problema da ordenação de permutações usando operações de prefixo e sufixo

Resumo

Reversões e transposições são os tipos mais comuns de rearranjos de genomas, que são operações que afetam grandes porções dos genomas. Por meio dos rearranjos é possível estabelecer a divergência entre indivíduos ao longo da evolução. A distância mínima entre dois determinados genomas é assumida como sendo a distância evolutiva entre eles, e ela pode ser obtida por meio de cenários que envolvam os rearranjos. Assim, um problema de ordenação de genomas por meio de um ou mais tipos de rearranjos é o problema de encontrar a distância mínima entre dois genomas utilizando os rearranjos permitidos. Quando as operações de rearranjo afetam segmentos do início ou do fim do genoma, dizemos que são rearranjos de prefixo ou de sufixo, respectivamente. Esta proposta apresenta alguns conceitos iniciais e resultados já existentes sobre alguns problemas relacionados, bem como especifica o objetivo do nosso trabalho, que visa lidar com problemas de ordenação usando operações de reversão e transposição nas suas versões de prefixo e sufixo. (AU)