Exercises marked with (*) require further reading/search beyond the suggested texts.
1. Sort the following genome using Bergeron's method:
+1 −3 −4 +7 +5 +6 −2
Answer:
Step 1: The permutation is framed by 0 and n + 1
0 +1 −3 −4 +7 +5 +6 −2 +8
Step 2: Find the oriented pairs (pairs of consecutive integers, that is, with |i|−|j| = ±1, with opposite signs)
(+1 −2) (−4 +5)
Step 3: Apply the reversal for the oriented pairs and check which reversal results in more oriented pairs (the underlined parts show where the reversal will be applied).
Operation 1:
1st Pair: (+1 −2)
(0 +1 −3 −4 +7 +5 +6 −2 +8)
(0 +1 +2 −6 −5 −7 +4 +3 +8)
Oriented pairs generated: (+4 −5) (−7+8)
2nd Pair: (−4 +5)
(0 +1 −3 −4 +7 +5 +6 −2 +8)
(0 +1 −3 −7 +4 +5 +6 −2 +8)
Oriented pairs generated: (+1 −2) (−3 +4) (+6 −7) (−7 +8)
The second pair (−4 +5) has score 4, and the first pair (+1 −2) has score 2.
We choose the pair that has the highest score: Pair: (−4 +5) and apply it, obtaining:
Permutation: (0 +1 −3 −7 +4 +5 +6 −2 +8)
Then we restart Steps 2 and 3 for this new permutation.
Operation 2:
1st Pair: (+1 −2)
(0 +1 −3 −7 +4 +5 +6 −2 +8)
(0 +1 +2 −6 −5 −4 +7 +3 +8)
Oriented pairs generated: (+3 −4) (−6 +7)
2nd Pair: (−3 +4)
(0 +1 −3 −7 +4 +5 +6 −2 +8)
(0 +1 +7 +3 +4 +5 +6 −2 +8)
Oriented pairs generated: (+1 −2) (−2 +3)
3rd Pair: (+6 −7)
(0 +1 −3 −7 +4 +5 +6 −2 +8)
(0 +1 −3 −7 −6 −5 −4 −2 +8)
Oriented pairs generated: (+1 −2) (−7 +8)
4th Pair: (−7 +8)
(0 +1 −3 −7 +4 +5 +6 −2 +8)
(0 +1 −3 +2 −6 −5 −4 +7 +8)
Oriented pairs generated: (+2 −3) (−6 +7)
We have score 2 for all oriented pairs in Operation 2. We choose arbitrarily the first pair to apply. We then start Steps 2 and 3 again with the resulting permutation.
Permutation: (0 +1 +2 −6 −5 −4 +7 +3 +8)
Operation 3:
1st Pair: (+3 −4)
(0 +1 +2 −6 −5 −4 +7 +3 +8)
(0 +1 +2 −6 −5 −4 −3 −7 +8)
Oriented pairs generated: (+2 −3) (−7 +8)
2nd Pair: (−6 +7)
(0 +1 +2 −6 −5 −4 +7 +3 +8)
(0 +1 +2 +4 +5 +6 +7 +3 +8)
No oriented pairs generated
Permutation: (0 +1 +2 −6 −5 −4 −3 −7 +8)
Operation 4:
1st Pair: (+2 −3)
(0 +1 +2 −6 −5 −4 −3 −7 +8)
(0 +1 +2 +3 +4 +5 +6 −7 +8)
Oriented pairs generated: (+6 −7) (−7 +8)
2nd Pair: (−7 +8)
(0 +1 +2 −6 −5 −4 −3 −7 +8)
(0 +1 +2 −6 −5 −4 −3 +7 +8)
Oriented pairs generated: (+2 −3) (−6 +7)
As in Operation 2, all pairs have the same score. We arbitrarily choose the second pair (−7 +8) to apply.
Permutation: (0 +1 +2 −6 −5 −4 −3 +7 +8)
Operation 5:
1st Pair: (+2 −3)
(0 +1 +2 −6 −5 −4 −3 +7 +8)
(0 +1 +2 +3 +4 +5 +6 +7 +8)
2nd Pair: (−6 +7)
(0 +1 +2 −6 −5 −4 −3 +7 +8)
(0 +1 +2 +3 +4 +5 +6 +7 +8)
The sorting produced (0 +1 +2 +3 +4 +5 +6 +7 +8) after five operations.
© 2015 Joao Meidanis