O problema reconstrução filogenética têm como objetivo determinar as relações evolutivas das espécies, usualmente representadas em estruturas de árvores. No entanto, esse problema tem se mostrado muito difícil uma vez que o espaço de busca das possíveis árvores é muito grande. Diversos métodos de reconstrução filogenética têm sido propostos. Vários desses métodos definem um critério de otimalidade para avaliar as possíveis soluções do problema. Porém, a aplicação de diferentes critérios resulta em árvores diferentes, inconsistentes entre sim. Nesse contexto, uma abordagem multi-objetivo para a reconstrução filogenética pode ser útil produzindo um conjunto de árvores consideradas adequadas por mais de um critério. Nesta tese é proposto um algoritmo evolutivo multi-objetivo, denominado PhyloMOEA, para o problema de reconstrução filogenética. O PhyloMOEA emprega os critérios de parcimônia e verossimilhança que são dois dos métodos de reconstru ção filogenética mais empregados. Nos experimentos, o PhyloMOEA foi testado utilizando quatro bancos de seqüências freqüentemente empregados na literatura. Para cada banco de teste, o PhyloMOEA encontrou as soluções da fronteira de Pareto que representam um compromisso entre os critérios considerados. As árvores da fronteira de Pareto foram validadas estatisticamente utilizando o teste SH. Os resultados mostraram que o PhyloMOEA encontrou um número de soluções intermediárias que são consistentes com as soluções obtidas por análises de máxima parcimônia e máxima verossimilhança realizados separadamente. Além disso, os graus de suporte dos clados pertencentes às árvores encontradas pelo PhyloMOEA foram comparadas com a probabilidade posterior dos clados calculados pelo programa Mr.Bayes aplicados aos quatro bancos de teste. Os resultados indicaram que há uma relação entre ambos os valores para vários grupos de clados. Em resumo, o PhyloMOEA é capaz de encontrar uma diversidade de soluções intermediárias que são estatisticamente tão boas quanto as melhores soluções de máxima parcimônia e máxima verossimilhança. Tais soluções apresentam um compromisso entre os dois objetivos / The phylogeny reconstruction problem consists of determining the evolutionary relationships (usually represented as a tree) among species. This is a very complex problem since the tree search space is huge. Several phylogenetic reconstruction methods have been proposed. Many of them defines an optimality criterion for evaluation of possible solutions. However, different criteria may lead to distinct phylogenies, which often conflict with each other. In this context, a multi-objective approach for phylogeny reconstruction can be useful since it could produce a set of optimal trees according to mdifficultultiple criteria. In this thesis, a multi-objective evolutionary algorithm for phylogenetic reconstruction, called PhyloMOEA, is proposed. PhyloMOEA uses the parsimony and likelihood criteria, which are two of the most used phylogenetic reconstruction methods. PhyloMOEA was tested using four datasets of nucleotide sequences found in the literature. For each dataset, the proposed algorithm found a Pareto front representing a trade-off between the used criteria. Trees in the Pareto front were statistically validated using the SH-test, which has shown that a number of intermediate solutions from PhyloMOEA are consistent with solutions found by phylogenetic methods using one criterion. Moreover, clade support values from trees found by PhyloMOEA was compared to clade posterior probabilities obtained by Mr.Bayes. Results indicate a correlation between these probabilities for several clades. In summary, PhyloMOEA is able to find diverse intermediate solutions, which are not statistically worse than the best solutions for the maximum parsimony and maximum likelihood criteria. Moreover, intermediate solutions represent a trade-off between these criteria
| Identifer | oai:union.ndltd.org:IBICT/oai:teses.usp.br:tde-02042008-142554 |
| Date | 11 February 2008 |
| Creators | Waldo Gonzalo Cancino Ticona |
| Contributors | Alexandre Cláudio Botazzo Delbem, André Carlos Ponce de Leon Ferreira de Carvalho, Roseli Aparecida Francelin Romero, Claudia Augusta de Moraes Russo, Ivan Nunes da Silva |
| Publisher | Universidade de São Paulo, Ciências da Computação e Matemática Computacional, USP, BR |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da USP, instname:Universidade de São Paulo, instacron:USP |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0022 seconds