July 2, 2012, midnight by Rosalind Team
Topics: Combinatorics, Genome Rearrangements
Rearrangements Power Large-Scale Genomic Changes
Perhaps the most common type of genome rearrangement is an inversion, which flips an entire interval of DNA found on the same chromosome. As in the case of calculating Hamming distance (see “Counting Point Mutations”), we would like to determine the minimum number of inversions that have occurred on the evolutionary path between two chromosomes. To do so, we will use the model introduced in “Enumerating Gene Orders” in which a chromosome is represented by a permutation of its synteny blocks.
A reversal of a permutation creates a new permutation by inverting some interval
of the permutation;
Given: A collection of at most 5 pairs of permutations, all of which have length 10.
Return: The reversal distance between each permutation pair.
1 2 3 4 5 6 7 8 9 10 3 1 5 2 7 4 9 6 10 8 3 10 8 2 5 4 7 1 6 9 5 2 3 1 7 4 10 8 6 9 8 6 7 9 4 1 3 10 2 5 8 2 7 6 9 1 5 3 10 4 3 9 10 4 1 8 6 7 5 2 2 9 8 5 1 7 3 4 6 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
9 4 5 7 0
Hint
Don't be afraid to try an ugly solution.