Rearrangements

2 problems from Rosalind — Bioinformatics Stronghold. Press Run on any block to execute it in your browser.

# Rosalind: REAR — Reversal Distance
# https://rosalind.info/problems/rear/
#
# Given: Up to five pairs of permutations of length 10.
# Return: The reversal distance for each pair.

let pairs = [
    { from_order: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10],  to_order: [3, 1, 5, 2, 7, 4, 9, 6, 10, 8] },
    { from_order: [3, 10, 8, 2, 5, 4, 7, 1, 6, 9],  to_order: [5, 2, 3, 1, 7, 4, 10, 8, 6, 9] },
    { from_order: [8, 6, 7, 9, 4, 1, 3, 10, 2, 5],  to_order: [8, 2, 7, 6, 9, 1, 5, 3, 10, 4] },
    { from_order: [3, 9, 10, 4, 1, 8, 6, 7, 5, 2],  to_order: [2, 9, 8, 5, 1, 7, 3, 4, 6, 10] },
    { from_order: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10],  to_order: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] },
]

# The 2-break distance in BA6C had a closed form — blocks minus cycles. Reversal
# distance has no such formula at this size, so it has to be searched for, and
# the search is why `reversal_distance` is a builtin rather than written here:
# ten elements admit 45 reversals and 3.6 million reachable orders, and the
# distance reaches 9. A one-sided search to that depth is hopeless; the builtin
# searches from both ends and meets in the middle, so each side only reaches
# depth 4 or 5.
let distances = pairs |> map(|pair| reversal_distance(pair.from_order, pair.to_order))

println("Result:   " + (distances |> map(|d| str(d)) |> join(" ")))
println("Expected: 9 4 5 7 0")

fn test_rear_reversal_distance() {
    assert (distances |> map(|d| str(d)) |> join(" ")) == "9 4 5 7 0",
        "REAR: got " + str(distances)
    # Identical permutations are no distance apart, and the measure is symmetric
    # because a reversal undoes itself.
    assert distances[4] == 0, "REAR: the last pair is already sorted"
    for pair in pairs {
        assert reversal_distance(pair.to_order, pair.from_order)
            == reversal_distance(pair.from_order, pair.to_order),
            "REAR: the distance must be symmetric"
    }
}

# Rosalind: SORT — Sorting by Reversals
# https://rosalind.info/problems/sort/
#
# Given: Two permutations of length 10.
# Return: The reversal distance, and a shortest collection of reversals taking
# the first to the second.

let from_order = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
let to_order = [1, 8, 9, 3, 2, 7, 6, 5, 4, 10]

# REAR asks how far apart two gene orders are; this asks for the route. The
# search is the same — the distance is just the length of what comes back — but
# the sequence is what actually says how the rearrangement happened, and a
# distance without one is unfalsifiable.
#
# Any shortest sequence is correct. Reversals commute in some orders and not
# others, so several routes of the same length usually exist.
let steps = sorting_reversals(from_order, to_order)

println("Result:   " + str(len(steps)))
for step in steps { println("          " + str(step[0]) + " " + str(step[1])) }
println("Expected: 2, then 4 9 and 2 5 — any shortest route is accepted")

fn test_sort_sorting_by_reversals() {
    assert len(steps) == 2, "SORT: expected 2 reversals, got " + str(len(steps))
    assert len(steps) == reversal_distance(from_order, to_order),
        "SORT: the route must be as long as the distance"

    # The route has to work. Applying the reversals in order must produce the
    # target — a plausible-looking list that does not sort is the failure this
    # problem invites.
    let current = from_order
    for step in steps {
        let from_index = step[0] - 1
        let to_index = step[1] - 1
        let head = range(0, from_index) |> map(|i| current[i])
        let middle = range(from_index, to_index + 1)
            |> map(|i| current[to_index - (i - from_index)])
        let tail = range(to_index + 1, len(current)) |> map(|i| current[i])
        current = head + middle + tail
    }
    assert current == to_order,
        "SORT: the reversals give " + str(current) + ", not " + str(to_order)

    # Every interval is a real one, and reverses more than a single element.
    for step in steps {
        assert step[0] >= 1 and step[1] <= len(from_order), "SORT: interval out of range"
        assert step[0] < step[1], "SORT: reversing one element does nothing"
    }
}