• 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
 
 
Thèse de Doctorat
DOI
https://doi.org/10.11606/T.45.2003.tde-20210729-131755
Document
Auteur
Nom complet
Estela Maris Rodrigues
Adresse Mail
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Paulo, 2003
Directeur
Titre en portugais
Algoritmos para comparação de árvores filogenéticas e o problema dos pontos de recombinação
Mots-clés en portugais
Teoria Dos Grafos
Resumé en portugais
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
Titre en anglais
not available
Resumé en anglais
not available
 
AVERTISSEMENT - Regarde ce document est soumise à votre acceptation des conditions d'utilisation suivantes:
Ce document est uniquement à des fins privées pour la recherche et l'enseignement. Reproduction à des fins commerciales est interdite. Cette droits couvrent l'ensemble des données sur ce document ainsi que son contenu. Toute utilisation ou de copie de ce document, en totalité ou en partie, doit inclure le nom de l'auteur.
Date de Publication
2021-07-29
 
AVERTISSEMENT: Apprenez ce que sont des œvres dérivées cliquant ici.
Tous droits de la thèse/dissertation appartiennent aux auteurs
CeTI-SC/STI
Bibliothèque Numérique de Thèses et Mémoires de l'USP. Copyright © 2001-2024. Tous droits réservés.