Rosalind — Bioinformatics Stronghold — Combinatorics

FIB — Rabbits and Recurrence Relations

A recurrence-relation exercise wearing rabbits, not population biology — nothing here dies, competes or mutates. WFMD and EBIN are where real population dynamics appear.

FIBD — Mortal Fibonacci Rabbits

solved Problem statement

FIB with a death clock added. Still a recurrence exercise rather than population biology, and useful mainly for showing that the state has to widen from one number to an age profile.

MRNA — Inferring mRNA from Protein

solved Problem statement

The reverse of PROT, and it cannot be done — the code is degenerate, so a protein maps back to many mRNAs. Leucine, serine and arginine take six codons each. Counting them needs a modulus because the total outgrows any integer.

PERM — Enumerating Gene Orders

solved Problem statement

Permutations as gene orders. n! grows fast enough that enumeration stops being possible almost immediately, which is the premise SIGN, REAR and SORT build on — there, gene order is the data and the question is how few reversals separate two of them.

PPER — Partial Permutations

solved Problem statement

Ordered selections rather than full orderings, taken modulo a million because the count outgrows the answer format long before it outgrows the biology. Combinatorial groundwork for the counting problems, not a biological question in itself.

SSET — Counting Subsets

solved Problem statement

Two to the n, which is the point. Any method that examines every subset of a set of sites stops being usable in the low twenties, and that is the wall the search problems elsewhere in this pack are built to avoid.

PMCH — Perfect Matchings and RNA Secondary Structures

solved Problem statement

RNA folds back on itself and pairs. This counts the ways every base could be paired, which requires the A and U counts to match and the C and G counts to match — a condition real sequences rarely satisfy, which is what MMCH addresses.

MMCH — Maximum Matchings and RNA Secondary Structures

solved Problem statement

PMCH without the assumption that everything pairs. Real RNA leaves bases unpaired because the counts do not match, so the question becomes how many bonds are possible rather than how many arrangements are complete.

CAT — Catalan Numbers and RNA Secondary Structures

solved Problem statement

Catalan numbers count matchings that do not cross, and non-crossing is a physical constraint rather than a mathematical convenience: crossing bonds are pseudoknots, which this model excludes. MOTZ relaxes the requirement that everything pairs, and RNAS adds wobble bonds and a minimum hairpin turn.

LEXF — Enumerating k-mers Lexicographically

solved Problem statement

Enumerating every k-mer over an alphabet, which is 4 to the k for DNA. Fine at k=3 and hopeless by k=20, which is why the k-mer problems index sequences rather than enumerate possibilities.

SIGN — Enumerating Oriented Gene Orderings

solved Problem statement

Signed permutations: 2^n times n! of them, because each gene may also be flipped. The sign is not decoration — a reversed gene reads on the opposite strand, which is exactly what REAR and SORT measure.

LEXV — Ordering Strings of Varying Length Lexicographically

solved Problem statement

Ordering strings of unequal length, where a prefix sorts before anything extending it. Ordinary lexicographic order on padded strings gets this wrong, which is the whole exercise.

ASPC — Introduction to Alternative Splicing

solved Problem statement

Summing binomial coefficients, motivated by alternative splicing: one gene yields many proteins depending on which exons are kept. The count grows fast enough that the modulus is doing real work.

MOTZ — Motzkin Numbers and RNA Secondary Structures

solved Problem statement

Motzkin numbers drop CAT's requirement that every base pairs, which is the more realistic model: real RNA leaves plenty unpaired. RNAS goes further and adds wobble bonds and a minimum hairpin length.

PDPL — Creating a Restriction Map

solved Problem statement

Self-verifying: the assertion recomputes the pairwise differences of the reconstructed points and requires them to reproduce the input multiset exactly, which is stronger than matching one printed answer.