Orientador: João Meidanis / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-04T09:01:04Z (GMT). No. of bitstreams: 1 Quitzau_JoseAugustoAmgarten_M.pdf: 2854625 bytes, checksum: 4e3e9cbba583ca76e69b4835f14dd8db (MD5) Previous issue date: 2005 / Resumo: A relação evolutiva entre especies de seres vivos e normalmente representada atraves de um diagrama conhecido como arvore filogenetica. Embora existam inumeros metodos de construção deste tipo de diagrama, com base nos mais variados tipos de dados biologicos, nenhum deles garante obter a arvore que melhor representa a relação evolutiva entre as especies de um conjunto. Alguns metodos ainda podem produzir varias arvores distintas para um mesmo conjunto, sendo incapazes de decidir qual a que melhor explica a relação entre os seres representados. Cabe então aos biologos comparar as arvores e decidir qual a melhor entre elas. Uma maneira de estudar semelhanças entre arvores construidas sobre um mesmo conjunto de especies e a utilização de um consenso entre as arvores. Atualmente existem diversos metodos de consenso, cada um enfatizando características diferentes do conjunto de arvores. Esta dissertação destaca a possibilidade de uso de metodos de consenso como metodos de construção, apresentando um teste bastante simples que ressalta a qualidade das arvores consenso em relação a arvores criadas pelos metodos tradicionais de construção de arvores filogeneticas. Alem disso, apresenta um novo metodo de consenso focado não na comparação de arvores, mas na construção de uma arvore filogenetica capaz de se aproximar mais da arvore correta do que a maior parte das arvores presentes no conjunto utilizado para construi-la / Abstract: The evolutionary relationship between species is usually represented by a diagram known as phylogenetic tree. Despite of the existence of a huge number of different methods for building such a diagram, based on the most diverse sorts of biological data, none of these methods guarantees that the reconstructed tree is the tree which represents better the evolutionary relationship between the species in a given set. Some of the methods may even build different trees for the same input set of species. In these cases, they are unable to decide which of the trees represents better the relationship between the considered beings. In such cases, the task of comparing the produced trees and choosing the best one is left to biologists. One way to study the similarity of phylogenetic trees is to build a consensus between them. Nowadays there are different consensus methods, each of them exploring a different characteristic of the set of trees. This work focus on the possibility of use of consensus methods as reconstruction methods, presenting a very simple test, which points out the quality of consensus trees compared to trees built by traditional phylogeny reconstruction methods. After this, we present a consensus method dedicated to reconstructing trees, instead of just comparing them. We also show that trees built by this method are usually closer to the true tree than most trees used to build them / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientador: Fernando Jose Von Zuben / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-12T21:45:18Z (GMT). No. of bitstreams: 1 Silva_AnaEstelaAntunesda_D.pdf: 8601078 bytes, checksum: 494abd829c21ee91c2a7003c33fdf0a1 (MD5) Previous issue date: 2007 / Resumo : A reconstrução de árvores filogenéticas pode ser interpretada como um processo sistemático de proposição de uma descrição arbórea para as diferenças relativas que se observam em conjuntos de atributos genéticos homólogos de espécies sob comparação. A árvore filogenética resultante apresenta uma certa topologia, ou padrão de ancestralidade, e os comprimentos dos ramos desta árvore são indicativos do número de mudanças evolutivas desde a divergência do ancestral comum. Tanto a topologia quanto os comprimentos de ramos são hipóteses descritivas de eventos não-observáveis e condicionais, razão pela qual tendem a existir diversas hipóteses de alta qualidade para a reconstrução, assim como múltiplos critérios de desempenho. Esta tese (i) aborda árvores sem raiz; (ii) enfatiza os critérios de quadrados mínimos, evolução mínima e máxima verossimilhança; (iii) propõe uma extensão ao algoritmo Neighbor Joining que oferece múltiplas hipóteses de alta qualidade para a reconstrução; e (iv) descreve e utiliza uma nova ferramenta para otimização multiobjetivo no contexto de reconstrução filogenética. São considerados dados artificiais e dados reais na apresentação de resultados, os quais apontam vantagens e aspectos diferenciais das metodologias propostas / Abstract: The reconstruction of phylogenetic trees can be interpreted as a systematic process of proposing an arborean description to the relative dissimilarities observed among sets of homologous genetic attributes of species being compared. The resulting phylogenetic tree presents a certain topology, or ancestrality pattern, and the length of the edges of the tree will indicate the number of evolutionary changes since the divergence from the common ancestor. Both topology and edge lengths are descriptive hypotheses of non-observable and conditional events, which implies the existence of diverse high-quality hypotheses for the reconstruction, as long as multiple performance criteria. This thesis (i) deals with unrooted trees; (ii) emphasizes the least squares, minimum evolution, and maximum likelihood criteria; (iii) proposes an extension to the Neighbor Joining algorithm which offers multiple high-quality reconstruction hypotheses; and (iv) describes and uses a new tool for multiobjective optimization in the context of phylogenetic reconstruction. Artificial and real datasets are considered in the presentation of results, which points to some advantages and distinctive aspects of the proposed methodologies / Doutorado / Engenharia de Computação / Doutor em Engenharia Elétrica

