The Genome Rearrangement Distance Problem Using Fusion, Fission, and Transpositions with Arbitrary Weights

Abstract: Recently we have shown that given two multi-chromossomal genomes it is easy to compute the minimum weight series of fusions, fissions, and transpositions needed to transform one genome into the other, when the weight associated to transpositions is twice as large as that associated to fusions and fissions. In this work we present several results on the computation of distance when an arbitrary weight is associated to transpositions. Some variations of the problem are also studied. For instance we present a polynomial time algorithm for the problem of syntenic distance when only the events of fusions and fissions are admitted.



Resumo: Recentemente foi mostrado que dados dois genomas multi-cromossomais é fácil calcular a série de peso mínimo de fusões, fissões e transposições necessárias para transformar um genoma no outro, quando é associado um peso duas vezes maior as transposições do que as fusões e fissões. Neste trabalho trabalho apresentaremos vários resultados sobre o problema da distância de fusão, fissão e transposição quando associamos pesos arbitrários às transposições. Algumas variações do problema também serão aqui estudadas. Por exemplo, apresentaremos um algoritmo polinomial para o problema da distância sintênica quando apenas os eventos de fusão e fissão são admissíveis.

2002