Search

Orientador: João Meidanis Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Não informado. Abstract: Not informed. Doutorado Doutor em Ciência da Computação

Orientadores: Zanoni Dias, Ulisses Martins Dias Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: A genômica comparativa é um campo de pesquisa da biologia com foco na comparação de características genéticas entre organismos. Dentre as características genéticas comumente utilizadas, podemos citar a sequência de genes dos genomas. O número de mutações genéticas capazes de transformar uma sequência genética em outra é uma das métricas amplamente utilizada para a comparação de dois genomas. Os rearranjos de genoma são eventos mutacionais que podem afetar grandes trechos de um genoma. A reversão e a transposição são dois dos eventos de rearranjo mais estudados na literatura. Uma reversão inverte um segmento do genoma, enquanto uma transposição troca a posição de dois segmentos adjacentes. Um modelo de rearranjo determina o conjunto de eventos de rearranjo que podem ser utilizados para transformar um genoma em outro. Os primeiros estudos apresentaram resultados considerando modelos de rearranjo constituídos exclusivamente por um único tipo de evento de rearranjo. Estudos posteriores apresentaram resultados considerando modelos de rearranjo compostos por múltiplos tipos de eventos de rearranjo. Quando consideramos apenas o número de eventos de rearranjo necessários para transformar um genoma em outro, assumimos que cada evento tem a mesma probabilidade de ocorrer em um cenário evolutivo, sendo essa abordagem chamada de não ponderada. No entanto, quando assumimos que determinados tipos de eventos ocorrem mais do que outros, é possível atribuir um custo a cada tipo de evento de rearranjo. Nessa nova versão, o objetivo do problema consiste em buscar uma sequência de eventos de rearranjo que transforme um genoma em outro com custo mínimo, sendo essa abordagem chamada de ponderada. Nesta tese, apresentamos uma abordagem que considera uma proporção mínima entre a quantidade de eventos de reversão e o tamanho da sequência de eventos de rearranjo que transforma um genoma em outro. Nós mostramos que a abordagem de proporção naturalmente contorna problemas que podem surgir adotando uma abordagem ponderada ou não ponderada. Além disso, realizamos uma análise de complexidade do problema e apresentamos algoritmos de aproximação com fatores constantes. Estudos têm destacado a importância da informação presente nas regiões intergênicas, que são estruturas presentes entre cada par de genes e nas extremidades de um genoma, e que podem levar a modelos mais realistas considerando um contexto evolutivo. O tamanho de cada região intergênica é dado pelo número de nucleotídeos presentes nela. Desde então, foram apresentados estudos considerando tanto a sequência de genes quanto o tamanho das regiões intergênicas para representar um genoma. Nesta tese, mostramos resultados nesse mesmo contexto, mas consideramos diferentes modelos de rearranjo. Além disso, introduzimos uma generalização dos problemas possibilitando atribuir um grau de flexibilidade em relação ao tamanho das regiões intergênicas desejadas no genoma alvo. Para ambos os casos, realizamos uma análise de complexidade dos problemas, desenvolvemos algoritmos e conduzimos experimentos para verificar o desempenho prático Abstract: Comparative genomics is a field of research in biology focusing on comparing genetic features between organisms. Among the genetic features commonly used, we can mention the sequence of genes in genomes. The number of genetic mutations capable of transforming one gene sequence into another is a widely used metric to compare genomes. Genome rearrangement events are mutational events that can affect large stretches of a genome. Reversal and transposition are two of the most studied rearrangement events in the literature. A reversal inverts a genome segment, while a transposition exchanges the position of two adjacent segments. A rearrangement model determines the set of rearrangement events that can be used to transform one genome into another. Early studies presented results considering a rearrangement model consisting exclusively of a single type of rearrangement event. However, subsequent studies presented results considering rearrangement models composed of multiple rearrangement events. When we consider only the number of rearrangement events that are required to transform one genome into another, we assume that each event has the same probability of occurring in an evolutionary scenario; this is called the unweighted approach. However, when we want certain types of events to occur more than others, it is possible to assign a cost to each type of rearrangement event. The problem goal changes to search for a sequence of rearrangement events that transforms one genome into another with minimal cost; this is called the weighted approach. In this work, we introduce an approach that considers a minimum proportion between the number of reversal events and the size of the rearrangement sequence that transforms one genome into another. We show that the proportion approach naturally overcomes problems that may arise by adopting a weighted or unweighted approach. In addition, we perform a complexity analysis of the problem and present approximation algorithms with constant factors. Another genetic feature that studies pointed out as relevant in a genetic comparison context is the intergenic regions, which are structures between each pair of genes and at the extremities of a genome. The size of each intergenic region is the number of nucleotides within it. Since then, studies were presented considering both the sequence of genes and the size of the intergenic regions to represent a genome. In this work, we show results in this same context but we consider different rearrangement models. In addition, we introduce a generalization of the problems such that it is possible to assign a degree of flexibility regarding the size of the intergenic regions desired in the target genome. For both cases, we conducted a complexity analysis of the problems, developed algorithms, and performed experiments to verify the practical performance Doutorado Ciência da Computação Doutor em Ciência da Computação CNPQ 140272/2020-8 CAPES 001

