Tese

Rearranjo de genomas por reversões (1998)

• Authors:
  • Araújo, Francisco Elói Soares de
  • Soares, José Augusto Ramos (Orientador)
• Autor USP: ARAUJO, FRANCISCO ELOI SOARES DE - IME
• Unidade: IME
• Sigla do Departamento: MAP
• Assunto: CIÊNCIA DA COMPUTAÇÃO
• Language: Português
• Abstract: 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, modeladaspara 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
• Imprenta:
  • Publisher place: São Paulo
  • Date published: 1998
• Data da defesa: 14.08.1998


---

How to cite

A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

• ABNT

  ARAÚJO, Francisco Elói Soares de. Rearranjo de genomas por reversões. 1998. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 1998. Disponível em: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-020752/. Acesso em: 18 abr. 2024.

• APA

  Araújo, F. E. S. de. (1998). Rearranjo de genomas por reversões (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-020752/

• NLM

  Araújo FES de. Rearranjo de genomas por reversões [Internet]. 1998 ;[citado 2024 abr. 18 ] Available from: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-020752/

• Vancouver

  Araújo FES de. Rearranjo de genomas por reversões [Internet]. 1998 ;[citado 2024 abr. 18 ] Available from: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-020752/

Últimas obras dos mesmos autores vinculados com a USP cadastradas na BDPI:

• Alinhamento e comparação de sequências