• 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
 
 
Tese de Doutorado
DOI
https://doi.org/10.11606/T.45.2003.tde-20210729-131755
Documento
Autor
Nome completo
Estela Maris Rodrigues
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2003
Orientador
Título em português
Algoritmos para comparação de árvores filogenéticas e o problema dos pontos de recombinação
Palavras-chave em português
Teoria Dos Grafos
Resumo em português
Uma árvore filogenética T é uma árvore enraizada cujas folhas estão distintamente rotuladas com elementos de um conjunto finito S(T), e cujos nós internos têm grau pelo menos 2. Uma floreta de concordância (agreement forest) de duas árvores filogenéticas T e U tais que S(T)=S(U) é uma floresta filogenética que pode ser obtida tanto a partir de T quanto de U realizando-se uma seqüência do seguinte par de operações: remoção de um arco e contração do arco cuja extremidade superior incide no arco removido. Neste trabalho, estudamos o seguinte problema: dadas duas árvores filogenéticas T e U tais que S(T)=S(U), encontrar uma floresta de concordância ótima, isto é, floresta de concordância de T e U que tenha um número mínimo de componentes. Este problema tem relação com o problema da localização de pontos de recombinação em seqüências genéticas ou protêicas pré-alinhadas, para o qual um modelo foi apresentado por Hein [17, 18]. Os resultados prévios para este problema, ambos para árvores filogenéticas com grau no máximo 2 nos nós, consistem em uma prova de que o problema é NP-difícil e um algoritmo de aproximação devido a Hein et al. [19, 20]. Em nosso trabalho, mostramos que o Algoritmo de Hein et al, apresentado como uma 3-aproximação, possui na verdade razão de aproximação 4, e que essa razão é justa. Também propomos, implementamos e testamos três algoritmos de 3-aproximação para o problema. Estes algoritmos deferem consideravelmente entre si com relaçao aos métodos de análise empregados e também quanto à qualidade das soluções produzidas. Esses resultados de aproximabilidade são desenvolvidos no contexto de uma família de algoritmos para o problema da floresta de concordância ótima, limitantes superiores e inferiores são apresentados para as razões de aproximação desses algoritmos. Adicionalmente, estendemos um desses algoritmos de 3-aproximação para um algoritmo de (d+1)-aproximação para o problema da floresta ) de concordância ótima com árvores filogenéticas possuindo grau máximo d nos nós (d > ou = a 2). Desenvolvemos ainda uma prova de que o problema da floresta de concordância ótima é APX-difícil para árvores com grau máximo 2 utilizando idéias de Hein et al. [19, 20]. Este resultado, junto com a (d+1)-aproximação para o problema da floresta de concordância ótima para árvores com grau no máximo d que provamos, mostra que este último problema é APX-completo e que o problema da floresta de concordância ótima para árvores sem restrição nos graus dos nós é APX-difícil. a relação entre op problema da floresta de concordância ótima e o modelo de Hein é feita através do problema de encontrar, para duas árvores filogenéticas com o mesmo conjunto de rótulos nas folhas, o número mínimo de transferências de subárvores que transform uma árvore na outra. Allen e steel[1] observam que as distâncias entre árvores filogenéticas dadas pelo número mínimo de transferência de subárvore (SPR) e pelo número de componentes de uma floresta de concordância ótima (MAF) não são equivalentes, corrigindo uma observação anterior de Hein et al. [20]. Em nosso trabalho, definimos duas distâncias entre árvores filogenéticas baseadas em diferentes tipos de transferências de subárvore. Mostramos que uma dessas distâncias equivale à distância MAF, enquanto que a outra é igua a MAF em alguns casos e MAF - 1 nos demais. Esta segunda distância pode ser aplicada ao cálculo do número de eventos de recombinação no modelo de Hein, pois as transferências de subárvore permitidas por ela equivalem a esses eventos
Título em inglês
not available
Resumo em inglês
not available
 
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-2024. Todos os direitos reservados.