Single Tandem Halving by Block Interchange - Biomedical Engineering Systems and Technologies - page 143

2.2 Rearrangements

A rearrangement operation on a given genome cuts a set of adjacencies of the genome
called breakpoints and forms new adjacencies with the exposed extremities, while alter-
ing no other adjacency. In the sequel, the adjacencies cut by a rearrangement operation
are indicated in the genome by the symbol .
An interval in a genome is a set of markers that appear consecutively in the genome.
Given two different adjacencies ( ab ) and ( cd ) in a genome G such that ( ab ) < ( cd ) ,
[ b ; c ] denotes the interval of G beginning with marker b and ending with marker c .
In this paper, we consider two types of rearrangement operations called block inter-
change (BI) and double-cut-and-join (DCJ) .
A block interchange (BI) on a genome G is a rearrangement operation that acts on
four adjacencies in G , ( ab ) < ( cd ) ( uv ) < ( xy ) such that the intervals [ b ; c ]

and [ v ; x ] do not overlap, swapping the intervals [ b ; c ] and [ v ; x ] . For example, the
following block interchange acting on adjacencies (12) < (6 6) < (38) < (8 7)
consists in swapping the intervals [2 , 6] and [8 , 8] .

≤

( ◦ 1 1 232456 673 8 495 8 7 9 ◦ )

↓

( ◦ 1 1 8 495 8 673 232456 7 9 ◦ )

A double-cut-and-join (DCJ) operation on a genome G cuts two different adjacencies
in G and glues pairs of the four exposed extremities to form two new adjacencies. Here,
we focus on two types of DCJ operations called excision and integration .
An excision is a DCJ operation acting on a single chromosome by extracting an in-
terval from it, making this interval a circular chromosome, and making the remainder a
single chromosome.For example, the following excision extracts the circular chromo-
some (234) :

( ◦ 1 234 56 ◦ ) → ( 234 )( ◦ 156 ◦ )

An integration is the inverse of an excision; it is a DCJ operation that acts on two
chromosomes, one being a circular chromosome, to produce a single chromosome. For
example, the following operation is an integration of the circular chromosome (234) :

( 2 34 )( ◦ 156 ◦ ) → ( ◦ 156 342 ◦ )

We now give an obvious, but very useful, property linking BI operations to DCJ opera-
tions.

Property 1. A single BI operation on a linear chromosome is equivalent to two DCJ
operations: an excision followed by an integration.

Proof. Let ( ) be a genome, U and V the two intervals that are to be

swapped by a block interchange operation, 12 and 3 the intervals constituting the rest
of the genome (note that each of them may be empty).
The first DCJ operation is the excision that produces the adjacency (1 V ) by extract-
ing and circularizing the interval [ U ;2] :

◦ 1 U 2 V 3 ◦