Orientador: Fernando Jose Von Zuben Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação 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: Zanoni Dias Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Neste trabalho, apresentamos três heurísticas para melhorar os resultados de algoritmos para o problema de Ordenação de Permutações com Sinais por Reversões e Transposições. Nossas heurísticas foram aplicadas tanto na versão clássica do problema quanto nas versões restrita a operações de prefixo e restrita a operações de prefixo ou sufixo. A nossa primeira heurística é chamada de Sliding Window, executa em tempo linear e fornece bons resultados. A nossa segunda heurística, Look Ahead, possui tempo de execução mais elevado dependendo do estimador de distância que é utilizado, mas seus resultados são mais expressivos. Nossa última heurística é chamada de Iterative Sliding Window e apresenta melhor custo-benefício entre o tempo de execução e a qualidade da solução em comparação com as duas primeiras heurísticas. Mostramos que as heurísticas Look Ahead e Sliding Window podem ser combinadas visando fornecer resultados ainda melhores. Para verificar o comportamento de nossas heurísticas, implementamos diversos algoritmos da literatura e realizamos experimentos práticos onde observamos melhorias em relação aos algoritmos originais. Efetuamos ainda um comparativo de desempenho entre nossas próprias heurísticas. Investigamos também o problema de Ordenação de Permutações com Sinais por Reversões e Transposições Ponderadas, adotando os pesos 2 e 3 para os eventos de reversão e transposição, respectivamente. Conseguimos apresentar limitantes inferiores para o problema e quatro algoritmos de aproximação. Dois desses algoritmos adotam uma estratégia gulosa e apresentam fatores de aproximação 3 e 2, enquanto os outros dois utilizam a estrutura de grafo de ciclos para ordenar a permutação e apresentam fatores de aproximação 5/3 e 3/2. Realizamos experimentos práticos com diferentes grupos de permutações com características distintas. Estendemos nossa investigação para considerar outras relações de peso entre os eventos de transposição e reversão. Mostramos também uma análise que considera essas relações distintas de peso e apresentamos o melhor fator de aproximação obtido para cada uma dessas relações Abstract: In this work, we present three heuristics to improve existing solutions for the Sorting Signed Permutations by Reversals and Transpositions problem. To assess the heuristics, we implemented algorithms described in the literature to provide initial solutions. We investigated the classical version of the problem as well as versions restricted to prefix operations and restricted to prefix or suffix operations. The first heuristic is called Sliding Window, it runs in linear time and provides good results. The second heuristic is called Look Ahead and showed remarkable results, but its execution time increases depending on the distance estimator used. Our last heuristic is called Iterative Sliding Window and it showed better results when we consider solution quality and execution time. We showed that the heuristics Look Ahead and Sliding Window can be combined to further improve the solutions. We performed the experiments and showed the improvement obtained by our heuristics compared with the solutions provided by the original algorithms. We also compared the three heuristics among themselves. We also investigated the Sorting Signed Permutations by Weighted Reversals and Weighted Transpositions problem using weights 2 and 3 for reversals and transpositions, respectively. We showed lower bounds and developed four approximation algorithms for the problem. Two of these algorithms use a strategy based on breakpoints and have approximation factors 3 and 2. The other two algorithms resort to a structure called cycle graph to sort the permutations and achieved the approximation factors 5/3 and 3/2. We executed these algorithms in five groups of permutations with different characteristics. To conclude this work, we made an analysis that considers different weights for reversal and transposition events and showed the best approximation factor obtained in each case Mestrado Ciência da Computação Mestre em Ciência da Computação CNPQ 138219/2016-8

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: Zanoni Dias Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Rearranjos de Genomas, diferentemente das mutações mais comuns que afetam pontualmente o genoma, são eventos de mutação globais que agem sobre grandes trechos do genoma, e são um desafio para a Teoria da Computação, uma vez que, na maioria dos casos, computar a distância entre dois genomas considerando operações globais resultam em problemas NP-Difíceis. De forma similar, podemos definir o Problema da Ordenação de Genomas, em que buscamos calcular o número mínimo de eventos de rearranjos necessários para ordenar blocos conservados de genomas, onde os genomas são representados por permutações. Um modelo de rearranjo determina quais eventos de rearranjo são permitidos para ordenar uma permutação ou transformar uma permutação em outra. Dentre os eventos de rearranjo mais comuns, podemos citar as reversões e as transposições. Modelos considerando os dois eventos, separadamente, já possuem vasta bibliografia. Entretanto, modelos considerando os dois eventos em conjunto ainda são pouco explorados. Nesta dissertação, apresentamos diversas heurísticas para ordenação de permutações por reversões e transposições considerando permutações com sinais e permutações sem sinais. Para tanto, diversas métricas compatíveis com o problema foram utilizadas em heurísticas, que mais tarde foram testadas com um grande conjunto de permutações aleatórias. As métricas que obtiveram os melhores resultados foram utilizadas em uma heurística denominada Heurística de Grafo de Ciclos. Além disso, foram criados bancos de configurações que auxiliam esta heurística no processo de ordenação de uma permutação. Os resultados obtidos pela Heurística de Grafo de Ciclos foram comparados com algoritmos já existentes na literatura, tanto os que permitem reversões e transposições, bem como os que consideram apenas um dos eventos, evidenciando que a Heurística de Grafo de Ciclos produz os melhores resultados para todos os conjuntos de permutações com sinais, e em grande parte dos conjuntos de permutações sem sinais Abstract: Genome rearrangements, unlike most common mutations that affects only one nucleotide, are global mutation events that affect large fragments of genomes and present a challenge to the Computational Theory Field, since in most cases, computing the distance between genomes considering global operations results in NP-Hard problems. Moreover, the Sorting Permutations by Genome Rearrangements problem seeks to compute the smallest number of rearrangement events needed to sort conserved blocks of genomes, with genomes represented by permutations. A rearrangement model determines which rearrangement events are allowed to sort a permutation or to transform a permutation into another. The two most common rearrangement events are reversals and transpositions. Rearrangement models considering reversals and transpositions separately have an extensive bibliography. However, models considering both events are still little explored. In this dissertation, we present some heuristics that sort permutations by reversals and transpositions considering signed and unsigned permutations. To do this, various metrics that are compatible with the problem were used. These heuristics were later tested with a large set of random permutations. Metrics that have achieved the best results were used in a heuristic named Cycle Graph Heuristic. In addition, cycle configurations were created and stored in a database in order to help our heuristic in the sorting process. The results obtained from Cycle Graph Heuristic were compared with existing algorithms in the literature, showing that our heuristic produces the best results for all sets of signed permutations and in many of the sets of unsigned permutations Mestrado Ciência da Computação Mestre em Ciência da Computação CNPQ 147337/2013-5

Orientadores: Zanoni Dias, Ulisses Martins Dias Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Rearranjos de Genomas são eventos que afetam longos trechos de um genoma durante a evolução. Dentre os rearranjos mais estudados, temos a reversão, que inverte a ordem e a orientação de um bloco consecutivo de genes, e a transposição, que troca a ordem relativa de dois blocos adjacentes. Modelos matemáticos vêm sendo utilizados para estimar a distância evolutiva entre diferentes organismos por rearranjos de genomas. A representação de um genoma se dá, na maioria das vezes, pela atribuição de um número único para cada gene e, ao supor que não existem genes repetidos, essa representação pode ser vista como uma permutação. Supondo que os dois genomas a serem comparados compartilham o mesmo conjunto de genes, calcular a distância evolutiva entre eles se torna o problema de encontrar o menor número de rearranjos necessários que transforma uma permutação em outra. Nesta tese, apresentamos diversos resultados envolvendo problemas de rearranjos de genomas: (i) provas de NP-dificuldade para quatro problemas cuja complexidade era desconhecida; (ii) um algoritmo polinomial exato para um problema cuja complexidade era desconhecida; e (iii) algoritmos de aproximação e provas de NP-dificuldade para problemas onde a representação dos genomas não considera apenas a ordem dos genes. Descrevemos estas contribuições com maior profundidade nos parágrafos a seguir. Dentre os problemas que envolvem rearranjos de genomas, existem quatro versões que permitem o uso de reversões e transposições ao mesmo tempo e que, apesar dos diversos algoritmos propostos nos últimos 20 anos, permaneciam com complexidade desconhecida. A primeira contribuição apresentada é a prova de NP-dificuldade desses quatro problemas. Uma das variações dos problemas de rearranjos de genomas consideram que cada rearranjo pode afetar apenas um pequeno número de genes, também conhecidos como rearranjos curtos e super curtos. Neste contexto, nossa segunda contribuição é a prova de que o único problema cuja complexidade era desconhecida envolvendo reversões super curtas e transposições super curtas admite um algoritmo polinomial exato. A grande maioria das abordagens em problemas de rearranjos existentes na literatura focaram apenas na ordem relativa dos genes de um genoma, desconsiderando outras características importantes existentes no genoma. Recentemente, pesquisadores mostraram que considerar as regiões existentes entre cada par de genes, chamadas de regiões intergênicas, pode resultar em melhores estimadores de distância em dados reais. Desta forma, nossa terceira contribuição investiga a incorporação das regiões intergênicas em modelos já existentes para reversões e transposições, tanto na abordagem sem restrições como na abordagem que considera apenas rearranjos super curtos, onde investigamos diversos algoritmos de aproximação para problemas que são NP-difíceis ou possuem complexidade desconhecida Abstract: Genome rearrangements are events that affect large stretches of a genome during evolution. Two of the most studied rearrangements are reversals, which reverses the order and orientation of a consecutive block of genes, and transpositions, which exchanges the relative order of two adjacent blocks. Mathematical models have been used to estimate the evolutionary distance between different organisms by genome rearrangements. The representation of a genome is very often made by assigning a unique number to each gene. If we assume no repeated genes, this representation can be seen as a permutation. By considering that the two genomes to be compared share the same set of genes, finding the evolutionary distance between them becomes the problem of finding the smallest number of genome rearrangements needed to transform one permutation into the other. In this thesis, we present several results involving genome rearrangement problems: (i) proofs of NP-hardness for four problems whose complexity was unknown; (ii) an exact polynomial algorithm for a problem whose complexity was unknown; and (iii) approximation algorithms and proofs of NP-hardness for problems where the genome representation carry more information than only the gene order. We describe these contributions in more depth in the following paragraphs. Among the problems involving genome rearrangements, four versions that allow the use of reversals and transpositions at the same time remained with unknown complexity despite the various algorithms proposed in the last 20 years. The first contribution presented is then the proofs of NP-hardness for these four problems. A variant of genome rearrangement problems considers that each rearrangement can affect only a small number of genes, also known as short and super short rearrangements. In this context, our second contribution is proof that the only problem involving super short reversals and super short transpositions whose complexity was unknown admits an exact polynomial algorithm. Most of the approaches for genome rearrangement problems in the literature so far have focused only on the relative order of genes in a genome, disregarding other important features presented in it. Recently, researchers have shown that considering the regions between each pair of genes, called intergenic regions, can result in better distance estimators in real data. Thus, our third contribution investigates the incorporation of intergenic regions in existing models for reversals and transpositions, both in the unrestricted and size restricted versions (i.e. super short operations), where we propose several approximation algorithms for problems that are either NP-hard or with unknown complexity Doutorado Ciência da Computação Doutor em Ciência da Computação CAPES CNPQ 140466/2018-5

