Limites para Distância e Diâmetro em Rearranjo de Genomas por Transposições
Autores
|
5374 |
2435,257,2026
|
|
|
5377 |
2435,257,2026
|
|
|
5378 |
2435,257,2026
|
Informações:
Publicações do PESC
Esta dissertação trata do problema de Rearranjo de Genomas em um de seus modelos mais clássicos, modelo de transposições. São abordados dois problemas: Ordenação por Transposições e Diâmetro de Transposição.
Sobre o problema de Ordenação por Transposições - provado ser NP-difícil em 2010 - é explorada a classe das permutações solitárias. Com o intuito de obter limites justos para esta classe é apresentado um estudo sobre sua caracterização e propriedades estruturais. São determinados assim valores exatos e limites justos para distâncias de algumas famílias apresentadas.
Os atuais limites inferiores para o diâmetro são obtidos através da justaposição de permutações solitárias, assim é tratado também o Diâmetro de Transposição - problema em aberto para n > 15. Um estudo sobre o atual limite inferior deste problema é apresentado através da investigação teórica da operação de união de permutações. Em particular, é investigada a união de permutações solitárias e sua utilização para construir as famílias que constituem os atuais limites inferiores.
Ainda em relação ao problema de Diâmetro de Transposição, em 2010 foi proposto um novo limite inferior através da união da nova definição de permutação super-ruim para construção das famílias mais distantes. Nesta dissertação é apresentada uma invalidação deste limite para o diâmetro de transposição. São apresentadas também condições suficientes para permutações não serem usadas na construção de novos limites através da operação de união. São propostas novas famílias onde suas distâncias atingem o atual limite inferior. E por fim, é apresentada uma nova estratégia para melhorar o limite inferior para o problema do diâmetro de transposição.
This dissertation discusses the transposition model, a classic mutational event in Genome Rearrangements. Two problems are considered: Sorting by Transpositions; and the Transposition Diameter.
For the Sorting by Transpositions - settled as NP-hard in 2010 - we obtain tight bounds and determine the transposition exact distance for the lonely permutation class, through a study of characterizations and structural properties of such permutations.
Lower bounds for the diameter have been obtained through a juxtaposition of lonely permutations, therefore for the Transposition Diameter - an open problem for every n>15 - we establish an algebraic study of the union operation. We present a theoretical investigation of the union of permutations, and the union of lonely permutations, the main tool used to construct the current lower bound.
In 2010, it was claimed a new lower bound for the Transposition Diameter by using the union of so-called super-bad permutations to construct such farther families. In this work, we show that there is no super-bad permutation, thus invalidating the claimed lower bound. We also present conditions so that several permutations cannot be used to increase the lower bound through the union operation. Moreover, we present alternative families that meet the current lower bound and propose a strategy to increase the lower bound that uses the union operation and further advances on the approach used so far in the literature.