Every problem

DNA — Counting DNA Nucleotides

solved Problem statement

A warm-up for the site's input format rather than a biological question — but the four counts it produces are exactly what GC content is computed from, and a lopsided base composition is the first thing a QC tool flags as contamination or adapter read-through.

RNA — Transcribing DNA into RNA

solved Problem statement

One character substituted for another, which is a fair summary of transcription only if you ignore splicing, capping and polyadenylation. SPLC covers the part this leaves out.

REVC — Complementing a Strand of DNA

solved Problem statement

The most-used operation in the whole track. A read carries no record of which strand it came from, so a motif present on one strand appears as its reverse complement on the other — which is why REVP, BA6E and GASM all have to search both.

HAMM — Counting Point Mutations

solved Problem statement

Counts differing positions, which undercounts mutations: a site can change and change back, leaving no trace. RSUB shows exactly that happening, and it is why distance models correct for unseen substitutions rather than using raw counts.

FIB — Rabbits and Recurrence Relations

solved Problem statement

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

GC — Computing GC Content

solved Problem statement

GC content ranges from about 16 to 75 percent across bacteria, and a difference under 5 percent is taken as evidence of the same species — which is why a fragment's GC content alone narrows down where it came from. It also biases sequencing: GC-rich regions amplify poorly and end up under-covered.

PROT — Translating RNA into Protein

solved Problem statement

Sixty-four codons encode twenty amino acids and a stop, so the code is degenerate and translation discards information. MRNA counts exactly how much.

SUBS — Finding a Motif in DNA

solved Problem statement

Finding every occurrence, overlaps included, because real motifs do overlap. The motifs worth finding are restriction sites (REVP) and binding sites — though a real binding site is a tendency rather than a fixed string, which KSIM and MPRT address.

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.

IPRB — Mendel's First Law

solved Problem statement

Mendel's first law as a probability question. The whole content is that two alleles segregate independently, which is what makes the offspring distribution a product rather than something requiring simulation.

IEV — Calculating Expected Offspring

solved Problem statement

Expectation is linear whether or not the events are independent, so the answer is a weighted sum with no interaction between genotypes to model. That property is why expected values are reached for far more often than full distributions.

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.

PRTM — Calculating Protein Mass

solved Problem statement

Monoisotopic masses, which is what a high-resolution instrument reports when it can resolve individual isotope peaks; low-resolution and high-mass measurements give average masses instead, differing by roughly 0.06 percent. Everything in the mass-spectrometry chapter rests on this sum.

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.

EDIT — Edit Distance

solved Problem statement

The crude version of sequence comparison, and the pack refines it twice: GLOB stops treating every substitution as equally costly, and GAFF stops treating a gap of k bases as k separate events. Useful mainly as the baseline those two improve on.

GLOB — Global Alignment with Scoring Matrix

solved Problem statement

BLOSUM62 is built from substitution frequencies actually observed in aligned protein blocks, so swapping a residue for a chemically similar one costs little and swapping it for an unrelated one costs a lot. That is the information EDIT throws away by charging one for every mismatch.

LOCA — Local Alignment with Scoring Matrix

solved Problem statement

Two proteins may share a single conserved domain inside otherwise unrelated sequence. A global alignment has to align the unrelated parts too and buries the signal; local alignment reports only the stretch that matches, which is what makes it the basis of database search.

GAFF — Global Alignment with Scoring Matrix and Affine Gap Penalty

solved Problem statement

One insertion of ten bases is a single mutational event, not ten. Charging per base makes an aligner scatter several short gaps where one long gap is right, so opening a gap costs more than extending it.

OAP — Overlap Alignment

solved Problem statement

Brute-force DP over lists; ~9 s. A flat-buffer implementation would be the natural follow-up.

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.

LIA — Independent Alleles

solved Problem statement

Mendel's second law. Alleles at different loci assort independently, so the two-locus probability factors — which is what makes this a binomial calculation rather than a simulation.

SEXL — Sex-Linked Inheritance

solved Problem statement

Males carry one X, so a recessive allele on it is expressed with no second copy to mask it. The proportion of affected males is therefore the allele frequency itself, which is why X-linked recessive conditions appear far more often in males than females.

AFRQ — Counting Disease Carriers

solved Problem statement

Hardy-Weinberg run backwards: the disease frequency gives the allele frequency, and the carrier frequency 2pq follows. For a rare recessive allele carriers vastly outnumber sufferers, which is the counterintuitive result the arithmetic exists to make obvious.

