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: Celmar Guimarães da Silva Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Tecnologia Resumo: Matrizes são estruturas subjacentes a diferentes tipos de visualização de dados, como por exemplo, heatmaps. Diferentes algoritmos possibilitam uma permutação automática de suas linhas e colunas para prover um melhor entendimento visual, procurando agrupar linhas e colunas similares e evidenciar padrões. Trabalhos anteriores testaram e compararam alguns desses algoritmos em matrizes de dados binários, obtendo bons resultados o algoritmo PQR-Sort with Sorted Restrictions, em termos de tempo de execução e qualidade da reordenação em alguns tipos de matrizes. Contudo, este algoritmo não foi estendido para trabalhar com matrizes de dados quantitativos. Dessa forma, como continuidade desses trabalhos, este projeto testa a hipótese de que é possível elaborar variações do algoritmo PQR-Sort with Sorted Restrictions capazes de reordenar matrizes de dados quantitativos, e cuja eficiência de tempo e de qualidade da reordenação supere algoritmos de mesmo propósito. Neste projeto, foram elaborados os algoritmos Smoothed Multiple Binarization (SMB) e Multiple Binarization (MB). Ambos utilizam criação de vetores característicos (para descoberta de padrões canônicos de dados), árvores PQR e binarização de matrizes para sua reordenação. O SMB possui um potencial para prover boas reordernações de matrizes que contenham ruídos, pois faz o tratamento destes ruídos no conjunto de dados. Esses algoritmos foram testados e comparados com o Multidimensional Scaling (MDS) e algoritmo de Sugiyama adaptado (heurística baricêntrica), em termos de qualidade de reordenação e tempo de execução sobre matrizes sintéticas com os padrões canônicos Simplex, Band, Circumplex e Equi. Os resultados obtidos indicaram que os algoritmos SMB e MB destacaram-se dentre os demais pela capacidade de evidenciação do padrão Circumplex, e trouxeram resultados similares aos dos algoritmos testados para os padrões Equi e Band. Os resultados também indicam que SMB e MB são, em média, 3 e 6 vezes mais rápidos que o MDS, respectivamente. Deste modo, o uso de SMB e MB torna-se atrativo para a reordenação de matrizes que evidenciem padrões Circumplex, Equi e Band Abstract: Matrices are structures underlying different types of data visualization, as heatmap. Different algorithms enable automatic permutation of their rows and columns to provide a better visual understanding, aiming to group similar rows and columns and show patterns. Earlier work tested and compared some of these algorithms on binary data matrices, and revealed that PQR-Sort with Sorted Restrictions algorithm returned good results in terms of runtime and quality of reordered matrix. However, this algorithm was not extended for quantitative data matrices. Thus, as a continuation of these studies, this project aims to test the hypothesis that it is possible to develop variations of the PQR-Sort with Sorted Restrictions algorithm able to reorder quantitative data matrices, and whose quality of results and time efficiency surpasses algorithms that have the same purpose. In this work, it was elaborated the Smoothed Multiple Binarization (SMB) and Multiple Binarization (MB). Both use feature selection (to discovering canonical pattern of data), PQR Tree and binary matrices for their reordering. SMB algorithm has a potential to provide good matrices reordering with noise, because it does the noise treatment in data sets. These algorithms were tested and compared with Multidimensional Scaling (MDS) and Adapted Sugiyama (or Barycentric Heuristic) algorithms, in terms of quality of reordering and runtime on synthetics matrices with the canonical patterns Simplex, Band, Circumplex and Equi. The results indicated that SMB and MB algorithms stood out from the others by capacity of highlight Circumplex pattern, besides showing that may to obtain similar results to MDS and Adapted Sugiyama for Equi and Band patterns. Furthermore, SMB and MB were, on average, 3 and 6 times faster than MDS, respectively. Thus, the use of the SMB and MB algorithms can be attractive for matrices reordering that evidence Circumplex, Equi and Band patterns Mestrado Tecnologia e Inovação Mestre em Tecnologia