MO640 - Exercises - Representation of genomes, Feijao and Meidanis 2011, Pevzner and Shamir 2004 (chapter 9), Setubal and Meidanis 1997 (chapter 7)

Exercises marked with (*) require further reading/search beyond the suggested texts.

3. What is the minimum number of reversals that have to be applied to the first genome below in order to obtain the second genome below?

Answer:

Three reversals can be applied to the first genome to get the second one:

1. Excise from ND3_hND4L_t to ND5_hND6_h and reverse.
2. Reverse gene ND6 by itself.
3. Excise from CYTB_h12S_t to ND1_hND2_t and reverse.

Argument:

We need at least 3 reversals to obtain the second genome from the first. To see this, let G₁ and G₂ be the adjacency sets for the first and second genomes, respectively.

G₁ = { ND3_hND4L_t, ND4L_hND4_t, ND4_hND5_t, ND5_hND6_h, ND6_tCYTB_t, CYTB_h12S_t, 12S_h16S_t, 16S_hND1_t, ND1_hND2_t }

G₂ = { ND3_hND5_h, ND5_tND4_h, ND4_tND4L_h, ND4L_tND6_t, ND6_hCYTB_t, CYTB_hND1_h, ND1_t16S_h, 16S_t12S_h, 12S_tND2_t }

The adjacencies that are in both sets are highlighted. There are 5 adjacencies present in each genome but not in the other. Two genomes with a reversal distance of 1 differ in at most 2 adjacencies, while when the distance is 2, they differ in at most 4 adjacencies, and so on.

Since there are 5 adjacencies unique to each of our genomes, the reversal distance between them cannot be less than 3. So, a series of three reversals is optimal.

MO640 Home

© 2015 Joao Meidanis