Exercises marked with (*) require further reading/search beyond the suggested texts.
3. Sort optimally the following genome using block interchanges:
+1 +8 +7 +3 +4 +6 +5 +2 +9
Answer:
First, we find x as the smallest value "out of place" and y, the largest value between x-1 and x. The first block ranges from x - 1 to y and the second from x to y + 1 (blocks are underlined).
+1 +8 +7 +3 +4 +6 +5 +2 +9 (x = 2, y = 8) +1 +2 +7 +3 +4 +6 +5 +8 +9 (x = 5, y = 7) +1 +2 +3 +4 +6 +5 +7 +8 +9 (x = 5, y = 6) +1 +2 +3 +4 +5 +6 +7 +8 +9 (sorted after 3 block interchange operations).
© 2015 Joao Meidanis