Exercises marked with (*) require further reading/search beyond the suggested texts.
3. Sort the following genome using Bergeron's method:
+1 +8 +7 +3 +4 +6 +5 +2 +9
Answer:
According to Bergeron, after breaking the hurdle (7 3 4 6 5 2) we can sort the permutation using Algorithm 1 alone, because the permutation contains at most two hurdles. Let's then revert (+7 +3 +4) and apply Algorithm 1 afterwards. This will yield the following sorting scenario:
0 +1 +8 +7 +3 +4 +6 +5 +2 +9 10 0 +1 +8 −4 −3 −7 +6 +5 +2 +9 10 (Reverting pair (−3, +2), which has score 2) 0 +1 +8 −4 −3 −2 −5 −6 +7 +9 10 (Reverting pair (+1, −2), which has score 2) 0 +1 +2 +3 +4 −8 −5 −6 +7 +9 10 (Reverting pair (+4, −5), score 2) 0 +1 +2 +3 +4 +5 +8 −6 +7 +9 10 (Reverting pair (+5, −6), score 2) 0 +1 +2 +3 +4 +5 +6 −8 +7 +9 10 (Reverting pair (−8, +9), score 2) 0 +1 +2 +3 +4 +5 +6 −7 +8 +9 10 (Reverting pair (−7, +8)) 0 +1 +2 +3 +4 +5 +6 +7 +8 +9 10
Total distance: 7
© 2015 Joao Meidanis