A framework for cost-constrained genome rearrangement under Double Cut and Join.

The study of genome rearrangement has many flavours, but they all are somehowtied to edit distances on variations of a multi-graph called the breakpointgraph. We study a weighted 2-break distance on Eulerian 2-edge-coloredmulti-graphs, which generalizes weighted versions of several Double Cut andJoin problems, including those on genomes with unequal gene content. We affirmthe connection between cycle decompositions and edit scenarios first discoveredwith the Sorting By Reversals problem. Using this we show that the problem offinding a parsimonious scenario of minimum cost on an Eulerian 2-edge-coloredmulti-graph - with a general cost function for 2-breaks - can be solved bydecomposing the problem into independent instances on simple alternatingcycles. For breakpoint graphs, and a more constrained cost function, based oncoloring the vertices, we give a polynomial-time algorithm for finding aparsimonious 2-break scenario of minimum cost, while showing that finding anon-parsimonious 2-break scenario of minimum cost is NP-Hard.