PROB — Introduction to Random Strings

solved Problem statement

Computed in logarithms because the raw probability of any particular long string underflows to zero — the same reason the HMM problems decode in log space rather than multiplying probabilities directly.

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.

LCSM — Finding a Shared Motif

solved Problem statement

Any longest common substring is a valid answer, so the assertion checks the length and that the motif really is shared, not one particular string.

TRAN — Transitions and Transversions

solved Problem statement

A random mutation process would give a ratio near 0.5, since there are twice as many ways to make a transversion. Real human data sits near 2.1 genome-wide and near 3 in exomes, largely because methylated cytosine deaminates to thymine. The ratio is therefore a standard quality check: a callset far from those values is reporting sequencing error rather than biology.

SPLC — RNA Splicing

solved Problem statement

What RNA glossed over. A eukaryotic gene is not a contiguous coding sequence — introns are cut out before translation, so the protein comes from the exons joined together. Removing the introns first is the difference between the right protein and nonsense.

CONS — Consensus and Profile

solved Problem statement

A profile is the same object BA2's motif search builds and scores against: counts per base per position. The consensus reads off the commonest base at each, which is a useful summary and a lossy one — it discards how strong the preference was.

GRPH — Overlap Graphs

solved Problem statement

Overlap graphs make reads the nodes, which makes assembly a Hamiltonian path — NP-hard. DBRU makes reads the edges instead and gets an Eulerian path, solvable in linear time. Same data, different graph, and the whole reason modern assemblers use de Bruijn graphs.

REVP — Locating Restriction Sites

solved Problem statement

Restriction enzymes cut at reverse palindromes because they bind as symmetric dimers, one subunit per strand, so the site reads the same on both. That is why these particular sequences matter and why they are always even in length.

TREE — Completing a Tree

solved Problem statement

A tree on n nodes has exactly n-1 edges, so the answer is that count minus the edges already present, with no search involved. The point is recognising the invariant rather than exploring the graph.

INOD — Counting Phylogenetic Ancestors

solved Problem statement

An unrooted binary tree with n leaves always has n-2 internal nodes, whatever its shape. That fixed relationship is what lets EUBT count trees by insertion and CNTQ count quartets without ever examining a topology.

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.

LGIS — Longest Increasing Subsequence

solved Problem statement

Longest increasing subsequence, which in a genomic setting is how conserved order is recovered from a comparison of two genomes: positions that stay in ascending order form a synteny block, and the rest is rearrangement.

SSEQ — Finding a Spliced Motif

solved Problem statement

A subsequence rather than a substring — the characters need not be contiguous. That is the right model for a motif split across exons, since the intervening introns are spliced out before the protein is made.

PDST — Creating a Distance Matrix

solved Problem statement

Pairwise p-distance: the fraction of positions at which two sequences differ. It is the crude measure HAMM warns about, applied to every pair, and it feeds the tree-building problems that follow.

ASMQ — Assessing Assembly Quality with N50 and N75

solved Problem statement

N50 is the contig length at which half the assembly sits in contigs that long or longer. It is the standard summary and a gameable one: joining contigs wrongly raises it, so a high N50 is evidence of a long assembly rather than a correct one.

ORF — Open Reading Frames

solved Problem statement

Six frames, not three — the gene may sit on either strand, and there is no way to tell from the sequence which. Each frame is scanned from every start codon to the first stop.

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.

SETO — Introduction to Set Operations

solved Problem statement

Set operations as groundwork. Worth having explicitly because several later problems phrase their answer as a complement or an intersection, and getting the universe wrong is a common way to be quietly off by a few elements.

LCSQ — Finding a Shared Spliced Motif

solved Problem statement

Any longest common subsequence is a valid answer, so the assertion checks the length and that the motif really is a subsequence of both strings.

KMP — Speeding Up Motif Finding

solved Problem statement

The failure array records, for each prefix, the longest proper prefix that is also a suffix — so a mismatch can resume without re-reading the text. That is what makes matching linear rather than quadratic, and it is the same insight the trie and suffix-array problems generalise.

DBRU — Constructing a De Bruijn Graph

solved Problem statement

Reads become edges rather than nodes, which turns assembly from a Hamiltonian path problem into an Eulerian one. GRPH shows the alternative; this is the construction real assemblers are built on.

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.

CORR — Error Correction in Reads

solved Problem statement

