Á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 (taxons) 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 busca 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. Palavras-chave: Filogenia, Árvores Filogenéticas, Biologia Computacional, Otimização Combionatória, Algoritmos e Heurísticas.
Abstract:
Ver documento original.
Tipo do Trabalho:
Tese
Referência:
Viana, Gerardo Valdisio Rodrigues. Técnicas para construção de árvores filogenéticas. 2007. 176 f. Tese (Doutorado em 2007) - Universidade Estadual do Ceará, , 2007. Disponível em: Acesso em: 27 de abril de 2024
Universidade Estadual do Ceará - UECE | Departamento de Tecnologia da Informação e Comunicação - DETIC
Política de Privacidade e Segurança Build 1
