Computational Biology Lecture 17: Genome rearrangements, sorting by reversals (cont.)

We continue with the problem of sorting signed permutations by reversal. We first establish a new lower bound on the number of reversals that take the number of hurdles into account. At this point it is beneficial to review the definitions for bad and good components, simple and super hurdles, and a fortress. A new lower bound We will show that dβ(α) ≥ n+1 − cβ(α)+hβ(α). First note that any reversal ρ can “destroy ” at most two hurdles. If ρ is defined by two reality edges in the same component (whether hurdle or not), then it only affects that component. If ρ is defined by two reality edges in different components, then: (1) if both are hurldes, no hurdle can separate them and hence only these two hurdles are affected, (2) if non of them is a hurdle, then at most two hurdles can separate them and hence at most two hurdles are affected, (3) if only one of them is a hurdle, then at most one hurdle can separate them hence at most two hurdles are affected. Let ∆h = h(αρ) − h(α), then ∆h ≥ −2. We define similarly ∆c = c(αρ) − c(α) and ∆(c − h) = ∆c−∆h. It is enough to show that ∆(c − h) ≤ 1 to prove that n+ 1 − cβ(α) + hβ(α) is a lower bound (bounding the increase in c − h after every reversal by 1 and using the fact that cβ(β) − hβ(β) = n+ 1 − 0 = n+ 1). Proof: Given a reversal ρ, we have three cases. case 1: ∆c = 1, then ρ acts on a good cycle and ∆h = 0 (no hurdles destroyed), ∆(c − h) = 1. case 2: ∆c = 0, then ρ acts on a bad cycle and ∆h ≥ −1 (at most one hurdle destroyed), ∆(c − h) ≤ 1