Search

The rearrangement distance is a method to compare genomes of different species. Such distance is the number of rearrangement events necessary to transform one genome into another. Two commonly studied events are the transposition, which exchanges two consecutive blocks of the genome, and the reversal, which reverts a block of the genome. When dealing with such problems, seminal works represented genomes as sequences of genes without repetition. More realistic models started to consider gene repetition or the presence of intergenic regions, sequences of nucleotides between genes and in the extremities of the genome. This work explores the transposition and reversal events applied in a genome representation considering both gene repetition and intergenic regions. We define two problems called Minimum Common Intergenic String Partition and Reverse Minimum Common Intergenic String Partition. Using a relation with these two problems, we show a $$\Theta \left( k \right)$$ Θ k -approximation for the Intergenic Transposition Distance, the Intergenic Reversal Distance, and the Intergenic Reversal and Transposition Distance problems, where k is the maximum number of copies of a gene in the genomes. Our practical experiments on simulated genomes show that the use of partitions improves the estimates for the distances.

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