Problemas de ordenação de permutações por operações ponderadas pelo número de fragmentações

Resumo

Calcular a distância evolucionária entre espécies é um problema importante da área de Biologia Computacional, sendo que para isso consideramos conjuntos de mutações que alteram grandes trechos do genoma, os quais chamamos de rearranjos de genoma. Representa-se um genoma como uma permutação de inteiros, em que cada elemento corresponde a um bloco conservado (região de alta similaridade entre os genomas a serem comparados). Devido a propriedades algébricas das permutações, o problema de transformar um genoma em outro é equivalente ao da ordenação de permutações por operações de rearranjo. A abordagem mais comum considera que todos os rearranjos tem o mesmo custo, assim o objetivo é encontrar uma sequência mínima de rearranjos que ordenem a permutação. Porém, estudos indicam que algumas operações de rearranjo tem maior probabilidade de acontecer do que outras, fazendo com que abordagens em que operações possuem custos diferentes sejam mais realistas. Nessa abordagem ponderada, o objetivo é encontrar a sequência que ordena a permutação, tal que a soma dos custos dos rearranjos dessa sequência seja mínimo. Esta proposta apresenta uma nova versão para o problema da ordenação de permutações por operações ponderadas, em que a função de custo de uma operação corresponde a quantidade de fragmentações que a operação causa na permutação. (AU)