FundaÃÃo Cearense de Apoio ao Desenvolvimento Cientifico e TecnolÃgico / Phylogenetic tree structures express similarities, ancestrality, and relationships between species
or group of species, and are also known as evolutionary trees or phylogenies. Phylogenetic
trees have leaves that represent species (taxons), and internal nodes that correspond to hypothetical
ancestors of the species. In this thesis we rst present elements necessary to the
comprehension of phylogenetic trees systematics, then efcient algorithms to build them will
be described. Molecular biology concepts, life evolution, and biological classication are important
to the understanding of phylogenies. Phylogenetic information may provide important
knowledge to biological research work, such as, organ transplantation from animals, and drug
toxicologic tests performed in other species as a precise prediction to its application in human
beings. To solve a phylogeny problem implies that a phylogenetic tree must be built from
known data about a group of species, according to an optimization criterion. The approach to
this problem involves two main steps: the rst refers to the discovery of perfect phylogenies, in
the second step, information extracted from perfect phylogenies are used to infer more general
ones. The techniques that are used in the second step take advantage of evolutionary hypothesis.
The problem becomes NP-hard for a number of interesting hypothesis, what justify the use of
inference methods based on heuristics, metaheuristics, and approximative algorithms. The description
of an innovative technique based on local search with multiple start over a diversied
neighborhood summarizes our contribution to solve the problem. Moreover, we used parallel
programming in order to speed up the intensication stage of the search for the optimal solution.
More precisely, we developed an efcient algorithm to obtain approximate solutions for a
phylogeny problem which infers an optimal phylogenetic tree from characteristics matrices of
various species. The designed data structures and the binary data manipulation in some routines
accelerate simulation and illustration of the experimentation tests. Well known instances have
been used to compare the proposed algorithm results with those previously published. We hope
that this work may arise researchers' interest to the topic and contribute to the Bioinformatics
area. / Ãrvores filogenÃticas sÃo estruturas que expressam a similaridade, ancestralidade e relacionamentos entre as espÃcies ou grupo de espÃcies. Conhecidas como Ãrvores evolucionÃrias ou simplesmente filogenias, as Ãrvores filogenÃticas possuem folhas que representam as espÃcies (tÃxons) e nÃs internos que correspondem aos seus ancestrais hipotÃticos. Neste trabalho, alÃm das informaÃÃes necessÃrias para o entendimento de toda a sistemÃtica filogenÃtica, sÃo apresentadas tÃcnicas algorÃtmicas para construÃÃo destas Ãrvores. Os conceitos bÃsicos de biologia molecular, evoluÃÃo da vida e classificaÃÃo biolÃgica, aqui descritos, permitem compreender o que à uma Filogenia e qual sua importÃncia para a Biologia. As informaÃÃes filogenÃticas fornecem,por exemplo, subsÃdios importantes para decisÃes relativas aos transplantes de ÃrgÃos ou tecidos de outras espÃcies para o homem e para que testes de reaÃÃo imunolÃgica ou de toxicidade sejam feitos antes em outros sistemas biolÃgicos similares ao ser humano. Resolver um Problema de Filogenia corresponde à construÃÃo de uma Ãrvore filogenÃtica a partir de dados conhecidos sobre as espÃcies em estudo, obedecendo a algum critÃrio de otimizaÃÃo. A abordagem dada a esse problema envolve duas etapas, a primeira, referente aos casos em que as filogenias sÃo perfeitas cujos procedimentos desenvolvidos serÃo utilizados na segunda etapa, quando deve ser criada uma tÃcnica de inferÃncia para a filogenia num caso geral. Essas tÃcnicas consideram de forma peculiar as hipÃteses sobre o processo de evoluÃÃo. Para muitas hipÃteses de interesse o problema se torna NP-DifÃcil, justificando-se o uso de mÃtodos de inferÃncia atravÃs de heurÃsticas, meta-heurÃsticas e algoritmos aproximativos. Nossa contribuiÃÃo neste trabalho consiste em apresentar uma tÃcnica de resoluÃÃo desse problema baseada em buscas locais com partidas mÃltiplas em vizinhanÃas diversificadas. Foi utilizada a programaÃÃo paralela para minimizar o tempo de execuÃÃo no processo de intensificaÃÃo da busca pela soluÃÃo Ãtima do problema. Desta forma, desenvolvemos um algoritmo para obter soluÃÃes aproximadas para um Problema da Filogenia, no caso, para inferir, a partir de matrizes de caracterÃsticas de vÃrias espÃcies, uma Ãrvore filogenÃtica que mais se aproxima da histÃria de sua evoluÃÃo. Uma estrutura de dados escolhida adequadamente aliada à manipulaÃÃo de dados em binÃrio em algumas rotinas facilitaram a simulaÃÃo e ilustraÃÃo dos testes realizados. InstÃncias com resultados conhecidos na literatura foram utilizadas para comprovar a performance do algoritmo. Esperamos com este trabalho despertar o interesse dos pesquisadores da Ãrea de ComputaÃÃo, consolidando, assim, o crescimento da BioinformÃtica.
| Identifer | oai:union.ndltd.org:IBICT/oai:www.teses.ufc.br:1188 |
| Date | 27 April 2007 |
| Creators | Gerardo ValdÃso Rodrigues Viana |
| Contributors | Fernando Antonio de Carvalho Gomes, Carlos Eduardo Ferreira, Tarcisio Haroldo Cavalcante Pequeno, Thalles Barbosa Granjeiro, Nelson Maculan Filho, Ruy Luiz Milidià |
| Publisher | Universidade Federal do CearÃ, Programa de PÃs-GraduaÃÃo em CiÃncia da ComputaÃÃo, UFC, BR |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFC, instname:Universidade Federal do Ceará, instacron:UFC |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.002 seconds