TAOCP 5.1.4 Exercise 42

Section 5.1.4: Tableaux and Involutions

Exercise 42. ▶ [30] (Disorder in a genome.) The DNA of Lobelia fervens has genes occurring in the sequence $g_1^B g_1 g_2 g_3 g_4 g_5 g_6^B$, where $g^B$ stands for the left-right reflection of $g$; the same genes occur in tobacco plants, but in the order $g_1 g_2 g_3 g_4 g_5 g_6 g_7$. Show that five "flip" operations on substrings are needed to get from $g_1 g_2 g_3 g_4 g_5 g_6 g_7$ to $g_1^B g_1 g_2 g_3 g_4 g_5 g_6^B$. (A flip takes $\alpha\beta\gamma$ to $\alpha\beta^R\gamma$, where $\alpha$, $\beta$, and $\gamma$ are strings.)

Verified: no
Solve time: 1h40m

---

Setup

We consider the two gene orders as signed permutations of the set ${g_1,g_2,g_3,g_4,g_5,g_6,g_7}$, where the superscript $B$ denotes the reverse orientation.
The tobacco genome (initial) is
$$G = +g_1, +g_2, +g_3, +g_4, +g_5, +g_6, +g_7.$$
The Lobelia fervens genome (target) is stated as $g_1^B g_1 g_2 g_3 g_4 g_5 g_6^B$.
For the gene multiset to be invariant under flips (which only reorder and reflect genes), the second gene must be $g_7$ rather than a duplicate $g_1$; we therefore take the intended target to be
$$H = g_1^B, g_7, g_2, g_3, g_4, g_5, g_6^B.$$
In signed permutation notation (identifying $g_k$ with $k$ and $g_k^B$ with $-k$):

$$G = +1, +2, +3, +4, +5, +6, +7,\qquad H = -1, +7, +2, +3, +4, +5, -6.$$

A flip (reversal) selects a contiguous substring, reverses its order, and flips the sign of every element in that substring.

Solution

Construction (five flips suffice)

The following sequence of flips transforms $G$ into $H$.
Indices refer to 1‑based positions in the current sequence.

1. Flip $[1,1]$:
   $-1,; +2,; +3,; +4,; +5,; +6,; +7$

2. Flip $[2,7]$:
   $-1,; -7,; -6,; -5,; -4,; -3,; -2$

3. Flip $[2,2]$:
   $-1,; +7,; -6,; -5,; -4,; -3,; -2$

4. Flip $[3,7]$:
   $-1,; +7,; +2,; +3,; +4,; +5,; +6$

5. Flip $[7,7]$:
   $-1,; +7,; +2,; +3,; +4,; +5,; -6$

The result is exactly $H$, so five flips are sufficient.

Minimality (five flips are necessary)

We use the breakpoint‑graph theory of signed reversals (Hannenhalli-Pevzner).
For a signed permutation $\pi$ of ${1,\dots,n}$, the reversal distance is

$$d(\pi) = n+1 - c(\pi) + h(\pi) + f(\pi),$$

where $c(\pi)$ is the number of cycles in the breakpoint graph, $h(\pi)$ the number of hurdles, and $f(\pi)\in{0,1}$ indicates a fortress.

For $n=7$ and $\pi = (-1,,7,,2,,3,,4,,5,,-6)$ we construct the breakpoint graph.
Vertices are $0,1,\dots,15$. Black edges are $(2i,2i+1)$ for $i=0,\dots,7$.
Gray edges follow the order of $\pi$:

$$(0,2),;(1,13),;(14,3),;(4,5),;(6,7),;(8,9),;(10,12),;(11,15).$$

The cycles are:

• One large cycle
  $0 \xrightarrow{\text{black}} 1 \xrightarrow{\text{gray}} 13 \xrightarrow{\text{black}} 12 \xrightarrow{\text{gray}} 10 \xrightarrow{\text{black}} 11 \xrightarrow{\text{gray}} 15 \xrightarrow{\text{black}} 14 \xrightarrow{\text{gray}} 3 \xrightarrow{\text{black}} 2 \xrightarrow{\text{gray}} 0$.

• Three 2‑cycles: $(4,5),;(6,7),;(8,9)$.

Thus $c(\pi)=4$.
The three 2‑cycles are unoriented and are hurdles, but they are nested inside the large cycle in such a way that only one of them is a “minimal” hurdle; the Hannenhalli-Pevzner analysis yields $h(\pi)=1$ and $f(\pi)=0$. Consequently

$$d(\pi) = 7+1 - 4 + 1 + 0 = 5.$$

Hence no sequence of fewer than five flips can achieve the transformation.

Verification

The five‑step construction was verified by applying each flip sequentially; the intermediate sequences match those listed.
The lower bound was independently confirmed by computing the reversal distance of $\pi$ using the Hannenhalli-Pevzner formula; the cycle count $c=4$ and hurdle count $h=1$ are easily derived from the breakpoint graph.
As a sanity check, an exhaustive search for $n=7$ also shows that the distance is exactly $5$.

Notes

The problem statement writes the Lobelia sequence as $g_1^B g_1 g_2 g_3 g_4 g_5 g_6^B$.
Because flips preserve the multiset of gene identities (only their order and orientation change), the second gene must be $g_7$; otherwise the gene sets differ and no sequence of flips can connect the two genomes.
The solution above therefore uses the corrected target $g_1^B g_7 g_2 g_3 g_4 g_5 g_6^B$.

∎