Most algorithms for the genome rearrangement distance need the decomposition of a Breakpoint Graph into cycles of alternating colors [1]}, [2]}, [3]}. [4]} developed heuristics for finding decompositions of Breakpoint Graphs based on the Tabu Search metaheuristic [5]}, [6]}, and presented experimental results on simulated data.
[7]} showed a polynomial-time reduction from the Maximum Breakpoint Graph Decomposition problem to the Maximum Eulerian Cycle Decomposition problem. Therefore, the results presented here have direct application in the genome rearrangement distance problem.
