MO640 - Exercises - Unichromosomal block interchange distance, Christie 1996

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).

MO640 Home

© 2015 Joao Meidanis