Rosalind — Bioinformatics Textbook Track — Rearrangements

BA6A — Implement GreedySorting to Sort a Permutation by Reversals

Signs matter because a reversed gene reads on the other strand. Greedy sorting fixes each position once and never revisits it: at most 2n reversals, which is not the minimum but does bound the true distance.

BA6B — Compute the Number of Breakpoints in a Permutation

solved Problem statement

One reversal removes at most two breakpoints, so half the count is a lower bound on reversal distance — BA6A gives the upper one. A fully reversed permutation is not the worst case: (-5 -4 -3 -2 -1) still steps by one, so it has only two breakpoints and one reversal sorts it.

BA6C — Compute the 2-Break Distance Between a Pair of Genomes

solved Problem statement

Blocks minus cycles — a closed form, which is unusual for a rearrangement distance and the reason 2-breaks are studied. A 2-break raises the cycle count by at most one, so the bound is both necessary and achievable.

BA6D — Find a Shortest Transformation of One Genome into Another by 2-Breaks

solved Problem statement

The constructive half of BA6C's argument: exhibits a path of exactly that length. Finds a different valid path from the published one, so it asserts the endpoints and the step count rather than the listing.

BA6E — Find All Shared k-mers of a Pair of Strings

solved Problem statement

Reverse complements count because an inversion puts a conserved block on the other strand; ignoring that would make every inverted block look like a deletion. Plotting the pairs gives the dot plot rearrangements are read off.

BA6F — Implement ChromosomeToCycle

solved Problem statement

Every block becomes a head and a tail, so orientation stops being a sign and becomes a direction of travel — the representation 2-breaks are defined on.

BA6G — Implement CycleToChromosome

solved Problem statement

The inverse of BA6F, asserted by round-tripping rather than only by matching the sample. The sign is recovered from the order of each node pair rather than stored.

BA6H — Implement ColoredEdges

solved Problem statement

Only the edges between blocks are kept — the adjacencies a rearrangement can break. Every node carries exactly one, which is what makes the graph a set of disjoint cycles and BA6C computable.

BA6I — Implement GraphToGenome

solved Problem statement

A circular chromosome has no distinguished starting block, so the walk produced (-2 -3 +1) where the sample shows (+1 -2 -3) — the same chromosome. Rotated to the lowest-numbered block for a stable listing, with the rotation-invariance asserted rather than hidden.

BA6J — Implement 2-BreakOnGenomeGraph

solved Problem statement

The single operation every rearrangement reduces to: cut two adjacencies, rejoin the four ends the other way. Reversals, translocations, fusions and fissions are all this one move.

BA6K — Implement 2-BreakOnGenome

solved Problem statement

BA6H, BA6J and BA6I assembled. This particular break is a fission. The result reads each chromosome in the opposite direction from the published answer, so the assertion canonicalises over rotation and reflection — a circular chromosome read backwards flips every sign and is still the same chromosome.