Introdução

Em rearranjo de genomas uma transposição consiste em um evento mutacional que troca um bloco contíguo de genes de uma região para outra dentro de um mesmo cromossomo. Em uma formalização matemática, modela-se um cromossomo Pi, com n genes para uma permutação Pi=[Pi₁ Pi₂...Pi_n] de números inteiros entre 1 e n, onde cada elemento Pi_j representa um gene. A distância de transposição d(Pi) é o número mínimo de transposições necessárias para ordenar Pi. Foi provado que o problema de distância de transposição é NP-difícil.

O diâmetro de transposição D(n) é a maior distância de transposição entre duas permutações de n elementos. Somente para n≤15 elementos os valores de D(n) são conhecidos. Se d(Pi)=D(n), dizemos que Pi é uma permutação diametral. Todas as permutações diametrais para n≤13 já foram encontradas, mas apenas alguns exemplos foram descritos para n=14 e n=15.

Objetivos

O presente estudo teve como objetivos:

• Estudar o problema de diâmetro de transposição com o intuito de contribuir para o problema de distância de transposição;

• Aumentar em algumas unidades o conjunto de valores de n para os quais o diâmetro é conhecido;

• Determinar quais permutações atingem o diâmetro de transposição.

Metodologia

A pesquisa se baseou fundamentalmente em teoria matemática e computacional, assim a metodologia consistiu: (a) no estudo de conceitos e propriedades combinatórios, matemáticos e algoritmicos em bibliografia recomendada e de artigos científicos relacionados ao problema; (b) na sistematização dos resultados através de relatórios; (c) em reuniões e seminários semanais.

Resultados

Calculamos a distância de transposição de todas as permutações para n≤14, através de uma busca em largura e usando equivalências tóricas para reduzir o espaço de busca. A pesquisa consumiu no máximo 66 GB de memória principal, e o tempo total de execução em um supercomputador SGI Altix 4700 foi de 22 dias.

Nossos dados foram retificados por um estudo anterior para n≤13. E esta é a primeira vez que a distribuição de distâncias para n=14 é computada.

Conclusões

O resultado deste trabalho pode ser usado como um ponto de partida para procurar permutações diametrais de 15 e 16 elementos, primeiramente gerando candidatos às permutações diametrais de 14 elementos, e em seguida, usando um algoritmo exato para o distância de transposição, juntamente ao nosso banco de dados, para procurar as permutações cuja distância é 9 ou 10.