Ordenação por Transposições baseado no Formalismo Algébrico
AUTOR(ES)
Héderson Pereira dos Santos
DATA DE PUBLICAÇÃO
2006
RESUMO
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.
ASSUNTO(S)
computational biology problem of sorting by transpositions biologia computacional genome rearrangements problema da ordenação por transposições, formalismo algébrico ciencia da computacao rearranjo de genomas algebraic formalism
