Ordenação por transposições baseado no formalismo algébrico

Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2006.Biologia Computacional é uma área da Ciência da Computação que tem por objetivo o estudo e aplicação de técnicas e ferramentas computacionais aos problemas da Biologia Molecular. Dentre os problemas pesquisados, encontra-se o de evolução molecular, onde são estudados métodos para comparar seqüências de espécies distintas, baseados em eventos mutacionais. Estes métodos geram medidas de distância, que podem ser empregadas para verificar o relacionamento em termos evolutivos entre dois organismos. Uma técnica de computar distância é comparar blocos, formados por um ou mais genes, de genomas de dois organismos. O nosso trabalho pertence à área de Rearranjo de Genomas que, de forma genérica, visa resolver o problema combinatorial de encontrar uma seqüência mínima de eventos de rearranjo (mutações) que transformam um genoma em outro. Estudamos um evento de rearranjo específico – transposição, que move uma porção de genes de um local para outro dentro do mesmo cromossomo. Este evento gera o problema da ordenação por transposições, que consiste em computar e encontrar a menor seqüência de transposições que transformam um genoma em outro. Neste trabalho propusemos dois algoritmos de aproximação baseados no formalismo algébrico de Dias e Meidanis para o problema de ordenação por transposições. Implementamos estes algoritmos utilizando a linguagem Java e comparamos os resultados obtidos com outros encontrados na literatura. Este trabalho visa contribuir para encontrar a complexidade do problema de ordenação por transposições que ainda não é conhecida. _________________________________________________________________________________________ ABSTRACTComputational Biology is an area that aims to study and to apply techniques and computational tools to problems of molecular biology. One of these problems is molecular evolution, in which methods are proposed for comparing sequences of distinct species, based on mutational events. These methods generate distance measures that could be employed to verify the evolutionary relationship between two organisms. A technique to compute distance is to compare blocks, composed by one ore more genes, of the genomes of two organisms. This work belongs to the field of genome rearrangement, that has the objective to solve the combinatorial problem of finding a minimum sequence of rearrangement events that transform a genome into another. We studied a particular rearrangement event - transposition, that moves a portion of genes from a local to another inside one chromosome. This event generates the problem of sorting by transpositions, that consists in computing and finding the minimum sequence of transpositions that transform a genome into another. In this work, we proposed two approximation algorithms based on the algebraic formalism of Dias and Meidanis to solve the problem of sorting by transpositions. We implemented these algorithms using the Java language, and compared the results obtained with the results of other algorithms found in the literature. This work aims to contribute to find the complexity of this problem still unknown