There will be a few theorems in this section and let's prove the first one, the Breakpoint Theorem. First, let's define the notions of adjacencies and breakpoints looking at this permutation. +3 and +4 are arranged in the right order. In the same order they are arranged in the identity permutation. Let's call it, an adjustment. +4 and +5 is the same story. +5 and -12 is definitely out of order. And certainly, there should be a breakpoint that cuts between them. So, there should be a reversal with one of its endpoints between +5 and -12 because otherwise, we will never be able to transform this permutation into that identity permutation. -12, -8, also breakpoint. This is an interesting case: -8 and -7. It's not +7 and +8 as we want to see in the identity permutation, but maybe there will be a reversal that contains both -8 and -7 and then after reversing, they will turn into a perfect permutation and will correspond to the case +7 and +8 and that's why we say -8 and -7 are in order, despite being inverted. -7, -6... the same story. -6 +1 is definitely a breakpoint, adjacency breakpoint. This is also a breakpoint, think about why it is a breakpoint. Again, breakpoint, breakpoint and finally, adjacency. We're done not quite yet, because there are two more implicit elements of this permutation, 0 and n+1 that describe the start and end of this permutation. And 0, +3 is the break point because 0 should not be next to +8, it should be next to +1. And +14 and +15 is adjacency. So after we define adjacencies and breakpoints, clearly the number of adjacencies plus the number of breakpoints in the permutation equals to the length of the permutation plus 1. And before we go further, I want to ask you a question. Well, what is the number of breakpoints in the identity permutation, +1, +2, ..., +n? Of course, this permutation has no breakpoints, zero, which means that sorting by reversal is essentially breakpoint elimination. Let's see how it works. So let's start from the initial permutation that has six breakpoints. We move next, there are only four breakpoints left. We move left, again, four breakpoints left. We move further, two breakpoints, and finally, in the identity permutation, zero breakpoints,which means that every sorting by reversal should reduce the number of breakpoints from six to zero in this case. We don't know what sequence of reversal is minimal, but we know that any or each of them will result in the reduction of the number of breakpoints to zero. Next question: how many breakpoints can be eliminated by a single reversal? Well, the answer to this question is simple; reversal has two ends and nothing happens with these breakpoints on the left and on the right of those end points. Also, every breakpoint that existed within this interval will remain the breakpoint. And therefore, the only breakpoints that can be affected by reversals are the two breakpoints on the end of the reversals. And since at every step, the number of breakpoints can be reduced by at most, two, we have the breakpoint theorem. Reversal distance should be larger or equal than the number of breakpoints over/divided by two. And it also immediately suggests a new Greedy algorithm and probably a better Greedy algorithm for sorting by reversal. Indeed, the only thing we need to do to sort a permutation optimally is to reduce the number of breakpoints by two at every step. Let's look at our segments of sorting by reversals and we see that at this step, we did something silly. We were supposed to be reducing the number of breakpoints by two at every step, but the number of breakpoints actually has not even reduced at this reversal. Maybe we should have chosen another reversal that would reduce the number of breakpoints by two, but you can check that there is no such reversal. And in fact, there are permutations for which there are no reversal reducing number of breakpoints even by one, which means whatever you do, the number of breakpoints remains the same. And that's why it turns out that the algorithm for sorting by reversals is actually quite complex. Even if I had an hour or two of time one on one with you, I wouldn't be able to explain all intricacies of the polynomial algorithm for sorting by reversals. And that's why I will switch from the problem of sorting by reversal to a different, seemingly even more difficult problem of finding rearrangements and optimal sorting by of multi-chromosomal genomes.
