Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2007. / Submitted by Aline Jacob (alinesjacob@hotmail.com) on 2010-01-13T23:42:24Z No. of bitstreams: 1 2007_RichardsonSilvaLima.pdf: 1732822 bytes, checksum: f5a18335dd0187afe34cc7fd5204096d (MD5) / Approved for entry into archive by Daniel Ribeiro(daniel@bce.unb.br) on 2010-01-14T21:40:01Z (GMT) No. of bitstreams: 1 2007_RichardsonSilvaLima.pdf: 1732822 bytes, checksum: f5a18335dd0187afe34cc7fd5204096d (MD5) / Made available in DSpace on 2010-01-14T21:40:01Z (GMT). No. of bitstreams: 1 2007_RichardsonSilvaLima.pdf: 1732822 bytes, checksum: f5a18335dd0187afe34cc7fd5204096d (MD5) Previous issue date: 2007-06-29 / Projetos de seqüenciamento de genomas obtêm as bases que compõem seqüências biológicas de um organismo, de tal forma que suas funções possam ser inferidas. As inferências de funções biológicas constituem uma das tarefas mais importantes destes projetos, as quais são realizadas na fase de anotação. Existem softwares} e bases de dados que podem auxiliar os biólogos a realizar esta tarefa com uma maior acurácia e eficiência. Esta etapa é chamada de anotação automática. Os biólogos decidem as funções biológicas ou classificações das seqüências, com base nos seus conhecimentos biológicos. Esta etapa é chamada de anotação manual. Sistemas Multiagente possuem uma arquitetura própria onde agentes inteligentes ou entidades autônomas interagem entre si de maneira cooperativa, compartilhando um objetivo comum ou agindo de acordo com seus objetivos individuais. Neste contexto, este trabalho propõe um sistema baseado na abordagem de Sistema Multiagente para apoiar o processo de anotação manual. A arquitetura do sistema provê a combinação de diferentes agentes, de tal forma que estes interajam entre si e com o ambiente, cooperando de forma a sugerir anotações manuais que deverão ser validadas pelos biólogos. Um protótipo, denominado BioAgents, foi desenvolvido sob uma arquitetura multiagente com abordagem blackboard a fim de validar a proposta. Como estudo de caso, aplicamos o BioAgents em dois projetos de seqüenciamento de genomas, cujo processamento foi realizado pelo Laboratório de Bioinformática do Instituto de Biologia da UnB, a saber: Projeto Genoma Funcional e Diferencial do Paracoccidioides brasilienses (Projeto Genoma Pb) e o Projeto Genoma Funcional e Genética Genômica de Paullinia cupana (Projeto Genoma Guaraná). ________________________________________________________________________________________ ABSTRACT / Genome sequencing projects provide the basis to form the biological sequences of an organism, in such a away that their functions can be inferred. The biological function inferences constitute one of the most important tasks of these projects, which is carried through the annotation phase. There are softwares and databases that can help the biologists through with improved accuracy and e±ciency. This task is called automatic annotation. The biologists decide the biological functions or the classi¯cation of the sequences based on their own biological knowledge. This task is called manual annotation. Multiagent Systems provide an architecture where intelligent agents or auto- nomous entities interact with each other in a cooperative way, where they can share a common goal or act according to their own interests. This work presents a system based on the Multiagent System approach to support the process of manual annotation. The architecture of the system provides the combination of di®erent agents, in such a way that these agents must interact among themselves and with the environment, suggesting annotations that will be later validated by the biologists. A prototype called BioAgents was developed under a multiagent architecture according to a blackboard approach in order to validate the proposal. Two study cases were developed applying the BioAgents in two genome sequen- cing projects of the Bioinformatics Laboratory of the Biology Institute of UnB - The Paracoccidioides brasilienses Functional and Di®erential Genome Project (Genome Pb Project) and The Paullinia cupana Functional and Genome Genetic Project (Genome Guaraná Project).

Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, Programa de Pós-Graducação em Informática, 2016. / Submitted by Albânia Cézar de Melo (albania@bce.unb.br) on 2016-04-20T13:39:42Z No. of bitstreams: 1 2016_LucasAngeloSilveira.pdf: 3262689 bytes, checksum: 37ca4daf6eff5634ec889a6a015bbd81 (MD5) / Approved for entry into archive by Raquel Viana(raquelviana@bce.unb.br) on 2016-05-30T17:25:56Z (GMT) No. of bitstreams: 1 2016_LucasAngeloSilveira.pdf: 3262689 bytes, checksum: 37ca4daf6eff5634ec889a6a015bbd81 (MD5) / Made available in DSpace on 2016-05-30T17:25:56Z (GMT). No. of bitstreams: 1 2016_LucasAngeloSilveira.pdf: 3262689 bytes, checksum: 37ca4daf6eff5634ec889a6a015bbd81 (MD5) / Translocações são usadas para mensurar a distância evolutiva entre espécies. Do ponto de vista biológico dois tipos de genomas tem recebido atenção: genomas com e sem sinal. Ao considerar genomas com sinal, computar a distância mínima de translocações é linear enquanto que o caso sem sinal é NP-difícil. Propõem-se algoritmos genéticos (AGs) para resolver o problema de distância de translocação entre genomas sem sinal. A abordagem, consiste em utilizar uma população composta por indivíduos representando genomas com sinal obtidos de um genoma sem sinal provido como entrada. A solução de cada indivíduo é também uma solução admissível para o genoma dado. A função de aptidão utilizada, que é a distância para genomas com sinal, é computada linearmente com um algoritmo proposto por Bergeron et al. O AG baseado nessa abordagem foi aprimorado com duas técnicas de otimização: memética e aprendizagem baseada em oposição. Além disso, foram propostas paralelizações do AG memético buscando diminuir o tempo de processamento assim como melhorar a precisão. A qualidade dos resultados foi validada utilizando uma implementação de um algoritmo de raio de aproximação 1.5+" recentemente proposto por Cui et al. Experimentos foram realizados tomando como entrada genomas sintéticos e gerados a partir de dados biológicos. Os AGs forneceram melhores resultados que o algoritmo de controle de qualidade. As paralelizações apresentaram melhoras tanto no tempo de execução quanto na precisão dos resultados. Utilizou-se o teste de hipóteses de Wilcoxon a fim de verificar a significância estatística das melhorias fornecidas pelos AGs aprimorados em relação àquelas fornecidas pelo AG básico. Desta análise foi possível identificar que o AG memético provê resultados diferentes (melhores) que o AG básico, e que este último e o AG com aprendizagem baseada em oposição não apresentam nenhuma diferença significativa. O teste foi também aplicado para comparar as soluções das paralelizações confirmando que existem aprimoramentos dos resultados comparados com o AG memético. _______________________________________________________________________________________________ ABSTRACT / Translocations are used to measure the evolutionary distance between species. From a biological point of view two types of genomes have received attention: signed and unsigned genomes. When considering signed genomes, the problem can be solved in linear time, while, in the case of unsigned genomes the problem was shown to be NP-hard. Genetic algorithms (GAs) are proposed to solve the translocation distance problem between unsigned genomes. The approach consists in using a population composed of individuals representing signed genomes obtained from a given unsigned genome provided as input. The solution of each individual is also an admissible solution to the given genome. The fitness function used, which is the distance for signed genome, is computed linearly with an algorithm proposed by Bergeron et al. The GA based on this approach has been enhanced with two optimization techniques: memetic and opposition based learning. Also, parallelizations of the GA embedded with memetic were proposed seeking to improve both running time as the accuracy of results. The quality of the results was verified using an implementation of a 1.5+"-approximation algorithm recently proposed by Cui et al. Experiments were performed taking as input synthetic genomes and genomes generated from biological data. The GAs provided better results than the quality control algorithm. The parallelizations showed improvements both regarding runtime as well as accuracy. A statistical analysis based on the Wilcoxon test was performed to check if the improvements in the solutions provided by enhanced GAs compared to those provided by the basic GA have some significance. This analysis can identify that the GA embedded with the technical memetic provides different (better) results than GA and that the results provided by the GA embedded with opposition based learning presents no significant difference. The test was also performed to compare the solutions of the parallelizations confirming that there are improvements of the results regarding the GA embedded memetic.