Orientador: Zanoni Dias Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Rearranjos de genomas são eventos de mutação globais que agem sobre grandes trechos de um genoma, diferentemente das mutações mais comuns que afetam pontualmente o genoma. Na maioria dos casos, computar a distância de rearranjo de genomas entre dois genomas resulta em problemas NP-difíceis. Em um problema da ordenação por Rearranjo de Genomas desejamos calcular a sequência de eventos de rearranjos necessários para ordenar blocos conservados de genomas com custo mínimo, onde os genomas são representados por permutações. Um modelo de rearranjo determina quais eventos de rearranjo são permitidos para ordenar uma permutação ou transformar uma permutação em outra. Neste trabalho abordamos o modelo de eventos de reversão, que ocorre quando um segmento do genoma é revertido. No problema clássico de ordenação por reversões, o custo para qualquer reversão em uma permutação é unitário, independente do tamanho do segmento a ser revertido. Novos estudos mostraram que a mecânica de rearranjo de genomas sugere que reversões com tamanho de segmento menor ocorrem com maior frequência. Desta forma, abordamos neste trabalho o problema de ordenação por reversões ponderadas, onde o custo de cada reversão é igual ao tamanho do segmento revertido. Para obter soluções para o problema, inicialmente nós desenvolvemos um algoritmo heurístico polimomial para a variação do problema em que a orientação dos genes não é considerada (que resulta em uma permutação sem sinal), e obtivemos resultados experimentais superiores aos algoritmos anteriormente conhecidos, considerando todas as permutações de tamanho até 10 e amostras de permutações maiores de tamanho até 100. Em seguida desenvolvemos uma Meta-heurística iterativa que segue a estratégia GRASP (Greedy Randomized Adaptive Search Procedure). Este método foi aplicado também à variação do problema em que a orientação dos genes é considerada (que resulta em uma permutação com sinal). Para ambas variações nós executamos experimentos para amostras de permutações de tamanho no intervalo de 10 a 100 e mostramos que nosso método apresenta resultados significativamente superiores a todas as outras abordagens anteriores Abstract: Genome rearrangements are global mutation events that act on large stretches of a genome. Those are unlike the more common mutations, that affect the genome punctually. In most cases, the computation of genome rearrangement distance between two genomes induces NP-Hard problems. Genome sorting problems aims to calculate the sequence of rearrangements events required to sort conserved genomes blocks with minimum cost, where genomes are represented by permutations. A rearrangement model determines which rearrangement events are allowed to sort a permutation or transform a permutation in to another. In this work, we deal with inversion events, which occur when a segment of DNA sequence in the genome is reversed. In the classic problem of sorting by inversions, the cost of any inversion in a permutation is unitary, independent of segment size to be reversed. Further studies showed that reversals with lower segment size occur with greater frequency. In this way, we address the sorting by weighted inversions problem and, in our model, each inversion costs the number of elements in the reversed segment. In order to generate solutions for this problem, we initially developed a polinomial heuristic algorithm for the problem variation where the gene orientation is not taken in consideration (where we use unsigned permutations). With this first method we ran experiments, taking as input all permutations of size up to 10 and sample permutations with size up 100, and we obtained results that outperform previously known algorithms. Then we developed an iterative meta-heuristic that follows the GRASP strategy (Greedy Randomized Adaptive Search Procedure). This time the method supported as well the variation of the problem that takes genes orientation in consideration (which results in a signed permutation). For both variations we ran experiments with samples of permutation with size in the range from 10 to 100, and we show that our method provided significantly better results than all the other previously known approaches Mestrado Ciência da Computação Mestre em Ciência da Computação CNPQ 132198/2012-6

Orientador: Zanoni Dias Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: O Problema das Panquecas tem como objetivo ordenar uma pilha de panquecas que possuem tamanhos distintos realizando o menor número possível de operações. A operação permitida é chamada reversão de prefixo e, quando aplicada, inverte o topo da pilha de panquecas. Tal problema é interessante do ponto de vista combinatório por si só, mas ele também possui algumas aplicações em biologia computacional. Dados dois genomas que compartilham o mesmo número de genes, e assumindo que cada gene aparece apenas uma vez por genoma, podemos representá-los como permutações (pilhas de panquecas também são representadas por permutações). Então, podemos comparar os genomas tentando descobrir como um foi transformado no outro por meio da aplicação de rearranjos de genoma, que são eventos de mutação de grande escala. Reversões e transposições são os tipos mais comumente estudados de rearranjo de genomas e uma reversão de prefixo (ou transposição de prefixo) é um tipo de reversão (ou transposição) que é restrita ao início da permutação. Quando o rearranjo é restrito ao final da permutação, dizemos que ele é um rearranjo de sufixo. Um problema de ordenação de permutações por rearranjos é, portanto, o problema de encontrar uma sequência de rearranjos de custo mínimo que ordene a permutação dada. A abordagem tradicional considera que todos os rearranjos têm o mesmo custo unitário, de forma que o objetivo é tentar encontrar o menor número de rearranjos necessários para ordenar a permutação. Vários esforços foram feitos nos últimos anos considerando essa abordagem. Por outro lado, um rearranjo muito longo (que na verdade é uma mutação) tem mais probabilidade de perturbar o organismo. Portanto, pesos baseados no comprimento do segmento envolvido podem ter um papel importante no processo evolutivo. Dizemos que essa abordagem é ponderada por comprimento e o objetivo nela é tentar encontrar uma sequência de rearranjos cujo custo total (que é a soma do custo de cada rearranjo, que por sua vez depende de seu comprimento) seja mínimo. Nessa tese nós apresentamos os primeiros resultados que envolvem problemas de ordenação de permutações por reversões e transposições de prefixo e sufixo considerando ambas abordagens tradicional e ponderada por comprimento. Na abordagem tradicional, consideramos um total de 10 problemas e desenvolvemos novos resultados para 6 deles. Na abordagem ponderada por comprimento, consideramos um total de 13 problemas e desenvolvemos novos resultados para todos eles Abstract: The goal of the Pancake Flipping problem is to sort a stack of pancakes that have different sizes by performing as few operations as possible. The operation allowed is called prefix reversal and, when applied, flips the top of the stack of pancakes. Such problem is an interesting combinatorial problem by itself, but it has some applications in computational biology. Given two genomes that share the same genes and assuming that each gene appears only once per genome, we can represent them as permutations (stacks of pancakes are also represented by permutations). Then, we can compare the genomes by figuring out how one was transformed into the other through the application of genome rearrangements, which are large scale mutations. Reversals and transpositions are the most commonly studied types of genome rearrangements and a prefix reversal (or prefix transposition) is a type of reversal (or transposition) which is restricted to the beginning of the permutation. When the rearrangement is restricted to the end of the permutation, we say it is a suffix rearrangement. A problem of sorting permutations by rearrangements is, therefore, the problem to find a sequence of rearrangements with minimum cost that sorts a given permutation. The traditional approach considers that all rearrangements have the same unitary cost, in which case the goal is trying to find the minimum number of rearrangements that are needed to sort the permutation. Numerous efforts have been made over the past years regarding this approach. On the other hand, a long rearrangement (which is in fact a mutation) is more likely to disturb the organism. Therefore, weights based on the length of the segment involved may have an important role in the evolutionary process. We say this is the length-weighted approach and the goal is trying to find a sequence of rearrangements whose total cost (the sum of the cost of each rearrangement, which depends on its length) is minimum. In this thesis we present the first results regarding problems of sorting permutations by prefix and suffix reversals and transpositions considering both the traditional and the length-weighted approach. For the traditional approach, we considered a total of 10 problems and developed new results for 6 of them. For the length-weighted approach, we considered a total of 13 problems and developed new results for all of them Doutorado Ciência da Computação Doutora em Ciência da Computação FAPESP 140017/2013-5 CNPQ 2013/01172-0

