• 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
 
 
Tesis Doctoral
DOI
https://doi.org/10.11606/T.45.2003.tde-20210729-131755
Documento
Autor
Nombre completo
Estela Maris Rodrigues
Dirección Electrónica
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Paulo, 2003
Director
Título en portugués
Algoritmos para comparação de árvores filogenéticas e o problema dos pontos de recombinação
Palabras clave en portugués
Teoria Dos Grafos
Resumen en 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 en inglés
not available
Resumen en inglés
not available
 
ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
Fecha de Publicación
2021-07-29
 
ADVERTENCIA: Aprenda que son los trabajos derivados haciendo clic aquí.
Todos los derechos de la tesis/disertación pertenecen a los autores
CeTI-SC/STI
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2023. Todos los derechos reservados.