Title: A framework for cost-constrained genome rearrangement under Double Cut and Join,
Abstract: The study of genome rearrangement has many flavours, but they all are somehow
tied to edit distances on variations of a multi-graph called the breakpoint
graph. We study a weighted 2-break distance on Eulerian 2-edge-colored
multi-graphs, which generalizes weighted versions of several Double Cut and
Join problems, including those on genomes with unequal gene content. We affirm
the connection between cycle decompositions and edit scenarios first discovered
with the Sorting By Reversals problem. Using this we show that the problem of
finding a parsimonious scenario of minimum cost on an Eulerian 2-edge-colored
multi-graph - with a general cost function for 2-breaks - can be solved by
decomposing the problem into independent instances on simple alternating
cycles. For breakpoint graphs, and a more constrained cost function, based on
coloring the vertices, we give a polynomial-time algorithm for finding a
parsimonious 2-break scenario of minimum cost, while showing that finding a
non-parsimonious 2-break scenario of minimum cost is NP-Hard.