Estendendo a Teoria de Bafna e Pevzner para o Problema da Ordenação por Transposições

Abstract

Rearranjos de Genomas em Biologia Computacional é uma área na qual basicamente se visa resolver um problema combinatorial de encontrar uma série mínima de eventos mutacionais, afetando porções grandes do genoma, que transformam um genoma em outro. Neste artigo, estudamos o evento de transposi ção, que move um bloco de genes de um local para outro, dentro de um único cromossomo. Este evento leva ao problema da ordenação por transposições, que visa encontrar a menor seq¨uência de transposições que transforma um genoma em outro. Bafna e Pevzner [1] propuseram uma teoria baseada em propriedades de uma estrutura denominada grafo de ciclos, não inteiramente detalhada. Portanto, nossa contribuição é completar a teoria de Bafna e Pevzner [1]. Com base nestes resultados, apresentamos uma implementação e diversos experimentos.