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
-
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: 07 nov. 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 nov. 07 ] 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 nov. 07 ] Available from: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-020752/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