Orientador: Guilherme Pimentel Telles Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Na biologia molecular o alinhamento de sequências é uma ferramenta para caracterizar similaridade ou distância entre sequências. O problema do alinhamento restrito por expressão regular (RECSA: Regular Expression Constrained Sequence Alignment) foi proposto no ano de 2005 por Arslan. O alinhamento restrito procura encontrar um alinhamento ótimo entre duas sequências de tal forma que a expressão regular esteja expressa numa parte do alinhamento. Famílias e domínios de proteínas encontram-se caraterizados como padrões no banco de dados PROSITE os quais são usados na biologia molecular para identificar e classificar proteínas. Esses padrões podem ser representados por expressões regulares e usados como restrição no alinhamento de Arslan. Na solução de Arslan para o alinhamento restrito é usado um autômato finito sem transições vazias construído a partir da expressão regular. O tempo de execução dessa solução depende do número de estados e transições desse autômato. Neste trabalho apresentamos quatro resultados. Primeiro, apresentamos um algoritmo melhorado da construção de Thompson que permite construir autômatos finitos mais compactos diretamente da expressão regular em tempo linear. Segundo, apresentamos uma forma de construir expressões regulares equivalentes a padrões PROSITE que, ao serem usadas na construção melhorada de Thompson, geram diretamente autômatos compactos sem transições vazias. Esses autômatos possuem número de estados sublinear e número de transições linear em relação ao número de símbolos da expressão regular, números menores que o esperado ao usar os resultados da literatura. Terceiro, esses autômatos compactos, ao serem usados na solução de Arslan, melhoram naturalmente o tempo de execução, esse tempo também é melhor que as soluções propostas por Chung et al. no ano de 2007 e por Kucherov et al. no ano de 2011. Finalmente, apresentamos um pré-processamento que, ao ser aplicado na solução de Arslan, melhora ainda mais o tempo de execução, conseguindo um limite inferior sobre a complexidade de tempo independente do tamanho do autômato Abstract: In molecular biology the sequence alignment is a tool for characterizing similarity or distance between sequences. The Regular Expression Constrained Sequence Alignment problem (RECSA) was proposed in 2005 by Arslan. Constrained alignment seeks to find an optimal alignment between two sequences such that the regular expression is expressed in a part of the alignment. Protein families and domains are characterized as patterns in PROSITE database, which are used in molecular biology to identify and classify proteins. These patterns can be represented by regular expressions and used as a restriction on Arslan alignment. In Arslan's solution for constrained alignment a finite automaton without empty transitions constructed from the regular expression is used. The running time of the solution depends on the number of states and transitions of this automaton. In this work we show four results. First, we present an improved Thompson's construction \cite{thompson68} that, allows building a more compact finite automatons directly from the regular expression in linear time. Second, we present a way to build regular expressions equivalent to PROSITE patterns that when used with the improved Thompson construction, generates compact automatons without empty transitions directly. These automatons have a sublinear number of states and a linear number of transitions in relation to the number of symbols in the regular expression, with smaller numbers than expected when compared to the literature results. Third, these compact automatons, when used in Arslan's solution improve runtime naturally and such time is also better than the solutions proposed by Chung et al. in 2007 and by Kucherov et al. in 2011. Finally, we present a preprocessing step which when applied to Arslan's solution improves further the running time, managing to achieve a lower bound on the time complexity independent of the size of the automaton Mestrado Ciência da Computação Mestre em Ciência da Computação CNPQ 132470/2012-8

Orientador: Zanoni Dias Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Ao longo da evolução, eventos de rearranjo podem alterar a ordem e a orientação dos genes de um genoma. O problema de calcular a menor sequência de rearranjos que transforma um genoma em outro é um problema bastante estudado que encontra aplicações em genômica comparativa. Representando genomas como permutações, nas quais os genes aparecem como elementos, esse problema pode ser reduzido ao problema combinatório de ordenar uma permutação utilizando o menor número de rearranjos. Tal problema combinatório, referido como problema da ordenação por rearranjo, varia de acordo com os tipos de rearranjo considerados. Nesta tese, focamos nosso estudo em dois tipos de rearranjo: reversões e transposições. Muitas variações do problema da ordenação por rearranjo que envolvem esses rearranjos têm sido atacadas na literatura e, para a maior parte delas, os melhores algoritmos conhecidos são aproximações ou heurísticas. Em razão disso, apresentamos uma ferramenta, chamada GRAAu, que auxilia a avaliação dos resultados produzidos por esses algoritmos. Além disso, apresentamos uma heurística genérica que pode ser usada para melhorar as soluções produzidas por qualquer algoritmo não exato. Além de apresentar o GRAAu e a heurística de melhoria, os quais possuem um apelo mais geral, apresentamos contribuições relacionadas à variações específicas do problema da ordenação por rearranjo. Primeiro, consideramos o problema da ordenação por transposições e apresentamos resultados teóricos e práticos relacionados a três algoritmos aproximados baseados em uma abordagem alternativa ao grafo de ciclos, que é uma ferramenta padrão para atacar o problema da ordenação por rearranjo. Depois, voltamos nossa atenção à variações que envolvem rearranjos curtos. Mais precisamente, estudamos cinco variações: (i) o problema de ordenar uma permutação linear com sinal por reversões super curtas, (ii) o problema de ordenar uma permutação circular com sinal por reversões super curtas, (iii) o problema de ordenar uma permutação linear com sinal por reversões curtas, (iv) o problema de ordenar uma permutação linear com sinal por rearranjos super curtos e (v) o problema de ordenar uma permutação linear com sinal por rearranjos curtos. Apresentamos algoritmos polinomiais para os problemas (i), (ii) and (iv), um algoritmo 5-aproximado para o problema (iii) e um algoritmo 3-aproximado para o problema (v). Usamos o algoritmo desenvolvido para o problema (ii) para reconstruir a filogenia de genomas de bactérias do gênero Yersinia e comparamos os resultados com as filogenias apresentadas em trabalhos anteriores Abstract: During evolution, rearrangement events may alter the order and the orientation of the genes in a genome. The problem of finding the minimum sequence of rearrangements that transforms one genome into another is a well-studied problem that finds application in comparative genomics. Representing genomes as permutations, in which genes appear as elements, that problem can be reduced to the combinatorial problem of sorting a permutation using a minimum number of rearrangements. Such combinatorial problem, referred to as rearrangement sorting problem, varies according to the types of rearrangements considered. In this thesis, we focus on two types of rearrangements: reversals and transpositions. Many variants of the rearrangement sorting problem involving these rearrangements have been tackled in the literature and, for most of them, the best known algorithms are approximations or heuristics. For this reason, we present a tool, called GRAAu, to aid in the evaluation of the results produced by these algorithms. In addition, we present a general heuristic that can be used to improve the solutions provided by any non-optimal algorithm. Besides presenting GRAAu and the improvement heuristic, which have a more general appeal, we present contributions regarding specific variants of the rearrangement sorting problem. First, we consider the problem of sorting by transpositions and we present experimental and theoretical results regarding three approximation algorithms based on alternative approaches to the cycle graph, which is a standard tool for attacking the rearrangement sorting problem. Then, we turn our attention to variants involving short rearrangements. More precisely, we study five variants: (i) the problem of sorting a signed linear permutation by super short reversals, (ii) the problem of sorting a signed circular permutation by super short reversals, (iii) the problem of sorting a signed linear permutation by short reversals, (iv) the problem of sorting a signed linear permutation by super short rearrangements, and (v) the problem of sorting a signed linear permutation by short rearrangements. We present polynomial-time algorithms for problems (i), (ii) and (iv), a 5-approximation algorithm for problem (iii), and a 3-approximation algorithm for problem (v). We use the algorithm developed for problem (ii) to reconstruct the phylogeny of Yersinia genomes and compare the result with the phylogenies presented in previous works Doutorado Ciência da Computação Doutor em Ciência da Computação FAPESP 2014/04718-6

