
How Did We Get Here? Permutations as Genome Rearrangements. 361
(a) If P
a
and P
b
are part of the same alternating cycle C
ab
of G(p),
that is, when there is an alternating path A
da
from d to a ending in
a gray edge, then in G(p
), the cycle C
ab
will be replaced by three
cycles, namely the two-vertex cycles x − 1 x and yy+1, andthe
cycle that contains b, d, the path A
da
,andc. Other cycles will not
change. See Figure 9.4 for an illustration.
x−1 a
yc
db
x y+1
x−1
d
y
x
b
ca
y+1
p
p’
FIGURE 9.4
The canonical block interchange of p when y and x are not adjacent, but are
part of the same cycle of G(p).
(b) If P
a
and P
b
are part of two distinct cycles C
a
and C
b
of G(p), then
in