Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-19T08:08:37.110Z
Answers.LastActivityDate: 2019-11-19T08:08:37.110Z
Answers.UserDisplayName: ning
Body: <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>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-01-08T17:33:22.537Z
Comments.Text: Check out [this lecture](https://cseweb.ucsd.edu/classes/wi05/cse206b/notes/L3.pdf) for an easier understanding.
Comments.UserDisplayName: d_kennetz
Tags: <phylogenetics><genomics>
Title: Proof of Breakpoint Reversal Sorting Approximation Algorithm
ThreadText: # 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.
  
  
  ---
  
  