Orientador: Zanoni Dias Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Alinhamento de seqüências é, reconhecidamente, uma das tarefas de maior importância em bioinformática. Tal importância origina-se no fato de ser uma operação básica utilizada por diversos outros procedimentos na área, como busca em bases de dados, visualização do efeito da evolução em uma família de proteínas, construção de árvores filogenéticas e identificação de motifs preservados. Seqüências podem ser alinhadas aos pares, problema para o qual já se conhece algoritmo exato com complexidade de tempo O(l2), para seqüências de comprimento l. Pode-se também alinhar simultaneamente três ou mais seqüências, o que é chamado de alinhamento múltiplo de seqüências (MSA, do inglês Multiple Sequence Alignment ). Este, que é empregado em tarefas como detecção de padrões para caracterizar famílias protéicas e predição de estruturas secundárias e terciárias de proteínas, é um problema NP - Difícil. Neste trabalho foram desenvolvidos métodos heurísticos para alinhamento múltiplo de seqüências de proteína. Estudaram-se as principais abordagens e métodos existentes e foi realizada uma série de implementações e avaliações. Em um primeiro momento foram construídos 342 alinhadores múltiplos utilizando a abordagem progressiva. Esta, que é uma abordagem largamente utilizada para construção de MSAs, consiste em três etapas. Na primeira delas é computada a matriz de distâncias. Em seguida, uma árvore guia é gerada com base na matriz e, finalmente, o MSA é construído através de alinhamentos de pares, cuja ordem é definida pela árvore. Os alinhadores desenvolvidos combinam diferentes métodos aplicados a cada uma das etapas. Para a computação das matrizes de distâncias foram desenvolvidos dois métodos, que são capazes também de gerar alinhamentos de pares de seqüências. Um deles constrói o alinhamento com base em alinhamentos locais e o outro utiliza uma função logarítmica para a penalização de gaps. Foram utilizados ainda outros métodos disponíveis numa ferramenta chamada PHYLIP. Para a geração das árvores guias, foram utilizados os métodos clássicos UPGMA e Neighbor Joining. Usaram-se implementações disponíveis em uma ferramenta chamada R. Já para a construção do alinhamento múltiplo, foram implementados os métodos seleção por bloco único e seleção do par mais próximo. Estes, que se destinam a seleção xiii do par de alinhamentos a agrupar no ciclo corrente, são comumente utilizados para tal tarefa. Já para o agrupamento de um par de alinhamentos, foram implementados 12 métodos inspirados em métodos comumente utilizados - alinhamento de consensos e alinhamento de perfis. Foram feitas todas as combinações possíveis entre esses métodos, resultando em 342 alinhadores. Eles foram avaliados quanto à qualidade dos alinhamentos que geram e avaliou-se também o desempenho dos métodos, utilizados em cada etapa. Em seguida foram realizadas avaliações no contexto de alinhamento baseado em consistência. Nesta abordagem, considera-se MSA ótimo aquele que estão de acordo com a maioria dos alinhamentos ótimos para os n(n ? 1)/2 alinhamentos de pares contidos no MSA. Alterações foram realizadas em um alinhador múltiplo conhecido, MUMMALS, que usa a abordagem. As modificações foram feitas no método de contagem k-mer, assim como, em outro momento, substituiu-se a parte inicial do algoritmo. Foram alterados os métodos para computação da matriz de distâncias e para geração da árvore guia por outros que foram bem avaliados nos testes realizados para a abordagem progressiva. No total, foram implementadas e avaliadas 89 variações do algoritmo original do MUMMALS e, apesar do MUMMALS já produzir alinhamentos de alta qualidade, melhoras significativas foram alcançadas. O trabalho foi concluído com a implementação e a avaliação de algoritmos iterativos. Estes se caracterizam pela dependência de outros alinhadores para a produção de alinhamentos iniciais. Ao alinhador iterativo cabe a tarefa de refinar tais alinhamentos através de uma série de ciclos até que haja uma estabilização na qualidade dos alinhamentos. Foram implementados e avaliados dois alinhadores iterativos não estocásticos, assim como um algoritmo genético (GA) voltado para a geração de MSAs. Nesse algoritmo genético, implementado na forma de um ambiente parametrizável para execução de algoritmos genéticos para MSA, chamado ALGAe, foram realizadas diversas experiências que progressivamente elevaram a qualidade dos alinhamentos gerados. No ALGAe foram incluídas outras abordagens para construção de alinhamentos múltiplos, tais como baseada em blocos, em consenso e em modelos. A primeira foi aplicada na geração de indivíduos para a população inicial. Foram implementados alinhadores baseados em blocos usando duas abordagens distintas e, para uma delas, foram implementadas cinco variações. A segunda foi aplicada na definição de um operador de cruzamento, que faz uso da ferramenta M-COFFEE para realizar alinhamentos baseados em consenso a partir de indivíduos da população corrente do GA, e a terceira foi utilizada para definir uma função de aptidão, que utiliza a ferramenta PSIPRED para predição das estruturas secundárias das seqüências. O ALGAe permite a realização de uma grande variedade de novas avaliações Abstract: Sequence alignment is one the most important tasks of bioinformatics. It is a basic operation used for several procedures in that domain, such as sequence database searches, evolution effect visualization in an entire protein family, phylogenetic trees construction and preserved motifs identification. Sequences can be aligned in pairs and generate a pairwise alignment. Three or more sequences can also be simultaneously aligned and generate a multiple sequence alignment (MSA). MSAs could be used for pattern recognition for protein family characterization and secondary and tertiary protein structure prediction. Let l be the sequence length. The pairwise alignment takes time O(l2) to build an exact alignment. However, multiple sequence alignment is a NP-Hard problem. In this work, heuristic methods were developed for multiple protein sequence alignment. The main approaches and methods applied to the problem were studied and a series of aligners developed and evaluated. In a first moment 342 multiple aligners using the progressive approach were built. That is a largely used approach for MSA construction and is composed by three steps. In the first one a distance matrix is computed. Then, a guide tree is built based on the matrix and finally the MSA is constructed through pairwise alignments. The order to the pairwise alignments is defined by the tree. The developed aligners combine distinct methods applied to each of steps. Then, evaluations in the consistency based alignment context were performed. In that approach, a MSA is optimal when agree with the majority along all possible optimal pairwise alignments. MUMMALS is a known consistency based aligner. It was changed in this evaluation. The k-mer counting method was modified in two distinct ways. The k value and the compressed alphabet were ranged. In another evaluation, the k-mer counting method and guide tree construction method were replaced. In the last stage of the work, iterative algorithms were developed and evaluated. Those methods are characterized by other aligner's dependence. The other aligners generate an initial population and the iterative aligner performs a refinement procedure, which iteratively changes the alignments until the alignments quality are stabilized. Several evaluations were performed. However, a genetic algorithm for MSA construction stood out along this stage. In that aligner were added other approaches for multiple sequence alignment construction, such as block based, consensus based and template based. The first one was applied to initial population generation, the second one was used for a crossover operator creation and the third one defined a fitness function Doutorado Ciência da Computação Doutor em Ciência da Computação

Orientador: Zanoni Dias Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: A teoria da seleção natural de Darwin afirma que os seres vivos atuais descendem de ancestrais, e ao longo da evolução, mutações genéticas propiciaram o aparecimento de diferentes espécies de seres vivos. Muitas mutações são pontuais, alterando a cadeia de DNA, o que pode impedir que a informação seja expressa, ou pode expressá-la de um modo diferente. A comparação de sequências é o método mais usual de se identificar a ocorrência de mutações pontuais, sendo um dos problemas mais abordados em Biologia Computacional. Rearranjo de Genomas tem como objetivo encontrar o menor número de operações que transformam um genoma em outro. Essas operações podem ser, por exemplo, reversões, transposições, fissões e fusões. O conceito de distância pode ser definido para estes eventos, por exemplo, a distância de reversão é o número mínimo de reversões que transformam um genoma em outro [9] e a distância de transposição é o número mínimo de transposições que transformam um genoma em outro [10]. Nós trataremos os casos em que os eventos de reversão e transposição ocorrem de forma isolada e os casos quando os dois eventos ocorrem simultaneamente, com o objetivo de encontrar o valor exato para a distância. Nós criamos modelos de Programação por Restrições para ordenação por reversões e ordenação por reversões e transposições, seguindo a linha de pesquisa utilizada por Dias e Dias [16]. Nós apresentaremos os modelos de Programação por Restrições para ordenação por reversões, ordenação por transposições e ordenação por reversões e transposições, baseados na teoria do Problema de Satisfação de Restrições e na teoria do Problema de Otimização com Restrições. Nós fizemos comparações com os modelos de Programação por Restrições para ordenação por transposições, descrito por Dias e Dias [16], e com as formulações de Programação Linear Inteira para ordenação por reversões, ordenação por transposições e ordenação por reversões e transposições, descritas por Dias e Souza [17] Abstract: The Darwin's natural selection theory states that living beings of nowadays are descended from ancestors, and through evolution, genetic mutations led to the appearance of different kinds of living beings. Many mutations are point mutations, modifying the DNA sequence, which may prevent the information from being expressed, or may express it in another way. The sequence comparison is the most common method to identify the occurrence of point mutations, and is one of the most discussed problems in Computational Biology. Genome Rearrangement aims to find the minimum number of operations required to change one sequence into another. These operations may be, for example, reversals, transpositions, fissions and fusions. The concept of distance may be defined for these events, for example, the reversal distance is the minimum number of reversals required to change one sequence into another [9] and the transposition distance is the minimum number of transpositions required to change one sequence into another [10]. We will deal with the cases in which reversals and transpositions events occur separately and the cases in which both events occur simultaneously, aiming to find the exact value for the distance. We have created Constraint Programming models for sorting by reversals and sorting by reversals and transpositions, following the research line used by Dias and Dias [16]. We will present Constraint Logic Programming models for sorting by reversals, sorting by transpositions and sorting by reversals and transpositions, based on Constraint Satisfaction Problems theory and Constraint Optimization Problems theory. We made a comparison between the Constraint Logic Programming models for sorting by transpositions, described in Dias and Dias [16], and with the Integer Linear Programming formulations for sorting by reversals, sorting by transpositions and sorting by reversals and transpositions, described in Dias and Souza [17] Mestrado Ciência da Computação Mestre em Ciência da Computação

