# Proof of Breakpoint Reversal Sorting Approximation Algorithm

I'm kind of new to bioinformatics and trying to self-study. I'm reading a bioinformatics book: An Introduction to Bioinformatics Algorithms and ran into some problems about understanding the proof of the Breakpoint Reversal Sort algorithm in chapter 5.4.

Specifically, the book states a theorem:

If a permutation $$\pi$$ contains a decreasing strip, then there is a reversal $$\rho$$ that decreases the number of breakpoints in $$\pi$$, that is, breakpoint ($$\rho(\pi)$$) < breakpoint($$\pi$$).

This theorem guarantees that the algorithm will terminate and lead to no breakpoint. The book later explains the proof for the theorem:

Let $$k$$ be the smallest element of decreasing strip, so element $$k-1$$ would be the ending of an increasing strip. Therefore element $$k$$ and $$k-1$$ corresponds to a breakpoint. Then reversing the segment between $$k$$ and $$k-1$$ will decrease the number of breakpoints.

I'm quite confused about this proof and don't really understand what the authors mean by reversing the segment between $$k$$ and $$k-1$$. Can someone please explain the proof for me?

Here's the lecture slide about reversal sorting that based on the book http://csbio.unc.edu/mcmillan/Media/Lecture07Spring2015.pdf.

• Check out this lecture for an easier understanding. Jan 8, 2019 at 17:33

Denote the strips in your permutation as $$\langle S_1, S_2, \cdots, S_n \rangle$$. Suppose $$k-1$$ is in segment $$S_i$$, and $$k$$ is in segment $$S_j$$, for some $$i, j \in [n], i \neq j$$.
Recall by definition of $$k$$ that $$k-1$$ must be the maximum and therefore rightmost element in an increasing strip, and $$k$$ the minimum and therefore also rightmost in a decreasing strip. Consider the two cases:
• $$i < j$$. The increasing strip comes before the decreasing. $$k-1$$ is on the 'right' end of $$S_i$$, but $$k$$ is on the 'right' end of $$S_j$$ also. In order for $$k-1$$ and $$k$$ to be adjacent, reverse the segments $$S_{i+1}, \cdots, S_j$$.
• $$j < i$$. The decreasing strip comes before the increasing. $$k$$ is on the 'right' end of $$S_j$$, but $$k-1$$ is on the 'right' end of $$S_i$$ also. Again, we reverse $$S_{i+1}, \cdots, S_j$$.
So, "reversing the segment between $$k$$ and $$k-1$$" means to reverse all the strips in-between the two strips containing $$k$$ and $$k-1$$, excluding the 'leftmost' strip, but including the 'rightmost' strip.