<p>Denote the strips in your permutation as <span class="math-container">$\langle S_1, S_2, \cdots, S_n \rangle$</span>. Suppose <span class="math-container">$k-1$</span> is in segment <span class="math-container">$S_i$</span>, and <span class="math-container">$k$</span> is in segment <span class="math-container">$S_j$</span>, for some <span class="math-container">$i, j \in [n], i \neq j$</span>.</p>

<p>Recall by definition of <span class="math-container">$k$</span> that <span class="math-container">$k-1$</span> must be the maximum and therefore rightmost element in an increasing strip, and <span class="math-container">$k$</span> the minimum and therefore also rightmost in a decreasing strip. Consider the two cases:</p>

<ul>
<li><span class="math-container">$i &lt; j$</span>. The increasing strip comes before the decreasing. <span class="math-container">$k-1$</span> is on the 'right' end of <span class="math-container">$S_i$</span>, but <span class="math-container">$k$</span> is on the 'right' end of <span class="math-container">$S_j$</span> also. In order for <span class="math-container">$k-1$</span> and <span class="math-container">$k$</span> to be adjacent, reverse the segments <span class="math-container">$S_{i+1}, \cdots, S_j$</span>.</li>
<li><span class="math-container">$j &lt; i$</span>. The decreasing strip comes before the increasing. <span class="math-container">$k$</span> is on the 'right' end of <span class="math-container">$S_j$</span>, but <span class="math-container">$k-1$</span> is on the 'right' end of <span class="math-container">$S_i$</span> also. Again, we reverse <span class="math-container">$S_{i+1}, \cdots, S_j$</span>.</li>
</ul>

<p>So, "reversing the segment between <span class="math-container">$k$</span> and <span class="math-container">$k-1$</span>" means to reverse all the strips in-between the two strips containing <span class="math-container">$k$</span> and <span class="math-container">$k-1$</span>, excluding the 'leftmost' strip, but including the 'rightmost' strip.</p>

CC BY-SA 4.0
2019-11-19T08:08:37.110Z
2019-11-19T08:08:37.110Z
ning
<p>I'm kind of new to bioinformatics and trying to self-study. I'm reading a bioinformatics book: <em>An Introduction to Bioinformatics Algorithms</em> and ran into some problems about understanding the proof of the Breakpoint Reversal Sort algorithm in chapter 5.4. </p>

<p>Specifically, the book states a theorem: </p>

<blockquote>
  <p>If a permutation <span class="math-container">$\pi$</span> contains a decreasing strip, then there is a reversal <span class="math-container">$\rho$</span> that decreases the number of breakpoints in <span class="math-container">$\pi$</span>, that is, breakpoint (<span class="math-container">$\rho(\pi)$</span>) &lt; breakpoint(<span class="math-container">$\pi$</span>).</p>
</blockquote>

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

<blockquote>
  <p>Let <span class="math-container">$k$</span> be the smallest element of decreasing strip, so element <span class="math-container">$k-1$</span> would be the ending of an increasing strip. Therefore element <span class="math-container">$k$</span> and <span class="math-container">$k-1$</span> corresponds to a breakpoint. Then reversing the segment between <span class="math-container">$k$</span> and <span class="math-container">$k-1$</span> will decrease the number of breakpoints.  </p>
</blockquote>

<p>I'm quite confused about this proof and don't really understand what the authors mean by reversing the segment between <span class="math-container">$k$</span> and <span class="math-container">$k-1$</span>. Can someone please explain the proof for me? </p>

<p>Here's the lecture slide about reversal sorting that based on the book <a href="http://csbio.unc.edu/mcmillan/Media/Lecture07Spring2015.pdf" rel="nofollow noreferrer">http://csbio.unc.edu/mcmillan/Media/Lecture07Spring2015.pdf</a>.  </p>

CC BY-SA 4.0
2019-01-08T17:33:22.537Z
Check out [this lecture](https://cseweb.ucsd.edu/classes/wi05/cse206b/notes/L3.pdf) for an easier understanding.
d_kennetz
<phylogenetics><genomics>
Proof of Breakpoint Reversal Sorting Approximation Algorithm
# Proof of Breakpoint Reversal Sorting Approximation Algorithm

(Asked by: username_0 on 2019-01-06)

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>.

**Tags:** phylogenetics, genomics
> **Comments:**
> **username_1**: Check out [this lecture](https://cseweb.ucsd.edu/classes/wi05/cse206b/notes/L3.pdf) for an easier understanding.  

---

## 1 answers

### Answer by username_2 on 2019-11-19. Score: 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.


---

