Algoritmos para comparação de árvores filogenéticas e o problema dos pontos de recombinação

• Ano de defesa: 2003
• Autor(a) principal: Rodrigues, Estela Maris
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Biblioteca Digitais de Teses e Dissertações da USP
• Palavras-chave em Português: Teoria Dos Grafos
• Link de acesso: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-131755/

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