Double Cut and Join Model
The double cut and join (DCJ) model is a model for genome rearrangement used to define an edit distance between genomes based on gene order and orientation, rather than nucleotide sequence. It takes the fundamental units of a genome to be synteny blocks, maximal sections of DNA conserved between genomes. It focuses on changes due to genome rearrangement operations such as inversions, translocations as well as the creation and absorption of circular intermediates. A genome is described as a directed, edge labeled graph with each vertex having degree 1 or 2. Edges are labeled as  synteny blocks, vertices of degree 1 represent telomeres, and vertices of degree 2 representing adjacencies between blocks. This requires that the genome consist of cycles and paths. Each component is called a chromosome. The beginning of each edge is called the tail, the end of each edge is called the head; together heads and tails are known as extremities. Vertices are described by their roles as heads and tails of blocks, for instance, in the figure, the adjacency which forms the head of marker 1 and the tail of marker 2 is labelled (h1, t2), the telomere formed by the  head of 2 is (h2). A double cut and join (DCJ) operation consists of one of the following four transformations: An edit distance, the double cut and join distance, is defined between genomes with the same number of edges formula_1 and formula_2, formula_3 as the minimum number of DCJ operations needed to transform formula_4 into formula_5. Mathematical Results. The DCJ distance defines a metric space. To verify this, we first note that formula_6, since no operations are needed to change G into itself, and if formula_7, formula_8, since at least one operation is needed to transform formula_1 into any other  genome. (A proof that the formula_10 is always defined whenever formula_1 and formula_2 are genomes with the same edges will follow.) Note that each operation has an inverse: (i) and (ii) are their own inverses, and (iii) is the inverse of (iv). Thus formula_13. The triangle inequality formula_14 holds because a series of DCJ operations transforming formula_1 to formula_2 followed by a series of transformations from formula_2 to formula_18 will transform formula_1 to formula_18, so the minimal number of operations needed to transform formula_1 to formula_18 must be no longer than this. To compute the DCJ distance between two genomes  formula_1 and formula_2 with the same set of synteny blocks, we construct a bipartite multigraph known as the adjacency graph formula_25 of the genomes. The vertex set of the adjacency graph is formula_26, where formula_27 is the vertex set of formula_1 and formula_29 is the vertex set of formula_2. For formula_31 and formula_32, we have formula_33 if formula_34 and formula_35 are an extremity of the same synteny block. If formula_34 and formula_35 share two extremities, we add two edges between formula_34 and formula_35 to formula_40. If formula_41, we see that the adjacency graph is composed entirely of paths of length  1, connecting two telomeres, and cycles of length 2, connecting two adjacencies. We can use this fact to calculate formula_42formula_43. Let formula_44 be the number of synteny blocks in genomes formula_1 and formula_2, formula_47 be the number of cycles in their adjacency graph, and formula_48 be the number of paths in their adjacency graph. Then formula_49 The proof shows that each DCJ operation can decrease formula_50 by no more than 1, and that if formula_7, there exists an operation decreasing formula_52. This proves that formula_42 is always defined, and gives a method for its calculation. Since it is easy to  count cycles and paths, formula_42 can be found in linear time.