Portal de Periódicos da CAPES

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

2002; Sociedade Brasileira de Matemática Aplicada e Computacional; Volume: 3; Issue: 1 Linguagem: Português

10.5540/tema.2002.03.01.0213

2179-8451

Maria Emília M. T. Walter, Eugenia T.G. Oliveira,

Algorithms and Data Compression

Rearranjos de Genomas em Biologia Computacional e uma area na qual basicamente se visa resolver um problema combinatorial de encontrar uma serie minima de eventos mutacionais, afetando porcoes grandes do genoma, que transformam um genoma em outro. Neste artigo, estudamos o evento de transposi cao, que move um bloco de genes de um local para outro, dentro de um unico cromossomo. Este evento leva ao problema da ordenacao por transposicoes, que visa encontrar a menor seq¨uencia de transposicoes que transforma um genoma em outro. Bafna e Pevzner [1] propuseram uma teoria baseada em propriedades de uma estrutura denominada grafo de ciclos, nao inteiramente detalhada. Portanto, nossa contribuicao e completar a teoria de Bafna e Pevzner [1]. Com base nestes resultados, apresentamos uma implementacao e diversos experimentos.