Assumes a correct read appears at least twice and an erroneous one exactly once — which is what read depth buys and why coverage matters. Reverse complements count as the same read, since strand is not recorded.

SCSP — Interleaving Two Motifs

solved Problem statement

Any shortest common supersequence is valid, so the assertion checks the length and that both inputs are subsequences of the result.

EVAL — Expected Number of Restriction Sites

solved Problem statement

The expected number of times a motif appears in a random sequence, which is what makes an observed count interesting or unremarkable. Without a baseline, finding a site says nothing at all.

LONG — Genome Assembly as Shortest Superstring

solved Problem statement

Shortest superstring is NP-hard in general. This is solvable only because the problem guarantees every pair overlaps by more than half their length, which makes the correct overlap unique and a greedy merge safe. GREP shows what happens when that guarantee is dropped.

KMER — k-Mer Composition

solved Problem statement

The official answer is a 256-entry array. Rather than restate it, the assertion checks the ordering endpoints, that the counts total the number of windows, and cross-checks an entry by independent counting — which is what an ordering or lookup mistake would break.

EBIN — Wright-Fisher's Expected Behavior

solved Problem statement

Expected allele counts under Wright-Fisher, where expectation is linear and so the answer is a sum of binomial means. WFMD gives the distribution this summarises.

SPEC — Inferring Protein from Spectrum

solved Problem statement

The answer is derived from the spectrum's consecutive differences (186.079 W, 131.040 M, 128.059 Q, 71.037 A) rather than restated from memory, and the assertion re-checks each residue against its own gap.

ROOT — Counting Rooted Binary Trees

solved Problem statement

Rooted binary trees on n leaves number (2n-3)!!, which passes a billion by n=11. That growth is why phylogenetics searches tree space rather than enumerating it.

CUNR — Counting Unrooted Binary Trees

solved Problem statement

The unrooted count, (2n-5)!!, which is the rooted count one step back — a rooted tree is an unrooted one with a root placed on some edge. EUBT constructs these rather than counting them.

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.

INDC — Independent Segregation of Chromosomes

solved Problem statement

Rosalind allows 0.001 absolute error and its printed sample rounds some entries differently, so the assertion pins the exact endpoints — log10(1023/1024) and log10(1/1024) — and that the tail never increases, rather than a rounding-dependent array.

TRIE — Introduction to Pattern Matching

solved Problem statement

Patterns sharing a prefix share a path, so the text is scanned once regardless of how many patterns are sought. That is the property that makes trie matching worth building, and BA9A and BA9B use it directly.

WFMD — The Wright-Fisher Model of Genetic Drift

solved Problem statement

Genetic drift: allele frequencies move at random in a finite population, and an allele can be lost or fixed with no selection involved at all. It is the null model everything claiming selection has to be tested against.

NWCK — Distances in Trees

solved Problem statement

Carries a small Newick parser written in BioLang — phylo_tree() renders SVG and nw_to_distance_matrix() takes a table, so neither parses Newick.

NKEW — Newick Format with Edge Weights

solved Problem statement

The NWCK parser extended to read ':length' suffixes, walking to the lowest common ancestor rather than breadth-first.

CTBL — Creating a Character Table

solved Problem statement

A character table records the splits a set of taxa admits. CHBP inverts it back into a tree, which works only because the splits of a consistent table are nested or disjoint and never crossing.

SPTD — Phylogeny Comparison with Split Distance

solved Problem statement

The two trees here share no nontrivial split, so the distance is 2(n-3) = 6; the splits of each are printed so that is checkable by eye. The assertion also requires a tree compared with itself to give 0, which tests the canonical split orientation rather than just the arithmetic.

CONV — Comparing Spectra with the Spectral Convolution

solved Problem statement

Both spectra repeat a mass, so the winning difference (149.06586) arises four ways; the example prints that reasoning. The assertion also pins the three hand-checked occurrences of 85.03163 and the size of the convolution.

PCOV — Genome Assembly with Perfect Coverage

solved Problem statement

Perfect coverage makes the De Bruijn graph a single cycle, so it is walked directly rather than searched. The assertion checks every read appears in the doubled string, which is what cyclic containment means.

SIMS — Finding a Motif with Modifications

solved Problem statement

Fitting alignment by dynamic programming over two rolling rows, written in place with indexed assignment. Rebuilding each row with push() took about 40 s; this takes about 18 s.

MEND — Inferring Genotype from a Pedigree

