Genome RearrangementsQuick ReviewOriented BlocksUnoriented BlocksDefinitionsDefinitions (cont.)Example 1Example 1 (cont.)Best Solution?BreakpointsExample 2Example 2 (cont.)StripsStrips (cont.)Special RulesExample 3Theorem 1ProofProof (cont.)Example 4ObservationsTheorem 2Slide 23Example 5The ResultTheorem 3Slide 27Slide 28Slide 29Slide 30Example 6Sorting a PermutationGeneral IdeaChoosing the Reversal sSorting AlgorithmAnother ExampleBut is it Optimal?Theorem 4Slide 39Genome RearrangementsUnoriented BlocksQuick ReviewLooking at evolutionary change through reversalsFind the shortest possible series of reversals that transform gene A into gene BIt has been shown that this results in an NP-Hard problemOriented Blocks1 2 3 4 55 2 1 3 41 2 3 4 51 2 5 4 31 2 5 3 45 2 1 3 4Unoriented BlocksOrientation of the blocks in the genomes is unknown2 1 3 7 5 4 8 61 2 3 4 5 6 7 8Definitionsunoriented permutation - a mapping from {1,2,…,n} to a set L of n labels.reversal – reverses the order of a segment of consecutive labels.Definitions (cont.)reversal distance – if p1,p2,…pt is a shortest series of reversals such that αp1p2…pt = β ,t is the reversal distance of α with respect to β, denoted by dβ(α)Example 1 2 1 3 7 5 4 8 61 2 3 4 5 6 7 8• Assign labels 1 through 8 to the blocks in the lower chromosome• Transfer the labels to the upper chromosome giving equal labels to homologous blocks• We obtain a starting permutation in the upper chromosome and our goal is to sort it into the lower one, the identityFigure below shows two chromosomes with homologous blocksExample 1 (cont.)2 1 3 7 5 4 8 61 2 3 7 5 4 8 61 2 3 4 5 7 8 61 2 3 4 5 7 6 81 2 3 4 5 6 7 8Best Solution?How do we know that this is the shortest series of reversals?To decide what the reversal distance should be, we look at the breakpointsBreakpointsA breakpoint of an unoriented permutation α is a pair of labels adjacent in α but not in the target. In the case of the identity, this means adjacent labels that are not consecutive.Example 2Assume the identity is the target…Breakpoints with oriented blocks:L 5 2 1 3 4 RBreakpoints with unoriented blocks:L 5 2 1 3 4 RExample 2 (cont.)L 2 1 3 7 5 4 8 6 R• b(α) denotes the number of breakpoints of α• a reversal can remove at most two breakpoints hence:d(α) > ( b(α) / 2 ) where d(α) is the reversal distance• using this rule, we see that d(α) > 4 for the above exampleStripsL 4 5 3 2 1 RIf we have two adjacent labels that do not make a breakpoint, they must be of the form:…x(x+1)or…x(x-1)Strips (cont.)strip – a sequence of consecutive labels surrounded by breakpoints but with no internal breakpointsTwo types of strips: increasingdecreasingSpecial RulesA single label surrounded by breakpoints is said to be a strip that is both increasing and decreasingL and R are always considered part of an increasing strip, even if they are by themselvesL and R are considered a single element for the purpose of defining strips. If 0, 1, … is a strip and …, n, n+1 is a strip, we consider these two sequences as a single strip. They are linked by the common element L = R.Example 3L 1 2 8 7 3 5 6 4 RStripsincreasing: (R,L,1,2) (5,6) decreasing: (8,7) both: (3) (4)Theorem 1If label k belongs to a decreasing strip and k - 1 belongs to an increasing strip, then there is a reversal that removes at least one breakpointL 4 5 2 3 1 7 6 Rkk-1ProofLabels k – 1 and k must belong to different strips, since only single elements are said to be both increasing and decreasing.The above statement implies that each one is the last element in its strip (each is followed by a breakpoint).Proof (cont.)Two possible schemes:… (k - 1) … k …… k … (k - 1) …Performing a reversal on the area between the breakpoints brings k and k-1 together, reducing the number of breakpoints by at least one.Example 4L 4 5 2 3 1 7 6 RL 4 5 2 3 1 7 6 RL 4 5 6 7 1 3 2 RL 4 5 6 7 1 3 2 Rkk-1ObservationsAll permutations have at least one increasing strip (L or R)All permutations do not necessarily have a decreasing stripIf there is a decreasing strip, the previous proof shows that there is a breakpoint-removing reversalTheorem 2If label k belongs to a decreasing strip and k + 1 belongs to an increasing strip, then there is a reversal that removes at least one breakpoint.L 5 4 2 3 1 6 7 Rk k+1ProofTwo possible schemes: (k + 1) … k … k … (k + 1) …Performing a reversal on the area between the breakpoints brings k and k+1 together, reducing the number of breakpoints by at least one.Example 5L 5 4 2 3 1 6 7 RL 5 4 2 3 1 6 7 RL 1 3 2 4 5 6 7 RL 1 3 2 4 5 6 7 Rk+1kThe ResultThe two proofs just explained show that, as long as we have decreasing strips, we can always reduce the number of breakpoints.Notice that this also applies to single-element stripsWhat about when there are no decreasing strips?Theorem 3Let α be a permutation with a decreasing strip. If all reversals that remove breakpoints from α leave no decreasing strips, then there is a reversal that removes two breakpoints from α.ProofLet k be the smallest label involved in a decreasing strip. p is the reversal uniting k and k - 1k – 1 must be to the left of k, otherwise p leaves a decreasing strip.… (k – 1) … k …Proof (cont.)Let ℓ be the largest label involved in a decreasing strip. σ is the reversal uniting ℓ and ℓ + 1ℓ + 1 must be to the right of ℓ, otherwise σ leaves a decreasing strip… ℓ … (ℓ + 1) …Proof (cont.)Observe that k must be inside the interval reversed by σ, otherwise σ would leave k ’s decreasing strip intact.Likewise, ℓ must belong to the interval of p… (k – 1) ℓ … k (ℓ + 1) …Proof (cont.)… (k – 1) ℓ … k (ℓ + 1) …We can see that p = σ must be trueThe reversal removes two breakpoints because k is united with k – 1 and ℓ is united with ℓ + 1Example 6L 7 8 3 5 4 6 1 2 RReversals that remove breakpointsL 7 8 3 5 4 6 1 2 RL 7 8 3 4 5 6 1 2 Rk-1ℓℓ + 1kSorting a PermutationWe can use an algorithm that sorts a permutation using at most 2 * d(α) reversals (that is, twice as many reversals as the minimum possible)Algorithm assumes that the target is the identity (1,2,3,4….)General IdeaA main loop looks at the current permutation and selects the best possible reversal to applyUpdate the current permutation and