We'll now talk about the algorithmic problem of sorting by reversals. Let's start from a short chromosome consisting of just 10 blocks and we'll number them in the order 1, 2, 3 to 10. Now a reversal... we can think about a reversal as something that breaks a chromosome at two places and glues the resulting pieces in a new order as shown on this slide. And as a result, the reversal introduces two breakpoints, disruptions in the gene order. For example, +3 and -8 are not supposed to be together but they are together in the new permutation, and the same thing applies to -4 and +9. So let's take a look at one of the possible rearrangement scenarios. In this case, transforming a permutation into an identity permutation which is +1 +2 +8 with these five reversals. Is it the shortest scenario? No, because there is a shorter scenario that transforms the same permutation into identity with just four reversals. And we will define reversal distance as the minimum number of reversals to transform one permutation into another. Biologists are often interested in shortest scenarios for transforming one genome into another because this shorter scenario often corresponds to the biological scenario or comes close to the biological scenarios. So we now have a transformation of one genome into another with just four reversals, but maybe there is even faster transformations of these genomes with just three reversals. And the reversal distance problem is the problem of calculating the reversal distance between two permutations. Input: two permutations, Output: the reversal distance between them. We will also be talking about sorting by reversal problem which uses an input of just a single permutation and ask for the reversal distance between this permutation and the identity permutation +1, +2, ..., +n Why identity permutations? Because we are at liberty to label the final permutation the way we want and we usually label this as +1, +2, +3, .... Now, what would be the most natural algorithm for sorting by reversals? I'm not saying good algorithm, but the most natural one? Let's look at this mouse permutation, for an example of this case. +1 is already in the right position in this permutation, but +2 is not. However, we can use a reversal, shown in bold here, to bring plus 2 at the right position. That's what we've done right here. We brought +2 at the right position, but now it has a wrong sign. Not a problem. We will reverse the sign using a short reversal right here. Now, we placed both +1 and +2at the right position, but -3 is at the wrong position. Not a problem, we'll find a reversal that brings it at the right position. Now let's take care of +4. Once again, let's find a reversal that brings it to the right position. It now has wrong sign, but we will reverse it. And we will continue doing this until we finally, using this Greedy algorithm, transform mouse into Philip. And after we looked at the Greedy algorithm for sorting by reversal, you may notice that of course, it's not optimal. We used 11 reversals to transform mouse into human permutations, but we know from the first slide in this lecture that it can be done in just seven reversals. So, maybe we should come up with a better algorithm, and to do this we will have to define the notion of a breakpoint graph.