Ordenação por transposições de prefixo

• Processo: 03/04578-5
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de setembro de 2003
• Data de Término da vigência: 28 de fevereiro de 2005
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: João Meidanis
• Beneficiário: Vinicius Jose Fortuna
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Combinatória Cromossomos
• Palavra(s)-Chave do Pesquisador: Combinatoria | Cromossomos | Otimizacao | Rearranjo De Genomas

Resumo

Considere um vetor contendo os número de 1 a n em uma ordem qualquer. Uma transposição de prefixo é uma operação que troca de posição de dois blocos adjacentes, sendo que um ocupa as posições de 1 a y-1 (um prefixo) e o outro de y a z-1, para certos inteiros y e z tais que 1 < y < z <= n+1. O problema da ordenação por transposições de prefixo consiste em determinar, dado um vetor com os números inteiros de 1 a n numa ordem qualquer, o número mínimo de transposições de prefixo necessário para deixá-lo em ordem crescente (chamado de distância). Este problema é uma variante mais simples de um outro problema, chamado de ordenação por transposições, que aparece em comparação de genomas. Neste trabalho pretendemos estudar quatro problemas: (1) resolver o problema para o vetor R_n = [n, n-1, n-2 2, 1]; (2) calcular a máxima distância entre vetores de tamanho n; (3) determinar a complexidade da ordenação por transposições de prefixo; e, (4) determinar a complexidade da ordenação por transposições. (AU)

Publicações acadêmicas

(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)

FORTUNA, Vinicius Jose. Distancias de transposição entre genomas. 2005. Dissertação de Mestrado - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.