Orientador: André Santanchè / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-21T20:20:46Z (GMT). No. of bitstreams: 1 Bernardo_IvelizeRocha_M.pdf: 1642753 bytes, checksum: 79818a62ab275ff01db056b803beb9b6 (MD5) Previous issue date: 2012 / Resumo: A flexibilidade proporcionada por planilhas eletrônicas possibilita sua customização seguindo modelos mentais de seus autores e as tornam sistemas populares de gerenciamento de dados. Gradativamente tem crescido a necessidade de se integrar e articular dados de diferentes planilhas e, para que máquinas possam auxiliar neste processo, o desafio é como interpretar automaticamente o seu esquema implícito, que é dirigido à interpretação humana. Alguns trabalhos propõem o mapeamento do conteúdo das planilhas para padrões abertos de interoperabilidade, principalmente aqueles da Web Semântica. A principal limitação destes trabalhos consiste no pressuposto de que é possível reconhecer e explicitar os esquemas e a semântica das planilhas automaticamente, independentemente do seu domínio. Este trabalho se diferencia por considerar o contexto e o domínio em que foram concebidas as planilhas essenciais para se traçar o conjunto de práticas compartilhadas pela comunidade em questão, que estabelece padrões de construção a serem reconhecidos automaticamente por nosso sistema, em um processo de extração de dados e explicitação de esquemas. Nossa proposta envolve uma estratégia para caracterização de padrões de construção associados a modelos conceituais de autores na construção de planilhas, que é resultado de uma ampla pesquisa de práticas compartilhadas por autores de planilhas no domínio de uso da Biologia. Neste documento apresentamos o resultado de um experimento prático envolvendo tal sistema, no qual integramos os dados de centenas de planilhas eletrônicas disponíveis na Web. Tal integração foi possível pela capacidade única de nossa abordagem de reconhecer a natureza da planilha analisada dentro de seu contexto de criação / Abstract: The flexibility provided by spreadsheets allows their customization following mental models of their authors and makes them popular data management systems. Gradually there is a growing need of integrating and join data from different spreadsheets and, to enable machines assistance in this process, the challenge is how to automatically interpret their implicit schema, which is addressed to human interpretation. In this sense, some related works propose mapping spreadsheets contents to open interoperability standards, mainly Semantic Web standards. The main limitation of such proposals is the assumption that it is possible to recognize and make explicit the schema and the semantics of spreadsheets automatically apart from their domain. This work differs by assuming the essential role of the context and the domain in which the spreadsheet was conceived to delineate shared practices of the community, which establishes building patterns to be automatically recognized by our system, in data extraction process and schema recognition. Our proposal involves a strategy to characterize building patterns related to conceptual models of authors in spreadsheets building process, which results from an extensive research of practices shared among authors of spreadsheets in the Biology usage domain. In this document we present a result of a practical experiment involving such a system, in which we integrated data from hundreds of spreadsheets available on the Web. This integration was possible due to a unique ability of our approach of recognizing the spreadsheet nature analyzed inside its creation context / Mestrado / Ciência da Computação / Mestra em Ciência da Computação