Introdução ao Problema de Ordenação por Transposições


                      Cleber Valgas Gomes Mira

                 Sexta-feira, 7 de maio de 2004

                  Auditório do IC, IC-1, 13:00hs


Resumo: 

	Um dos principais problemas em Biologia Computacional é realizar
comparações entre genomas de espécies distintas com o objetivo de 
levantar hipóteses evolutivas e construir filogenias de um grupo de
espécies. Uma das técnicas de Genômica Comparativa mais utilizadas em 
certas variedades do vírus da Herpes e no estudo de espécies "distantes"
na linha da evolução é a técnica de análise de Rearranjo de Genomas. Um 
evento de rearranjo em um genoma é uma mutação que envolve o 
deslocamento de grandes blocos de genes. O problema de Rearranjo de
Genomas resume-se em encontrar o menor numero de eventos que transformem
um genoma em outro. 
Dentre os diversos eventos de rearranjo, as transposições tem despertado
grande interesse teórico entre os cientistas da computação devido a 
complexidade de sua estrutura combinatórica e o fato de não ter sido 
ainda classificada a sua dificuldade. 

Nessa apresentação iremos mostrar os dois primeiros algoritmos 
aproximativos para determinar a distância de transposição.