Orientador: Zanoni Dias Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Ao longo da evolução, mutações globais podem alterar a ordem dos genes de um genoma. Tais mutações são chamadas de eventos de rearranjo. Em Rearranjo de Genomas, estimamos a distância evolutiva entre dois genomas calculando-se a distância de rearranjo entre eles, que é o tamanho da menor sequência de eventos de rearranjo que transforma um genoma no outro. Representando genomas como permutações, nas quais os genes aparecem como elemento, à distância de rearranjo pode ser obtido resolvendo-se o problema combinatório de ordenar uma permutação utilizando o menor número de eventos de rearranjo. Este problema, que é referido como Problema da Ordenação por Rearranjo, varia de acordo com os tipos de eventos de rearranjo considerados. Nesta dissertação, focamos nosso estudo em dois tipos de eventos: reversões e transposições. Variações do Problema da Ordenação por Rearranjo que consideram esses eventos têm se mostrado difíceis de ser resolvida otimamente, por isso a maior parte dos algoritmos propostos - os quais denominamos genericamente por algoritmos de rearranjo de genomas - são aproximados e é esperado que os próximos avanços ocorram nesse sentido. Em razão disso, desenvolvemos uma ferramenta que avalia as respostas desses algoritmos. Para ilustrar sua aplicação, nós a utilizamos para avaliar as respostas de 16 algoritmos de rearranjo de genomas aproximados relativos a 6 variações do Problema da Ordenação por Rearranjo. Além da ferramenta, este trabalho traz outras contribuições. Desenvolvemos um algoritmo exato para calcular distâncias de rearranjo que é mais eficiente em termos de uso de memória do que qualquer outro algoritmo que encontramos na literatura. Apresentamos conjecturas que dizem respeito à forma como as distâncias de rearranjo se distribuem. Validamos conjecturas referentes ao diâmetro, que é o maior valor alcançável pela distância de rearranjo entre uma permutação qualquer e a identidade considerando-se todas as permutações com o mesmo número de elementos. Apresentamos demonstrações formais para o fator de aproximação de alguns dos algoritmos avaliados. Por fim, mostramos que os fatores de aproximação de 7 dos 16 algoritmos avaliados não podem ser melhorados, o que contradiz algumas hipóteses levantadas na literatura, e conjecturamos que os fatores de aproximação de outros 6 algoritmos também não possam Abstract: During evolution, global mutations may modify the gene order in a genome and such mutations are called rearrangement events. In Genome Rearrangements, we estimate the evolutionary distance between two genomes by computing the rearrangement distance between them, which is the length of the shortest sequence of rearrangement events that transforms one genome into the other. Representing genomes as permutations, in which genes appear as elements, the rearrangement distance can be obtained by solving the combinatorial problem of sorting a permutation using a minimum number of rearrangement events. This problem is referred to as Rearrangement Sorting Problem and varies accordingly to the types of rearrangement events considered. In this dissertation, we focus on two types of rearrangement events: reversals and transpositions. Variants of Rearrangement Sorting Problem involving these events have been shown to be difficult to solve optimally, therefore most of the proposed algorithms - which we denominate generically as genome rearrangement algorithms - are approximations, which have been the expected direction to follow. For this reason, we developed a tool that evaluates the results of these algorithms. To illustrate its application, we used it to evaluate the results of 16 genome rearrangement algorithms regarding 6 variants of Rearrangement Sorting Problem. Besides this tool, we developed an exact algorithm for computing rearrangement distances that is more efficient in terms of memory than any algorithm we have found in literature. Additionally, we presented conjectures on how the rearrangement distance are distributed and validated them regarding their diameter, which is the greatest value that the rearrangement distance between a permutation and the identity can reach considering all permutations with the same number of elements. Moreover, we presented formal proofs on the approximation ratio of some of the evaluated algorithms and showed that the approximation ratio of 7 out of the 16 evaluated algorithms cannot be improved, which contradicts some hypothesis raised in literature. Lastly, we conjectured that the approximation ratio of another 6 algorithms also cannot be improved Mestrado Ciência da Computação Mestre em Ciência da Computação

Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2010. Neste trabalho, propusemos e implementamos um método de aprendizagem por reforço no sistema BioAgents, que tem a finalidade de auxiliar os biólogos na fase de anotação manual de sequências biológicas em projetos de sequenciamento de genomas. O sistema foi reimplementado de modo a permitir a incorporação do mecanismo de aprendizagem, por meio de uma camada adicional no BioAgents. Para validar o método e a implementação, realizamos dois experimentos, com dados reais dos Projetos Genoma do fungo Paracoccidioides brasiliensis e da planta Paullinia cupana. Utilizamos genomas de referência para validar as anotações sugeridas, atribuindo recompensas aos bancos de dados e as ferramentas utilizadas pelos agentes. Os resultados obtidos com a camada de aprendizagem, quando comparados com o sistema sem o método proposto, mostram uma melhora de desempenho. ______________________________________________________________________________________________ ABSTRACT In this work, we proposed and implemented a reiforcement learning method at the BioAgents system which has the objective of assisting biologists in the process of manual annotation of biological sequences in genome sequencing projects. The system was reimplemented to allow the incorporation of a learning mechanism, based in an additional layer in BioAgents. To validate the method and implementation, we conducted two experiments, with real data of the Projeto Genoma of fungus Paracoccidioides brasiliensis and of plant Paullinia cupana. We used reference genomes to validate the suggested annotations, giving rewards to the databases and tools handled by the agents. The results obtained with the learning layer, when compared with the system without the proposed method, showed a performance improvement.

Orientador: João Meidanis Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: A evolução das técnicas de seqüenciamento tornou possível a obtenção de uma enorme quantidade de dados genômicos. O desafio atual é analisar esses dados e construir novos conhecimentos a partir deles. Neste contexto, um problema importante e ainda em aberto é a criação de métodos de análise taxonômica de genomas completos. Especialmente para organismos procariontes, para os quais ainda não há um conceito claro de espécie, a comparação de genomas completos pode significar uma importante contribuição. Neste trabalho propomos uma metodologia para comparação de genomas completos baseada na teoria de Rearranjo de Genomas, aplicando-a a organismos da família Vibrionaceae ¿ uma família heterogênea que compreende organismos de cinco diferentes gêneros, incluindo o vibrião causador da cólera, uma doença grave e que ainda causa anualmente milhares de mortes em países em desenvolvimento. As distâncias genômicas obtidas quando analisamos separadamente cada um dos dois cromossomos que compõem o genoma desses organismos estão de acordo com as árvores filogenéticas construídas empregando outros métodos de comparação genômica. Esse resultado corrobora nosso método e a utilização da teoria de rearranjo de genomas como uma alternativa para análise de genomas completos. Além disso, pode indicar que os eventos modelados neste trabalho, como perda de genes, transferências horizontais, reversões entre outros, exercem um papel importante na evolução desses organismos. Compreender a dinâmica desses eventos e combiná-la a outros métodos de análise genômica pode significar um grande avanço para a construção de uma filogenia mais acurada para estes vibriões Abstract: The evolution in genomic sequencing techniques has resulted in a large amount of genomic data. The challenge that arises from this scenario is to analyze these data and to extract from them relevant biologic information. In this context, taxonomic analysis of complete genome sequences is still an open problem. Futhermore, it is critical for procaryotes, which still lack a clear definition of species, and whose taxonomic classification is in continuous evolution, where complete genomes comparison may well play a significant role. In this work, we propose a methodology to compare complete genomes based on genome rearrangement theory. We have applied our method to organisms of Vibrionaceae family ¿ a heterogeneous family that comprehends organisms from five different genera, including the agent responsible for cholera, a severe disease in developing countries. The genomic distances obtained when we analysed each chromosome individually are in agreement with phylogenic trees built using other genomic methods. This result validates our method and the genomic rearrangement theory as an alternative to analyze complete genomes. It also can indicate the importance played by rearrangement events in the vibrio genomic evolution. The understanding of these events, combined with other genomic methods, can play an important role in the construction of a robust vibrio phylogeny Mestrado Biologia Computaçional Mestre em Ciência da Computação

