Ordenação por reversão. - Nakasato, Andrea Tieme (2008)
Muitos problemas em biologia computacional, especialmente aqueles envolvendo comparação de genomas, podem ser reduzidos a problemas clássicos em combinatória. Neste contexto, um genoma é representado por uma permutação sinalizada cujos elementos correspondem aos genes, e cujos sinais (+ ou -) indicam a direção de transcrição dos genes. Assim, genomas podem ser comparados simplesmente comparando-se as correspondentes permutações e operações em genomas podem ser definidos em termos de operações sobre permutações. Neste trabalho, estamos interessados no problema de comparar dois genomas determinando um cenário com o melhor número de operações de reversão que são necessárias para transformar um genoma em outro. Este problema, na linguagem de permutações, é um problema clássico conhecido como ordenação por reversão. Observamos que podemos supor que uma das permutações dadas é a identidade, e assim, podemos considerar que é dada apenas uma permutação e que o objetivo é transformá-la na permutação identidade, realizando o menor número de operações de reversão.