Exercises marked with (*) require further reading/search beyond the suggested texts.
2. Sort optimally the following genome using block interchanges:
+6 +1 +2 +7 +4 +8 +9 +5 +3
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).
+6 +1 +2 +7 +4 +8 +9 +5 +3 (x = 1, y = 6) +1 +2 +7 +6 +4 +8 +9 +5 +3 (x = 3, y = 9) +1 +2 +3 +5 +7 +6 +4 +8 +9 (x = 4, 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 4 block interchange operations).
© 2015 Joao Meidanis