Orientador: João Meidanis Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: O sucesso na obtenção de cadeias completas de DNA de alguns organismos tem incentivado a busca de novas técnicas computacionais capazes de analisar esse montante de informação para aplicá-lo na descoberta de novos remédios, aumento da produção de alimentos e investigação do processo de evolução dos seres vivos, entre outras aplicações. A comparação de seqüências de DNA (ou RNA) de diferentes espécies é uma das técnicas importantes para desvendar novas propriedades biológicas. Uma das maneiras de se comparar dois genomas é analisar como os dois se distinguem com base em certas mutações chamadas eventos de rearranjo em genomas. Nessa técnica de comparação, um genoma é modelado como uma seqüência de regiões que são conservadas em um conjunto de genomas. O problema de rearranjos em genomas consiste genericamente em encontrar, dados dois genomas como entrada e um conjunto de tipos de eventos de rearranjo permitidos, uma seqüência mínima de tais eventos de rearranjo que transforme um genoma em outro. No formalismo clássico de rearranjos em genomas, um genoma tem sido modelado como um conjunto de seqüências de inteiros. Cada número inteiro representa um gene e o seu sinal representa a orientação do gene no genoma. O problema de rearranjos em genomas nesse modelo é analisado de forma geral por meio de diversos diagramas e grafos que representam certas propriedades do par de genomas na entrada do problema. Neste trabalho, usamos um novo modelo para rearranjos em genomas proposto por Meidanis e Dias [39]: o formalismo algébrico. Em vez de se basear na análise de diagramas, o formalismo algébrico usa permutações na modelagem de genomas e, principalmente, utiliza resultados de grupos de permutações para analisar as propriedades de genomas e os efeitos de eventos de rearranjo. A motivação para o desenvolvimento do formalismo algébrico é a possibilidade de formalização de argumentos sobre rearranjos por meio de métodos algébricos, em vez da utilização de recursos gráficos como é feito no formalismo clássico. Esperamos que, por meio do desenvolvimento de um novo formalismo para o tratamento de problemas de rearranjos em genomas, algoritmos mais eficientes para a resolução desses problemas, ou maneiras mais simples de demonstrar alguns dos resultados clássicos na área sejam encontrados com maior facilidade. Nesse trabalho, apresentamos duas soluções simples e eficientes derivadas diretamente do formalismo algébrico para dois problemas de rearranjos em genomas (o problema de rearranjos em genomas por intercâmbio de blocos e reversões com sinais e o problema de rearranjo em genomas por fissões, fusões e reversões com sinais). Também discutimos e propomos um algoritmo polinomial para o problema de rearranjos em genomas por transposições generalizadas. Acreditamos que o sucesso na solução desses problemas possa ser estendido para outros problemas de rearranjos em genomas com a consolidação dos conceitos fundamentais do formalismo algébrico. Esperamos com essa tese convencer o leitor de que o formalismo algébrico é um modelo representativo e poderoso para tratar genomas compostos por cromossomos circulares e ao lidar com a atribuição de pesos a eventos de rearranjo. Por outro lado, não defendemos que o formalismo clássico seja simplesmente substituído pelo formalismo algébrico. Ambos os formalismos podem ser beneficiados por um processo semelhante, porém em menor escala, ao sucesso do desenvolvimento da Geometria Analítica e da Geometria Tradicional Abstract: The success in obtaining complete sequences of DNA of some species has encouraged the search for new computational techniques for the analysis of such huge amount of information. One hopes that the results of this research could be applied for the development of new medicines, increasing food crops productivity, better understanding of the evolutionary process in live beings, among other applications. One technique for the genome analysis is the comparison of DNA (or RNA) sequences from different species. Such a comparison may reveal the similarities and differences between the genomes, which could be used in phylogeny reconstruction for instance. Two genomes can be compared by the analysis of their differences based on mutational events called genome rearrangements. The genome rearrangement problem (also called a sorting problem) consists of finding a minimum sequence of rearrangement events that transforms one genome into another and the number of rearrangement events in the sequence is called the genomic distance. In the classical formalism for genome rearrangements, a genome is usually modeled by a set of sequences of integers. Each integer represents a gene and its sign stands for the orientation of the gene in the genome. The genome rearrangement problem in this model is analyzed generally with tools such as diagrams and graphs that convey the properties of the genomes in the problem input. We use instead a new model for genome rearrangements proposed by Meidanis and Dias [39]: the algebraic formalism. Instead of being based on the analysis of diagrams, the algebraic formalism uses permutations to model genomes and the results from permutation group theory for the analysis of the properties of genomes and the effects of rearrangement events. The motivation for the development of the algebraic formalism is the possibility of stating arguments more formally by means of algebraic methods than by using graphical resources as the classical formalism does. We hope that more efficient algorithms for genome rearrangement problems or simpler proofs for classical results in the area will be more easily found due to the development of a new formalism. We present a simple, efficient solution based on the algebraic formalism for two genome rearrangement problems (the problem of genome rearrangements by block-interchanges and signed reversals and the problem of genome rearrangements by fissions, fusions, and signed reversals). We also discuss and offer a solution for the problem of genome rearrangements by generalized transpositions. We believe that the success in solving those genome rearrangement problems could be extended to other problems by consolidating the fundamental concepts of the algebraic formalism. We hope that the reader will be convinced that the algebraic formalism is representative and powerful in dealing with circular chromosomes and modeling the assignment of weights to rearrangement events. On the other hand, we do not argue in favor of a substitution of the classical formalism by the algebraic formalism. Both of these formalisms could profit by a similar, even though on a smaller scale, success of the development of the Analytic Geometry and the Traditional Geometry Doutorado Doutor em Ciência da Computação

Orientador: João Meidanis Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Nas últimas décadas presenciamos grandes avanços na biologia molecular que levaram ao acúmulo de um grande volume de dados acerca de moléculas, tais como DNAs e proteínas, essenciais para a vida e para seu entendimento.O estágio atual é de busca por ferramentas que permitam extrair informações com relevância biológica destes dados. Neste contexto, a comparação de genomas surge como uma das ferramentas e nesta categoria incluímos rearranjo de genomas. Em rearranjo, o genoma é representado por uma seqüência de blocos conservados e, dados dois genomas e um conjunto de operações, busca-se pela que transformem um genoma no outro. Em 1995, Hannenhallie Pevzner apresentaram o primeiro algoritmo polinomial para o problema da ordenação por reversões orientadas. Tal algoritmo executa em tempo O(n4) e foi o primeiro algoritmo polinomial para um modelo realístico de rearranjo de genomas. Desde então, surgiram algoritmos que apresentam desempenho assintoticamente melhor. O melhor deles, apresentado por Tannier e Sagot em 2004, é capaz de executar em tempo O (n(n log n)1/2). Há um algoritmo linear, desenvolvido por Bader e colegas[2], mas este capaz de determinar a seqüência de reversões, apenas calcula a distância. Motivado pela carência de uma derivação algébrica mais formal da teoria desenvolvida em rearranjo de genomas, desenvolvemos uma solução formal para o problema da distância de reversão com sinal. Utilizamos, em tal solução, um formalismo algébrico para rearranjo de genomas que relaciona a recente teoria de rearranjo de genomas ?basicamente fundamentada no trabalho de Hannenhalli e Pevzner ? e a teoria de grupos de permutação de uma nova forma. Pretendemos criar a base para grandes avanços na área através de um formalismo algébrico forte Abstract: In the last decades we have seen a great progress in molecular biology. That lead to a large volume of data on molecules, DNA and proteins, essential for life.The current stage of research lies in the pursuit of tools to extract information with biological relevance from this data. In this context, comparison of genomes is an important tool and genome rearrangements is a way of doing that comparison. In rearrangement analysis the genome is represented by a sequence of conserved blocks. The aim is to ?nd a minimum sequence of operations that transform a genome into another given as input two genomes and a set of allowed operations. In 1995, Hannenhalli and Pevzner presented the ?rst polinomial algorithm for sorting signed permutations by reversals. This algorithm has complexity O(n4) in time and was the ?rst polinomial algorithm for a realistic model of genome rearrangement. Since then, new algorithms with better asintotic performance had appeared. The fastest algorithm, with complexity O(n?n logn), was developed byTannier and Sagot in 2004. Motivated by a lack of a more formal derivation in the genome rearrangement developed theory, we developed a formal solution for the signed reversal distance problem. We use an algebraic formalism that relates the recent genome rearrangement theory ? basically based on a work of Hannenhalli and Pevzner ? to permutation group theory in a new form. We intend to build a solid theoretical base for further advances in the area through strong algebraic formalism Mestrado Teoria da Computação Mestre em Ciência da Computação

