• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Dissertação de Mestrado
DOI
https://doi.org/10.11606/D.45.1998.tde-20210729-020752
Documento
Autor
Nome completo
Francisco Elói Soares de Araújo
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 1998
Orientador
Título em português
Rearranjo de genomas por reversões
Palavras-chave em português
Ciência Da Computação
Resumo em português
O cálculo do número mínimo de eventos de rearranjo de genomas que transformam o genoma de uma espécie em outra é usado para inferir o grau de parentesco entre duas espécies. Devido ao fato da reversão ser, muitas vezes, o único evento de rearranjo de genomas presente em um único cromossomo, o Problema Ordenação po Reversões (MIN-SBR) têm sido estudado, principalmente, nos últimos anos. Nessa disertação estudamos as duas versões de MIN-SBR: a versão orientada, representada por uma permutação orientada, isto é, quando conhecemos a orientação dos genes em relação ao cromossomo, e a versão não-orientada, representada por uma permutação não-orientada, quando não conhecemos essa orientação. Para a versão orientada, Hannenhalli e Pevzner (HP95) descreveram um algoritmo polinominal, que, dada uma permutação orientada'VET.pi' com n elementos, determina uma seqüência mínima de reversões que ordenam 'VET.pi'em tempo O('n IND.5'). Posteriormente, uma versão mais eficiente desse algoritmo foi descrita por Kaplan, Shamir e Tarjan {KST97} cujo tempo é O(n'alfa'(n)+nr), onde 'alfa'(n) é o inverso da função de Ackerman e d é o número mínimo de reversões que ordena 'VET.pi'. Descrevemos uma versão para esse algoritmo que gasta tempo O(nd). Mostramos também, resumidamente, os trabalhos de Meidanis, Walter e Dias [MWD97] que determinam o valor do diâmetro por reversões em permutações orientadas, e formalizam a versão orientada do problema em permutações orientadas circulares, modeladas para estudar o número mínimo de reversões que transformam um cromossomo circular em outro. Para a versão não-orientada do problema, descrevemos o algoritmo polinomial aproximado de Bafna e Pevzner [BP93] que encontra uma seqüência de reversões (que ordenam uma permutação não-orientada 'pi' com n elementos) de tamanho menor ou igual a 7/4 do tamanho da seqüência mínima de reversões que ordena 'pi', e o valor do diâmetro por reversões em ) permutações não-orientadas. Por fim, descrevemos a prova de Caprara [Cap96] de que a versão não orientada de MIN-SBR é NP-difícil
Título em inglês
not available
Resumo em inglês
The calculus of the minimal number of genome rearrangements'events that turn the genome of one specie into another is used to infer the level of relationship among two specie. Because the reversal is, many times, the only genome rearrangements'events present in only one chomosome, the problem of sorting by reversals (MIN-SBR) have been studie, mainly, in the last years. In the dissertation, we studied the two MIN-SBR versions: the signed version, represented by a signed permutation, that is, when we know the relationship between the orientation of the genes and the chromosome, and the unsigned version, represented by a unsigned permutation, when we do not know this orientation. For the signed version, HP95 described a polinomial algorithm that given a signed permutation 'VET.pi' with n elements determine a minimal sequence of reversals that sorting 'VET.pi' in O('n IND.5') time. Later, a more efficient version of this algorithm was described by KST97, whose time is O(n'alfa'(n)+nr), where 'alfa'(n) is the inverse of Ackerman's function, and d is the minimal number of reversals that sorts 'VET.pi'. We describe a version of this algorithm that runs in O(nd) time. We also show, briefly, the work of MWD97 that determine the value of reversal diameter of signed permutations, and formalize the signed version of the circular signed permutations problem, modeled to study the minimal number of reversals that turn one circular chromosome into another. For the unsigned version of problem, we describe the approximation polinomial algorithm by BP93 that finds a reversal sequence (that sorts aunsigned permutation 'pi' with n elements)wich size is at the most7/4 of minimal reversals sequence size that sort 'pi', and the value of reversal diameter in unsigned permutation. Finally, we describe the Caprara's proof[Cap96] of theNP-hardness of the MIN-SBR unsigned version
 
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
Data de Publicação
2021-07-29
 
AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.
Todos os direitos da tese/dissertação são de seus autores
CeTI-SC/STI
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2021. Todos os direitos reservados.