Exportar registro bibliográfico

Rearranjo de genomas por reversões (1998)

  • Authors:
  • 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:
  • Data da defesa: 14.08.1998
  • Acesso à fonte
    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; SOARES, José Augusto Ramos. Rearranjo de genomas por reversões. 1998.Universidade de São Paulo, São Paulo, 1998. Disponível em: < https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-020752/ >.
    • APA

      Araújo, F. E. S. de, & Soares, J. A. R. (1998). Rearranjo de genomas por reversões. 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, Soares JAR. Rearranjo de genomas por reversões [Internet]. 1998 ;Available from: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-020752/
    • Vancouver

      Araújo FES de, Soares JAR. Rearranjo de genomas por reversões [Internet]. 1998 ;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:

Digital Library of Intellectual Production of Universidade de São Paulo     2012 - 2021