Orientador: João Meidanis Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Uma das principais formas de se medir a distância evolutiva entre espécies é avaliando-se quão transformado um genoma foi em relação a outro. Tais transformações são conhecidas como rearranjos de genoma. Neste trabalho estaremos analisando o rearranjo chamado de transposição, evento que troca de posição dois blocos consecutivos de genes de um mesmo cromossomo. Mais especificamente, buscamos encontrar o número mínimo de transposições que transforma um cromos somo em outro, valor conhecido como distância de transposição. Matematicamente, consideramos os cromossomos como permutações e o problema de se transformar uma permutação em outra pode ser visto como uma ordenação. Em nosso estudo, introduzimos uma operação de remoção de elementos, ferramenta ainda pouco explorada no estudo da distância de transposição, mas que nos possibilitou obter um limite superior para a distância de transposição. Também sugerimos novas formas de se utilizar a remoção de elementos e a análise de subseqüências de permutações. Como forma de se tentar obter novos conhecimentos sobre o problema da distância de transposição, consideramos a variação do problema em que somente transposições de prefixo são permitidas. Zanoni Dias propôs um algoritmo polinomial que transforma qualquer permutação de comprimento n em sua reversa em f3n/41 passos, porém sem uma prova completa. Modificamos esse algoritmo, mantendo o número de passos, e apresentamos uma prova completa da correção do algoritmo modificado. Ainda no problema de distância de transposição de prefixo, analisamos as permutações cujas distâncias se igualam ao limite inferior de distância de pontos de quebra. Tais permutações são fáceis de serem ordenadas por transposições de prefixo em tempo polinomial, pois possuem ordenação ótima única e bem definida. Ao final chegamos à conclusão que as permutações que são fáceis de se ordenar no problema de transposições de prefixo também são fáceis no problema de transposições, o que prova que a variação do problema auxilia no estudo do problema original Abstract: One of the main ways of measuring the evolution distance among species is to evaluate how large chunks have moved when comparing two genomes. Such changes are know as genome rearrangements. In this work we analyze a rearrangement event called transposition that changes the position of two consecutive blocks of genes in a chromosome. More specifically, we look for the minimum number of transpositions needed to transform a chromosome into another. This value is called the transposition distance. Mathematically, chromosomes are regarded as permutations and changing one genome into another can be seen as a sorting problem. In our study, we introduce an operation of element removal from permutations, which has not been fully explored, but allowed us to find an upper bound for the transposition distance. We also suggest new ways of making use of element removal and the analysis of permutation subsequences. In the hope of obtaining new knowledge about the problem of transposition distance, we considered the variation of the problem where we allow prefix transpositions only. Zanoni Dias developed a polynomial algorithm that changes any permutation into its reverse using f3n/41 steps, but without a proof of its correctness. We have modified this algorithm, keeping the number of steps, and presented a complete proof of the correction of the modified algorithm. Still about the prefix transposition distance, we have analyzed those permutations whose distance equals the breakpoint lower bound. Such permutations are easily sorted by prefix transpositions in polynomial time, since they have a unique and well-defined optimum sorting. Finally, we concluded that the permutations that are easily sorted in the prefix transposition problem are also easily sorted in the transposition problem, which proves that the variation of the problem helps the study of the original problem Mestrado Mestre em Ciência da Computação

Orientador : João Meidanis Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Hoje em dia, estão disponíveis, publicamente, uma imensa quantidade de informações genéticas. O desafio atual da Genômica é processar estes dados de forma a obter conclusões biológicas relevantes. Uma das maneiras de estruturar estas informações é através de comparação de genomas, que busca semelhanças e diferenças entre os genomas de dois ou mais organismos. Neste contexto, a área de Rearranjo de Genomas vem recebendo bastante atenção ultimamente. Uma forma de comparar genomas é através da distância de rearranjo, determinada pelo número mínimo de eventos de rearranjo que podem explicar as diferenças entre dois genomas. Os principais estudos em distância de rearranjo envolvem eventos de reversões e transposições. A presente coletânea é composta de oito artigos, contendo vários resultados importantes sobre Rearranjo de Genomas. Estes trabalhos foram apresentados em seis conferências, sendo uma nacional e cinco internacionais. Dois destes trabalhos serão publicados em importantes revistas internacionais e outro foi incluído como um capítulo de um livro. Nossas principais contribuições podem ser divididas em dois grupos: um novo formalismo algébrico e uma série de resultados envolvendo o evento de transposição. A nova teoria algébrica relaciona a teoria de Rearranjo de Genomas com a de grupos de permutações. Nossa intenção foi estabelecer um formalismo algébrico que simplificasse a obtenção de novos resultados, até hoje, muito baseados na construção de diagramas. Estudamos o evento de transposição de várias formas. Além de apresentarmos resultados sobre a distância de transposição entre uma permutação e sua inversa, também estudamos o problema de rearranjo envolvendo transposições e reversões simultaneamente, construindo algoritmos de aproximação e estabelecendo uma conjectura sobre o diâmetro. Usamos o formalismo algébrico para mostrar que é possível determinar a distância de fusão, fissão e transposição em tempo polinomial. Este é o primeiro resultado polinomial conhecido para um problema de rearranjo envolvendo o evento de transposição. Por último, introduzimos dois novos problemas de rearranjo: o problema de distância sintênica envolvendo fusões e fissões, e o problema de transposição de prefixos. Para ambos apresentamos resultados significativos, que avançam o conhecimento na área Abstract: Nowadays, a huge amount of genetic information is public1y available. Genomic's current challenge is to process this information in order to obtain relevant biological conc1usions. One possible way of structuring this information is through genome comparison, where we seek similarities and differences among the genomes of two or more organisms. In this context, the area of Genome Rearrangements has received considerable attention lately. One way of comparing genomes is given by the rearrangement distance, which is determined by the minimum number of rearrangement events that explain the differences between two genomes. The main studies in rearrangement distance involve reversal and transposition events. The present collection is composed of eight artic1es, containing several important results on Genome Rearrangements. These papers were presented in six conferences, one with Brazilian scope and five with international scope. Two of these works will be published in important international journals, and one other work appeared as a book chapter. Our main contributions can be divided into two groups: a new algebraic formalism and a series of results involving the transposition event. The new algebraic theory relates the genome rearrangement theory to the theory of permutation groups. Our intention was to establish an algebraic formalism that simplifies the creation of new results, up to now excessively based on the construction of diagrams. We studied the transposition event in several ways. Besides presenting results on the transpositions distance between a permutation and its inverse, we also studied the rearrangement problem involving transpositions and reversals simultaneously, constructing approximation algorithms and proposing a conjecture on the diameter. We used the algebraic formalism to show that it is possible to determine the distance of fusion, fission, and transposition in polynomial time. This is the first polynomial time result for a rearrangement problem involving the transposition event. Finally, we introduced two now rearrangement problems: the syntenic distance problem involving fission and fusion, and the prefix transposition problem. For each one of these problems we present significant results, widening the knowledge in this area Doutorado Doutor em Ciência da Computação