MO640 - Exercícios - Para 2004-11-24

Para esta questão, considere genomas lineares e operações posicionais como no artigo de Dias, Fortuna e Meidanis, 2004. Considere o genoma [6,1,2,4,3,5] e determine a distância de transposições e também a distância de transposições de prefixo entre ele e [1,2,3,4,5,6].
Encontre uma série de floor(n/2)+2 operações (cada uma sendo uma reversão ou uma transposição) que transforme π_n = (-1 -2 -3 ... -n) em ι_n = (+1 +2 +3 ... +n), mas onde a última operação aplicada seja uma reversão. Obs: pode usar quaisquer resultados usados no artigo de Meidanis, Walter e Dias, 2002.
Considerando genomas circulares, de dupla fita, e operações intrínsecas como descrito na tese de Dias, 2002, observe que reversões são operações de norma 2. Existem outros tipos de operações, que não sejam reversões, mas que tenham norma 2 e que aplicadas em um genoma resultem em um outro genoma? Em outras palavras, existe uma permutacao ρ e um genoma π tais que ρ tem norma 2 e o produto ρπ seja um genoma?