Search

Orientador: João Meidanis Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Reconstrução filogenética é o campo da Biologia Computacional dedicado a inferir um histórico evolutivo a partir de dados biológicos do presente. Nesta tese de doutorado, apresentamos três trabalhos sobre diferentes problemas relacionados ao tema. O primeiro visa reconstruir o ancestral comum a três genomas de entrada. Apesar da entrada aparentemente limitada, este problema pode ser aplicado para determinar ancestrais em árvores de topologia já conhecida. Nosso trabalho introduz uma forma de representar genomas através de matrizes. A partir disto, definimos o problema da mediana de matrizes, que, dadas três matrizes A, B e C, consiste em encontrar uma matriz M que minimize a soma d(A,M) + d(B,M) + d(C,M), onde d(X,Y) é o posto da matriz Y-X. Para resolver tal problema, apresentamos um algoritmo aproximado que garante resultados no mínimo tão bons quanto um dos genomas de entrada, mas que, em experimentos simulando a evolução de genomas, teve resultados muito mais próximos do ótimo. Além disso, mostramos também uma heurística que traduz uma matriz qualquer, como a resultante do nosso algoritmo, de volta para um genoma. No segundo, o objetivo é reconstruir genomas ancestrais a partir dos históricos evolutivos de suas famílias de genes. Para isto, estendemos o esquema de programação dinâmica do software DeCo, que constrói florestas retratando a evolução de adjacências. Nossa implementação, em vez de escolher apenas as adjacências de uma solução mais parcimoniosa, explora todo o espaço de soluções, escolhendo adjacências em função da sua maior frequência. Com esta abordagem, conseguimos reduzir significativamente o número de inconsistências ao avaliar múltiplas instâncias sobre os mesmos genes. Finalmente, discutimos uma ferramenta capaz de auxiliar na reconstrução de genomas ancestrais, considerando os genomas de espécies descendentes e sem a necessidade dos históricos de todas as famílias de genes. Esta ferramenta é a estrutura de dados chamada árvore PQR, que não só detecta se a entrada tem a propriedade dos uns consecutivos, como também indica os obstáculos que possivelmente impedem a instância de ter a propriedade. Isto é importante porque, ao reconstruir genomas ancestrais, erros na entrada são muito comuns e podem muito facilmente impedir a instância de ter a propriedade dos uns consecutivos. Aqui, consolidamos o conhecimento sobre os algoritmos online e offline para árvores PQR em um único artigo. Com isto, avançamos em três diferentes direções o conhecimento nas áreas de Reconstrução Filogenética e de Biologia Computacional Abstract: Phylogenetic reconstruction is the field of computational biology dedicated to infer evolutionary history from given extant biologic data. In this PhD thesis, we present three works on different issues related to the topic. The first aims to reconstruct the common ancestor to three input genomes. Despite the apparently limited input, this problem can be applied to determine ancestors in trees whose topology is already known. Our work introduces a way to represent genomes using matrices. From this, we define the matrix median problem, which consists of, given three matrices A, B and C, find a matrix M that minimizes the sum d(A,M) + d(B,M) + d(C,M), where d(X,Y) is the rank of the matrix Y-X. To solve this problem, we present an approximate algorithm that ensures results at least as good as one of the input genomes, but that, in the experiments simulating the evolution of genomes, got much closer to optimal results. Furthermore, we also show a heuristic that translates any matrix, like the ones returned by our algorithm, back to a genome. In the second, the goal is to reconstruct ancestral genomes from the evolutionary histories of their respective gene families. For this, we extend the dynamic programming scheme of DeCo, that builds forests depicting the evolution of adjacencies. Our implementation, instead of choosing just the adjacencies of one most parsimonious solution, explores the entire solution space, choosing adjacencies in function of their larger frequency. Using this approach, we managed significantly reduce the number of inconsistencies while evaluating multiple instances on the same genes. Finally, we discuss a tool to assist in the reconstruction of ancient genomes, considering the genomes of descendant species, without the need for the histories of all the gene families. This tool is the data structure called PQR-tree, which not only detects whether the entry has the consecutive ones property, but also the obstacles that possibly prevent the instance from having said property. This is important because, while reconstructing ancient genomes, entry errors are very common and can very easily prevent the instance from having the consecutive ones property. Here, we consolidate the knowledge on the online and offline algorithms for PQR trees in a single paper. With these, we moved knowledge in phylogenetic reconstruction and computational biology forward in three different directions Doutorado Ciência da Computação Doutor em Ciência da Computação CAPES FAPESP 2012/13865-7, 2013/07868-6

Orientador: João Meidanis Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: As árvores PQR são estruturas de dados usadas para tratar o problema dos uns consecutivos e problemas relacionados. Aplicações incluem reconhecimento de grafos de intervalos, de grafos planares, e problemas envolvendo moléculas de DNA. A presente dissertação busca consolidar o conhecimento sobre árvores PQR e, principalmente, sua construção incremental, visando fornecer uma base teórica para o uso desta estrutura em aplicações. Este trabalho apresenta uma descrição detalhada do projeto do algoritmo para construção online de árvores PQR, partindo de uma implementação inocente das operações sugeridas e refinando sucessivamente o algoritmo até alcançar a complexidade de tempo quase-linear. Neste projeto, lidamos com um obstáculo que surge com a utilização de estruturas de union-find que não havia sido tratado anteriormente. A demonstração da complexidade de tempo do algoritmo apresentada aqui também é nova e mais clara. Além disso, o projeto é acompanhado de uma implementação em Java dos algoritmos descritos Abstract: PQR trees are data structures used to solve the consecutive ones problem and other related problems. Applications include interval or planar graph recognition, and problems involving DNA molecules. This dissertation aims at consolidating existing and new knowledge about PQR trees and, primarily, their online construction, thus providing a theoretical basis for the use of this structure in applications. This work presents a detailed description of the online PQR tree construction algorithm's design, starting with a naive implementation of the suggested operations and refining them successively, culminating with an almost-linear time complexity. In this project, we dealt with an obstacle that arises with the use of union-find structures and that has never been addressed before. The proof presented here for the time complexity is also novel and clearer. Furthermore, the project is accompanied by a Java implementation of all the algorithms described Mestrado Ciência da Computação Mestre em Ciência da Computação

Agradecimentos: J.P.P.Z. visit to Simon Fraser University was funded by the São Paulo Research Foundation (FAPESP) Abstract: The reconstruction of evolutionary scenarios for whole genomes in terms of genome rearrangements is a fundamental problem in evolutionary and comparative genomics. The DeCo algorithm, recently introduced by Bérard et al., computes parsimonious evolutionary scenarios for gene adjacencies, from pairs of reconciled gene trees. However, as for many combinatorial optimization algorithms, there can exist many co-optimal, or slightly sub-optimal, evolutionary scenarios that deserve to be considered. We extend the DeCo algorithm to sample evolutionary scenarios from the whole solution space under the Boltzmann distribution, and also to compute Boltzmann probabilities for specific ancestral adjacencies. We apply our algorithms to a dataset of mammalian gene trees and adjacencies, and observe a significant reduction of the number of syntenic conflicts observed in the resulting ancestral gene adjacencies FUNDAÇÃO DE AMPARO À PESQUISA DO ESTADO DE SÃO PAULO - FAPESP Aberto