Autores

4741
Caroline da Silva Reis
2026,257,2099
4742
2026,257,2099
4743
2026,257,2099

Informações:

Publicações do PESC

Título
Ciclo Hamiltoniano em Grafos de Rearranjo de Genomas por Transposições Pré-Fixadas
Linha de pesquisa
Algoritmos e Combinatória
Tipo de publicação
Dissertação de Mestrado
Número de registro
Data da defesa
9/2/2010
Resumo

Uma transposição é uma operação que troca dois blocos consecutivos e adjacentes em uma permutação. Uma transposição pré-fixada é uma transposição que move o primeiro elemento em uma permutação. Definimos um grafo denominado Grafo de Rearranjo de Genomas por Transposições Pré-fixadas no qual cada vértice está associado a uma permutação do Grupo Simétrico quando existe uma transposição pré-fixada que aplicada a uma permutação produz a outra.

Neste trabalho apresentamos propriedades deste grafo, dentre as quais a principal é a existência e a construção de ciclos Hamiltonianos. Além de ser interessante pelo fato de o problema de saber se existe ciclo Hamiltoniano em um grafo ser NPCompleto, também corrobora a conjectura de Lovász sobre ciclo Hamiltoniano em Grafos de Cayley. Em uma abordagem de Bioinformática, também torna possível listar todas as permutações de um determinado tamanho, numa ordem na qual há uma transposição pré-fixada entre duas permutações consecutivas, e ainda de modo que todas as permutações com o mesmo último elemento estejam consecutivas nesta listagem, o que auxilia no estudo do problema desafiador de ordenar por transposições.

Abstract

A transposition is an operation that exchanges two consecutive adjacent blocks in a permutation. A prefix transposition is a transposition that moves the first element in the permutation. We define the Prefix Transposition Genome Rearrangement Graph, the vertices are the permutations the Symmetric Group are adjacent when there exists a prefix transposition that applied to a permutation produces the other one.

In this work we present properties of this graph, amongst which the main one is the existence and construction of Hamiltonian cycles. Besides being interesting for the fact that to know whether there are Hamiltonian cycles in a graph is NPComplete, also it corroborates to Lovász’s conjecture about Hamiltonian cycles in Cayley graphs. In the context of Bioinformatics, it additionally yields a list of all the permutations of a given size, in an order that has a prefix transposition between two consecutive permutations, and in a particular way such that all the permutations with the same last element are consecutive in this order, which contributes to the study of the challenging problem to sorting by transpositions.

Topo