A general framework for genome rearrangement with biological constraints

Eulerian 2-edge-color multi-graphs for genomes A = ( { 3 t , 1 t } , { 1 h , 2 h } , { 2 t , 3 h } ) , ( { 4 t } , { 4 h , 1 t } , { 1 h } ) , B = ( { 1 h , 2 h } , { 2 t , 1 t } ) , ( { 3 t , 2 h } , { 2 t , 1 h } , { 1 t , 3 h } ) , and A ′ = ( { 3 t , 2 h } , { 2 t , 1 t } , { 1 h , 2 h } , { 2 t , 3 h } ) , ( { 4 t } , { 4 h , 1 t } , { 1 h } ) . Edges adjacent to a special vertex ° represent the endpoints of linear chromosomes (e.g. black edges { 1 h , ° } and { 4 t , ° } ). Extra edges are added for the missing genes (e.g. the black edge { 2 t , 2 h } and the gray edge { 4 h , 4 t } ), called ghost adjacencies in [15]. In the genomes A and A ′ , gene 1 is repeated twice, and the operation transforming A into A ′ is an insertion of a gene 2, corresponding to the 2-break G ( A , B ) → G ( A ′ , B ) . A DCJ scenario transforming A ′ into the linear genome B includes a deletion of a gene