Reconstructing Evolutionary Histories
When we calculate the Hamming distance between two genetic strings, we can easily infer a collection of point mutations that occurred on the evolutionary path between the two strings by simply examining the mismatched symbols. However, when calculating the reversal distance (see “Reversal Distance”), we only have the minimum number of reversals separating two permutations.
The computational problem of sorting by reversals demands instead that we provide a minimum list of reversals transforming one permutation into another. As a result, sorting by reversals subsumes the calculation of reversal distance: once we have a minimum collection of reversals, the reversal distance follows immediately.
A reversal of a permutation can be encoded by the two indices at the endpoints of the interval that
it inverts; for example, the reversal that transforms
A collection of reversals sorts
Given: Two permutations
Return: The reversal distance
1 2 3 4 5 6 7 8 9 10 1 8 9 3 2 7 6 5 4 10
2 4 9 2 5