solved Problem statement

The distribution was worked out by hand up the pedigree before being asserted, and the example prints that derivation. The assertion also requires the three probabilities to sum to one.

LING — Linguistic Complexity of a Genome

solved Problem statement

The fraction of substrings that actually occur out of all that could. Repetitive sequence scores low because it reuses the same substrings — which is exactly what makes repeats hard to assemble through, as GREP demonstrates.

RSTR — Matching Random Motifs

solved Problem statement

Derived rather than recalled: the motif has four weak and four strong bases, so p = 0.2^4 x 0.3^4 = 1.296e-05 and 1-(1-p)^90 = 0.00117. The assertion pins p as well as the answer.

EDTA — Edit Distance Alignment

solved Problem statement

Any optimal alignment is valid, so the assertion checks the distance and that the two rows are equal length, recover the inputs once gaps are removed, and differ in exactly `distance` positions.

CTEA — Counting Optimal Alignments

solved Problem statement

Two passes: the edit-distance table, then a count of the paths achieving it. The distance agrees with EDIT on the same pair of strings.

FOUN — The Founder Effect and Genetic Drift

solved Problem statement

The first generation was derived by hand — from one copy, (7/8)^8 = 0.343609 so log10 = -0.463936 — and the assertion pins that plus the requirement that loss never becomes less likely over time.

GCON — Global Alignment with Constant Gap Penalty

solved Problem statement

The affine recurrence with a zero extension cost. Cross-checked against GLOB, which scores the same pair at 8 with a per-residue gap of 5.

PRSM — Matching a Spectrum to a Protein

solved Problem statement

GSDMQS ties with IASMQS at multiplicity 3, so the assertion requires the reported protein to be one of the maximal ones rather than a single fixed string.

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.

CSET — Fixing an Inconsistent Character Set

solved Problem statement

Any character whose removal restores consistency is a valid answer, so the assertion checks the four-gamete condition on the result and that the input really was inconsistent, rather than naming one row.

LREP — Finding the Longest Multiple Repeat

solved Problem statement

Rosalind supplies the suffix tree as an edge list, so nothing has to build one — the work is counting leaves below each node, which is how often the path to it occurs.

MREP — Identifying Maximal Repeats

solved Problem statement

Read off the LCP array: a value of at least 20 is a candidate repeat, kept when its occurrences do not all share the character before them.

LAFF — Local Alignment with Affine Gap Penalty

solved Problem statement

One call. Local mode and affine gaps were both already in align(); what was missing until recently was any way to reach a substitution matrix from it.

SMGB — Semiglobal Alignment

solved Problem statement

Semiglobal is one of the two alignment modes added for this pack; before that the problem could not be expressed at all.

MGAP — Maximizing the Gap Symbols of an Optimal Alignment

solved Problem statement

The scoring is deliberately unspecified, which is the hint: a maximum-score alignment matches as much as it can, so the answer falls out of the longest common subsequence.

CSTR — Creating a Character Table from Genetic Strings

solved Problem statement

A split is nontrivial only when both sides hold at least two strings; a position where one string differs from all the others separates nothing. Which state is written as 1 is arbitrary, so the assertion accepts a row or its complement.

SUFF — Encoding Suffix Trees

solved Problem statement

Built from the suffix array and LCP array rather than by collapsing a trie. Both give the same tree; a trie of all suffixes has O(n^2) nodes first, whereas the arrays are linear — which is why aligners store the arrays and never materialise the tree.

SGRA — Using the Spectrum Graph to Infer Peptides

solved Problem statement

Monoisotopic masses, so differences are matched within a tolerance rather than exactly. The graph is a DAG since masses only increase, so the longest path is one scan in sorted order instead of an exponential search.

FULL — Inferring Peptide from Full Spectrum

solved Problem statement

A peptide fragments from both ends at once, so a b-ion and its y-ion sum to the parent mass and the list mixes them unlabelled. It does not matter which is which — taking an ion spends its complement, since a prefix and its suffix are one event and cannot both extend the chain.

ALPH — Alignment-Based Phylogeny

solved Problem statement

Small parsimony with the gap as a fifth symbol rather than a missing value — in an alignment a gap is evidence that an indel happened, and treating it as unknown would make every column containing one free. Finds a different labelling of equal score, so the assertion recounts the changes.

GASM — Genome Assembly Using Reads

solved Problem statement

