Distancias de transposição entre genomas / Transposition distances between genomes

AUTOR(ES)
DATA DE PUBLICAÇÃO

2005

RESUMO

Uma das principais formas de se medir a distância evolutiva entre espécies é avaliando-se quão transformado um genoma foi em relação a outro. Tais transformações são conhecidas como rearranjos de genoma. Neste trabalho estaremos analisando o rearranjo chamado de transposição, evento que troca de posição dois blocos consecutivos de genes de um mesmo cromossomo. Mais especificamente, buscamos encontrar o número mínimo de transposições que transforma um cromos somo em outro, valor conhecido como distância de transposição. Matematicamente, consideramos os cromossomos como permutações e o problema de se transformar uma permutação em outra pode ser visto como uma ordenação. Em nosso estudo, introduzimos uma operação de remoção de elementos, ferramenta ainda pouco explorada no estudo da distância de transposição, mas que nos possibilitou obter um limite superior para a distância de transposição. Também sugerimos novas formas de se utilizar a remoção de elementos e a análise de subseqüências de permutações. Como forma de se tentar obter novos conhecimentos sobre o problema da distância de transposição, consideramos a variação do problema em que somente transposições de prefixo são permitidas. Zanoni Dias propôs um algoritmo polinomial que transforma qualquer permutação de comprimento n em sua reversa em f3n/41 passos, porém sem uma prova completa. Modificamos esse algoritmo, mantendo o número de passos, e apresentamos uma prova completa da correção do algoritmo modificado. Ainda no problema de distância de transposição de prefixo, analisamos as permutações cujas distâncias se igualam ao limite inferior de distância de pontos de quebra. Tais permutações são fáceis de serem ordenadas por transposições de prefixo em tempo polinomial, pois possuem ordenação ótima única e bem definida. Ao final chegamos à conclusão que as permutações que são fáceis de se ordenar no problema de transposições de prefixo também são fáceis no problema de transposições, o que prova que a variação do problema auxilia no estudo do problema original

ASSUNTO(S)

teoria da computação genomas computer theory phylogeny genomes filogenia

ACESSO AO ARTIGO

Documentos Relacionados