6

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.

Eric Leung
  • 155
  • 1
  • 5
Hang Le
  • 61
  • 2

1 Answers1

1

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.

ning
  • 141
  • 5