A read gives no clue which strand it came from, so the graph holds every read and its reverse complement and falls into two mirror cycles. Returns AATCTGT — a rotation of the reverse complement of GATTACA, which the assertion checks up to both rotation and strand.

MULT — Multiple Alignment

solved Problem statement

Four sequences need a hypercube and 2^k-1 moves out of every cell — fifteen here, against three for a pairwise alignment. Exact multiple alignment costs O(n^k), which is why every tool that aligns hundreds of sequences is approximating.

GREP — Genome Assembly with Perfect Coverage and Repeats

solved Problem statement

PCOV returns one answer; this is the honest version. Repeats make the Eulerian cycle non-unique and all six cycles are genomes consistent with the reads — so the reads do not determine the chromosome, and reporting one would be picking arbitrarily.

MPRT — Finding a Protein Motif

solved Problem statement

Calls NCBI, so it needs a network connection and its answer can change over time.

Fetches from UniProt, so it runs in the advisory job rather than the hermetic gate. The motif matcher itself is asserted offline — N{P}[ST]{P} has alternatives and exclusions, so it is a pattern rather than a substring search.

OSYM — Isolating Symbols in Alignments

solved Problem statement

The best alignment through a given pairing is the best way of reaching it plus the best way of leaving it, so one forward table and one backward table answer all 49 pairs at once — the same trick BA5K uses to find a middle edge.

ITWV — Finding Disjoint Motifs in a Gene

solved Problem statement

Two motifs competing for the same characters, which is what makes this different from finding each separately. Every reachable state must consume the current character or the window ends — carrying one forward unconsumed would let the motifs match unrelated parts of the sequence.

CNTQ — Counting Quartets

solved Problem statement

The answer is C(n,4), and the reason matters more than the number: in a fully resolved tree any four taxa are separated into two pairs by some edge, so the shape never enters into it. The assertion enumerates all 15 subsets and confirms it rather than trusting the formula.

QRT — Quartets

solved Problem statement

An 'x' means not scored, not a third state — so a partial character still separates the taxa it did see, and missing data does not make it useless. Quartets are recorded canonically because neither side nor the order within a side carries meaning, and two characters often support the same one.

CHBP — Character-Based Phylogeny

solved Problem statement

The inverse of CTBL. It works because a consistent table's splits are laminar — any two nested or disjoint, never crossing — and a laminar family is exactly a tree. Returns a differently-rooted Newick, so the assertion compares induced splits rather than a formatting choice.

EUBT — Enumerating Unrooted Binary Trees

solved Problem statement

Built by insertion: every unrooted binary tree arises exactly once by splitting an edge and hanging the next taxon off it, which is why the count is (2n-5)!! — fifteen trees at n=5, over two million at n=10. That growth is why nobody enumerates trees to find the best one.

QRTD — Quartet Distance

solved Problem statement

Quartets degrade gracefully where splits do not: moving one taxon changes a handful of quartets but can destroy every split at once. Asserted to be zero between a tree and itself, which is the identity any distance must satisfy.

RNAS — Wobble Bonding and RNA Secondary Structures

solved Problem statement

Real RNA pairs U-G nearly as readily as A-U, so a count excluding wobble understates what a molecule can fold into. Memoised with has_key — contains(keys(memo), k) rebuilds the key list on every probe and would make the lookup the bottleneck the memo was meant to remove.

KSIM — Finding All Similar Motifs

solved Problem statement

A binding site is a tendency rather than a fixed string, so exact search finds a fraction of real sites — the motif here does not occur exactly at all. Checks every (start, length) pair directly, which is O(n^2) and stated as such: a 50 kbp genome would need the fitting-alignment form instead.

RSUB — Identifying Reversing Substitutions

solved Problem statement

A site that mutates and mutates back looks, from the tips alone, as though nothing happened — which is exactly what makes distant relationships hard to recover. Only the internal labels reveal it, which is why the problem supplies them.

REAR — Reversal Distance

solved Problem statement

Where BA6C's 2-break distance had a closed form, this has none at size 10 and must be searched: 45 reversals per step, 3.6 million reachable orders, distance reaching 9. The builtin searches from both ends and meets in the middle, so each side only reaches depth 4 or 5.

SORT — Sorting by Reversals

solved Problem statement

REAR asks how far apart two gene orders are; this asks for the route, which is what actually says how the rearrangement happened. The assertion applies the reversals and checks they produce the target — a plausible list that does not sort is the failure this invites.