Every problem

BA1A — Compute the Number of Times a Pattern Appears in a Text

solved Problem statement

BA1B — Find the Most Frequent Words in a String

solved Problem statement

Shows a real distinction: kmer_count() tallies canonical k-mers, pooling each with its reverse complement, so it reports GCAT and ATGC as one count of 4. This problem wants literal occurrences, so it counts the raw windows from kmers().

BA1C — Find the Reverse Complement of a String

solved Problem statement

BA1D — Find All Occurrences of a Pattern in a String

solved Problem statement

BA1G — Compute the Hamming Distance Between Two Strings

solved Problem statement

BA3A — Generate the k-mer Composition of a String

solved Problem statement

BA4A — Translate an RNA String into an Amino Acid String

solved Problem statement

BA5G — Compute the Edit Distance Between Two Strings

solved Problem statement

BA9G — Construct the Suffix Array of a String

solved Problem statement

Suffix arrays were one of three gaps this pack was built to measure. They are a builtin now, which is what LREP and MREP in the Stronghold pack stand on.

BA1E — Find Patterns Forming Clumps in a String

solved Problem statement

A sliding window with a tally inside it. A k-mer qualifies once, so the answers are a set.

BA1F — Find a Position in a Genome Minimizing the Skew

solved Problem statement

A running count of G minus C. The dip marks the replication origin, which is what the problem is about.

BA1H — Find All Approximate Occurrences of a Pattern

solved Problem statement

hamming_distance is a builtin, so this is a windowed scan and nothing more.

BA1I — Most Frequent Words with Mismatches

solved Problem statement

The answer need not occur in the text at all. Tallying each window's neighbourhood is the same arithmetic over far fewer strings than testing all 4^k candidates.

BA1J — Frequent Words with Mismatches and Reverse Complements

solved Problem statement

A site can sit on either strand, so a k-mer is credited for its reverse complement too — which is why the winners differ from BA1I on the same input.

BA1K — Generate the Frequency Array of a String

solved Problem statement

Indexed by PatternToNumber, so it lists every possible k-mer including those that never occur. That is what separates it from a tally.

BA1L — Implement PatternToNumber

solved Problem statement

k-mers in lexicographic order are the base-4 numbers with A=0, C=1, G=2, T=3.

BA1M — Implement NumberToPattern

solved Problem statement

The inverse of BA1L.

BA1N — Generate the d-Neighborhood of a String

solved Problem statement

Grown one position at a time, dropping any prefix that has already spent more than d substitutions.

BA2A — Implement MotifEnumeration

solved Problem statement

A motif need not occur exactly anywhere, so the candidates are the neighbourhoods of the first string's windows: anything qualifying must be within d of one of them.

BA2B — Find a Median String

solved Problem statement

Every k-mer is a candidate, not only those occurring in the strings. Any minimiser is accepted, so the assertion checks the distance rather than the string: this finds ACG where the sample shows GAC, and both score 2.

BA2C — Find a Profile-most Probable k-mer

solved Problem statement

The product down the profile's columns. Every entry here is non-zero so no window is ruled out, which is the situation pseudocounts exist to fix in the problems that follow.

BA2H — Implement DistanceBetweenPatternAndStrings

solved Problem statement

Best per string, summed across them: a motif only has to occur once in each.

BA3B — Reconstruct a String from its Genome Path

solved Problem statement

The path is already ordered, so the string is the first k-mer plus one symbol from each after it. Finding the order is what BA3C and BA3H are for.

BA3C — Construct the Overlap Graph of a Collection of k-mers

solved Problem statement

An edge where one k-mer's suffix is another's prefix. Written with `source` and `target` because `from` and `to` are reserved words.

BA3D — Construct the De Bruijn Graph of a String

solved Problem statement

Nodes are (k-1)-mers and edges are the k-mers, which is the inversion that turns assembly into an Eulerian path problem rather than a Hamiltonian one.

BA3E — Construct the De Bruijn Graph of a Collection of k-mers

solved Problem statement

The same construction from a bag of reads rather than a string. A duplicate k-mer stays duplicated: it is evidence of a repeat, not noise.

BA5A — Find the Minimum Number of Coins Needed to Make Change

solved Problem statement

The greedy answer is wrong here and that is the point: taking 25 first needs three coins where 20+20 needs two.

BA5C — Find a Longest Common Subsequence of Two Strings

solved Problem statement

lcs is a builtin. More than one subsequence is longest, so the assertion checks the length and that it really is a subsequence of both.

BA5E — Find a Highest-Scoring Alignment of Two Strings

solved Problem statement

One call: global, BLOSUM62, linear gap of 5.

BA5F — Find a Highest-Scoring Local Alignment of Two Strings

solved Problem statement

PAM250, not BLOSUM62 — the two disagree enough to change the answer, and the problem says which it wants.

BA5H — Find a Highest-Scoring Fitting Alignment of Two Strings

solved Problem statement

All of w against any window of v. Semiglobal returns the same number on this input for a different reason — it would clip w's ends too — so a fitting mode was added rather than asserting the coincidence.

BA5I — Find a Highest-Scoring Overlap Alignment of Two Strings

solved Problem statement

The shape read assembly asks for: where the end of one read agrees with the start of the next.

BA5J — Align Two Strings Using Affine Gap Penalties

solved Problem statement

Charging for opening a gap and less per symbol after is what stops one long insertion being priced as a run of unrelated ones.

BA8A — Implement FarthestFirstTraversal

solved Problem statement

Each new center is the point furthest from all chosen so far. Deterministic, unlike k-means, which is why it is used to seed clustering rather than to do it.

BA8B — Compute the Squared Error Distortion

solved Problem statement

Squared, so one badly placed point counts for far more than several slightly-off ones. This is the quantity k-means minimises.

BA8C — Implement the Lloyd Algorithm for k-Means Clustering

solved Problem statement

Assign, then move each center to the mean of what it was assigned, until nothing moves. Seeded with the first k points because Lloyd's converges differently from different seeds — which is what BA8A exists to address.

BA9D — Find the Longest Repeat in a String

solved Problem statement

The largest entry in the LCP array, and nothing else. Two suffixes sharing a long prefix is what a repeat is, so the array has already found every one of them before the problem is read.

BA9E — Find the Longest Substring Shared by Two Strings

solved Problem statement

Concatenate with a separator, then take the largest LCP between neighbouring suffixes that came from different sides. The separator is load-bearing: without it a match can run across the join and name a substring neither string contains.

BA9I — Construct the Burrows-Wheeler Transform of a String

solved Problem statement

Sorting rotations and sorting suffixes agree once the string ends in a sentinel, so the suffix array gives the transform directly — the character before each sorted suffix.

BA9J — Reconstruct a String from its Burrows-Wheeler Transform

solved Problem statement

The k-th occurrence of a symbol in the first column is the k-th in the last. That correspondence alone rebuilds the text, which is why the transform can be stored without anything beside it.

BA10A — Compute the Probability of a Hidden Path

solved Problem statement

One product of fifty transitions, which lands at 1e-19 — the concrete reason the decoding problems that follow are done in log space rather than directly.

BA10B — Compute the Probability of an Outcome Given a Hidden Path

solved Problem statement

Conditioning on the path makes the positions independent, so the transitions never enter into it. Checked against the same product taken by hand.

BA10C — Implement the Viterbi Algorithm

solved Problem statement

The problem this pack was built to reach: HMM decoding is what gene finders, profile search and segmentation all run on, and nothing in the tree could do it before.

BA10D — Compute the Probability of a String Emitted by an HMM

solved Problem statement

The forward algorithm. Its assertion enumerates all 1024 paths of the sample and sums them, so the collapse is checked against the thing it replaces rather than only against a published number.

BA10J — Solve the Soft Decoding Problem

solved Problem statement

Forward-backward, which answers a different question from Viterbi: the most likely state at each position need not lie on any single path the model can produce.

BA10H — Estimate the Parameters of an HMM

solved Problem statement

With the path given there is nothing to infer — the best estimate is the fraction of the time each move was made. A state the path never visits keeps a uniform row, which is the only choice that leaves it a distribution.

BA10I — Implement Viterbi Learning

solved Problem statement

Decode, re-estimate as if that path were the truth, repeat. Climbs to a local optimum, so where it starts is part of the problem rather than an implementation detail.

BA10K — Implement Baum-Welch Learning

solved Problem statement

Expectation-maximisation: counts the expected number of times each transition was taken over every path at once, instead of committing to the best one. Its assertion checks the likelihood rises round by round, not only end to end.

BA10E — Construct a Profile HMM

solved Problem statement

A family of sequences becomes something a new sequence can be scored against — what Pfam and HMMER search with. Conserved columns become match states; gappy ones become insertions, which keeps the model's length at the family's length rather than the alignment's.

BA10F — Construct a Profile HMM with Pseudocounts

solved Problem statement

Without a pseudocount, anything six sequences never happened to do is scored as impossible. It is added after the counts become probabilities, not before — added to raw counts its influence would depend on how many sequences the alignment contains.

BA10G — Perform a Multiple Sequence Alignment with a Profile HMM

solved Problem statement

Viterbi cannot do this: deletion states are silent, so nine states emit seven symbols. The silent states have to be settled in layer order at each position before the emitting ones look back at them.

BA2D — Implement GreedyMotifSearch

solved Problem statement

Greedy in the strict sense: each string picks what the current profile likes best and nothing is reconsidered. Fast, and wrong often enough that BA2E exists.

BA2E — Implement GreedyMotifSearch with Pseudocounts

solved Problem statement

One number different from BA2D. Without a pseudocount a base absent from a column makes every k-mer containing it impossible rather than unlikely. On this five-string sample the two versions actually tie at a score of 2 — the assertion says so rather than claiming an improvement the data does not show.

BA2F — Implement RandomizedMotifSearch

solved Problem statement

Seeded so the example is reproducible. Graded on the score reached rather than on one particular set, because several distinct sets tie at the optimum of 9 — asserting on the published one would be asserting on the seed.

BA2G — Implement GibbsSampler

solved Problem statement

Replaces one motif at a time rather than all of them, and draws in proportion to probability instead of taking the best — which is what lets it leave a local optimum. Rosalind's suggested 20 starts settles at 10 here; 200 reaches the optimal 9.

BA3F — Find an Eulerian Cycle in a Graph

solved Problem statement

Hierholzer's algorithm, linear in the edges. Asserted on the property — every edge used exactly once, every step a real edge — rather than on the published string, which is one rotation among many.

BA3G — Find an Eulerian Path in a Graph

solved Problem statement

Add the edge between the two unbalanced nodes, find a cycle, then cut the added edge out again. Which node the walk starts and ends at is forced by the degrees, so those are asserted exactly.

BA3H — Reconstruct a String from its k-mer Composition

solved Problem statement

Reads become edges, not nodes — which makes assembly an Eulerian path, solvable in linear time. Reads as nodes would give a Hamiltonian path instead: the same data, a different graph, and the difference between tractable and NP-hard.

BA3I — Find a k-Universal Circular String

solved Problem statement

Every (k-1)-mer has two edges in and two out, so the graph is balanced and the walk closes. Returns a different valid string from the published one; the assertion reads around the circle and checks all 2^k k-mers appear exactly once.

BA3J — Reconstruct a String from its Paired Composition

solved Problem statement

Paired reads pin down a repeat that either read alone would be ambiguous inside. The two halves must agree wherever they overlap, and checking that agreement is what makes a wrong assembly detectable.

BA4B — Find Substrings of a Genome Encoding a Given Amino Acid String

solved Problem statement

A peptide can be encoded on either strand, so both are searched. ATGGCC appears twice and both occurrences count — the answer is substrings by position, not a set of distinct strings.

BA4C — Generate the Theoretical Spectrum of a Cyclic Peptide

solved Problem statement

A cyclic peptide's fragments include those wrapping past the end, and each wrapping piece is the complement of a non-wrapping one. 242 appears twice because LE and QN both weigh it.

BA4D — Compute the Number of Peptides of Given Total Mass

solved Problem statement

Counted by building up from below rather than enumerated — listing 14.7 billion peptides to count them is not an option. Eighteen residue masses, not twenty, since I/L and K/Q collide.

BA4E — Find a Cyclic Peptide with Theoretical Spectrum Matching an Ideal Spectrum

solved Problem statement

Branch and bound: a candidate whose linear spectrum contains a mass the target lacks can never recover, since growing it only adds masses. That pruning is the whole algorithm — without it the search is 18^n.

BA4F — Compute the Score of a Cyclic Peptide Against a Spectrum

solved Problem statement

Real spectra are missing masses and contain spurious ones, so exact matching is unavailable. Multiplicity counts: set intersection would score a peptide explaining a repeated mass once as well as one explaining it fully.

BA4G — Implement LeaderboardCyclopeptideSequencing

solved Problem statement

With a noisy spectrum nothing can be pruned for inconsistency — the right peptide will contain masses the spectrum lacks. Candidates survive on rank instead. Returns a reflection of the published answer; the assertion compares cyclic spectra, since a cycle has no distinguished start.

BA4H — Generate the Convolution of a Spectrum

solved Problem statement

Differences between fragment masses are themselves residue masses, so the commonest ones are what the peptide is built from — recoverable without assuming the standard twenty.

BA4I — Implement ConvolutionCyclopeptideSequencing

solved Problem statement

The published answer contains a residue of mass 72, which is not an amino acid. That is the point: the alphabet is read off the data rather than assumed, so modified residues are findable. Returns a different peptide of equal score, which is all a noisy spectrum can distinguish.

BA4J — Generate the Theoretical Spectrum of a Linear Peptide

solved Problem statement

A strict subset of the cyclic spectrum. Both are needed because sequencing grows a peptide one residue at a time, and scoring a partial peptide cyclically would credit it with wrap-around fragments it does not have.

BA4K — Compute the Score of a Linear Peptide Against a Spectrum

solved Problem statement

8 against BA4F's 11 on identical input, because the linear spectrum has fewer masses to agree with.

BA4L — Trim a Peptide Leaderboard

solved Problem statement

Ties at the cutoff are kept, since cutting one arbitrarily can discard the right answer while keeping an equal rival. LAST and ALST are anagrams and still score differently — linear fragments are contiguous, so order matters.

BA4M — Solve the Turnpike Problem

solved Problem statement

Reading positions from pairwise distances, the same shape of problem as reading a peptide from fragment masses. Backtracking on the largest unplaced distance, which must reach one of the two ends — so each step has two choices rather than a search over all subsets.

BA5B — Find the Length of a Longest Path in a Manhattan-like Grid

solved Problem statement

The grid is filled once in order and never revisited. Enumerating the paths would mean C(n+m, n) of them — 70 here, exponential in general. Longest path is NP-hard in general graphs; it is easy here only because the grid is acyclic.

BA5D — Find the Longest Path in a DAG

solved Problem statement

Easy for one reason: the graph is acyclic, so its nodes can be ordered with every edge pointing forwards and each score is final when read. Unreachable nodes stay at negative infinity rather than 0, or a detour through one could outscore a real path.

BA5K — Find a Middle Edge in an Alignment Graph in Linear Space

solved Problem statement

A full alignment table costs O(nm) memory; one column costs O(n). Two linear-space sweeps meeting in the middle locate where the best alignment crosses it. Asserted against the full aligner: the middle node's total equals the alignment's own score.

BA5L — Align Two Strings Using Linear Space

solved Problem statement

Hirschberg's algorithm on BA5K's middle edge. Each half is re-swept, but the halves shrink geometrically so the total stays O(nm) while memory drops from a table to a column — the trade that makes whole-genome alignment possible. Reproduces the published alignment exactly.

BA5M — Find a Highest-Scoring Multiple Sequence Alignment

solved Problem statement

Three sequences need a cube, and each cell has seven predecessors rather than three. The cost is O(n^k), which is why exact multiple alignment stops being possible at a handful of sequences and real tools use heuristics. Returns a different optimal alignment from the published one; the assertion recounts the agreeing columns.

BA5N — Find a Topological Ordering of a DAG

solved Problem statement

Kahn's algorithm with a FIFO queue. This is what BA5B and BA5D stand on: a longest path can be found in one sweep only if each node is reached after everything leading into it. Several orderings are valid, so the assertion checks every edge points forwards.

BA8D — Implement the Soft k-Means Clustering Algorithm

solved Problem statement

Where BA8C forces every point to pick one cluster, here a point midway between two centers pulls on both. Beta sets how decisive that sharing is: large beta reproduces Lloyd, small beta drags every center towards the overall mean.

BA8E — Implement Hierarchical Clustering

solved Problem statement

Needs no k. Produces a nested family of partitions rather than one — which is what a phylogenetic tree is. Average linkage is specified and it matters: single linkage chains elongated clusters, complete linkage insists on compactness.

BA7A — Compute Distances Between Leaves

solved Problem statement

In a tree there is exactly one path between any two nodes, so there is nothing to optimise — no Dijkstra, no relaxation. That uniqueness is also what lets BA7C invert the distances to recover the tree.

BA7B — Compute Limb Length

solved Problem statement

The minimum over pairs picks the two leaves whose paths diverge immediately, leaving the limb alone. This is what makes BA7C possible: knowing the limb, it can be subtracted off and the leaf removed.

BA7C — Implement AdditivePhylogeny

solved Problem statement

The exact inverse of BA7A. Exact only because the matrix is additive. Asserted by rebuilding every pairwise distance from the tree rather than by matching one printed layout, since internal node numbering is not unique.

BA7D — Implement UPGMA

solved Problem statement

Hierarchical clustering with heights, so every leaf ends the same distance from the root — a molecular clock made concrete. The assertion checks that ultrametric property directly. Often wrong in practice, which is what BA7E exists to avoid.

BA7E — Implement the Neighbor Joining Algorithm

solved Problem statement

Corrects each distance by how far each leaf sits from everything else, so a fast-evolving lineage is no longer mistaken for a distant one. This sample matrix is not additive — its three four-point pairings are 53, 55 and 50 — so no tree fits it exactly and the assertion checks that rather than expecting the distances back unchanged.

BA7F — Implement SmallParsimony

solved Problem statement

Sankoff's algorithm. Every column is independent, so each is solved separately and the scores added. Greedy choice from the leaves fails: a locally cheap base can force two changes higher up. Returns a different labelling of equal score, and the assertion recounts the changes it actually shows.

BA7G — Adapt SmallParsimony to Unrooted Trees

solved Problem statement

An edge costs the same read in either direction, so the score does not depend on where a root is placed — hang one in the middle of any edge, run BA7F unchanged, then remove it. The labelling can differ; the score cannot, which the assertion checks by comparing the rooted and unrooted totals.

BA9A — Construct a Trie from a Collection of Patterns

solved Problem statement

Patterns sharing a prefix share a path, so the trie is walked once per text position no matter how many patterns there are. Node numbering is explicitly free, so the assertions are structural: every pattern spellable, no node with two edges on one symbol.

BA9B — Implement TrieMatching

solved Problem statement

Every pattern is tested at once by a single walk, so the cost is the text length times the longest pattern rather than times the pattern count. Cross-checked against a plain scan.

BA9H — Pattern Matching with the Suffix Array

solved Problem statement

The same answer as BA9B reached the other way, and the example says which to reach for: a trie is built from the patterns and suits many patterns against one text; a suffix array is built from the text and suits one text queried repeatedly.

BA9K — Generate the Last-to-First Mapping of a String

solved Problem statement

The kth occurrence of a symbol in one column is the kth in the other, so a row is found by counting rather than searching. Asserted to be a bijection over every row, which is what makes the walk in BA9J terminate.

BA9L — Implement BWMatching

solved Problem statement

Searching the transform without ever rebuilding the text: sorted rows mean every match forms one contiguous band, narrowed one symbol at a time. Cross-checked by inverting the transform — the point being that the search never needed to.

BA9M — Implement BetterBWMatching

solved Problem statement

Two precomputed tables remove BWMatching's scan, so a query costs time proportional to the pattern rather than to the text. That difference is what makes indexing a genome once and querying it billions of times practical.

BA9Q — Construct the Partial Suffix Array of a String

solved Problem statement

A full suffix array of a human genome is 12 GB before the sequence itself. Keeping every Kth value cuts that by a factor of K, with the rest recoverable by walking the BWT — the compromise real read aligners ship with.

BA9C — Construct the Suffix Tree of a String

solved Problem statement

A trie of every suffix with non-branching chains collapsed. That collapse is what makes it linear rather than quadratic — a trie of all suffixes has O(n^2) nodes and almost all have one child. Built directly here; Ukkonen's algorithm is linear but obscures the structure at this size.

BA9F — Find the Shortest Non-Shared Substring of Two Strings

solved Problem statement

Shortest first, which makes the answer minimal by construction: if a substring of length k is absent, everything containing it is absent too. Returns CC where the sample shows AA; the assertion proves no one-character answer exists.

BA9N — Find All Occurrences of a Collection of Patterns in a String

solved Problem statement

BA9L and BA9M count occurrences without locating them, because a BWT band gives rows of the sorted matrix rather than text positions. Turning a row back into a position is what the suffix array supplies — the partial one of BA9Q in a real aligner, since the full one would undo the memory saving.

BA9O — Find All Approximate Occurrences of a Collection of Patterns in a String

solved Problem statement

Reads carry errors and genomes carry variants, so exact matching finds nothing useful and every aligner is an approximate matcher. Position 4 appears twice because two patterns match there — the answer lists occurrences, not distinct positions.

BA9P — Implement TreeColoring

solved Problem statement

How BA9E's shared-substring question is answered on a generalised suffix tree: colour leaves by which string they came from, and an internal node goes purple exactly when its substring occurs in both.

BA6A — Implement GreedySorting to Sort a Permutation by Reversals

solved Problem statement

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.

BA11A — Construct the Graph of a Spectrum

solved Problem statement

Reading a peptide off a spectrum rather than guessing peptides and scoring them as BA4 did. Every path from 0 to the heaviest mass spells a candidate, so sequencing becomes a path problem instead of a search over 20^n peptides.

BA11B — Implement DecodingIdealSpectrum

solved Problem statement

A spectrum holds prefix and suffix masses mixed together, so not every path is an answer — each candidate is rebuilt and checked. GPFNA and its reverse ANFPG both survive, because reversing a peptide only swaps which masses are prefixes.

BA11C — Convert a Peptide into a Peptide Vector

solved Problem statement

Puts a peptide in the same shape as a spectrum so the two can be compared by a dot product — which is what makes scoring one multiplication per position and finding the best peptide a path problem.

BA11D — Convert a Peptide Vector into a Peptide

solved Problem statement

The inverse of BA11C: gaps between consecutive 1s are the residue masses, so nothing has to be searched for. Asserted by round-tripping.

BA11E — Sequence a Peptide

solved Problem statement

The heaviest path through a graph of prefix positions. Negative entries matter — a spectral vector is measurement, not a count, so a path is penalised for claiming a prefix the data argues against, which is what stops the answer being simply the longest path.

BA11F — Find a Highest-Scoring Peptide in a Proteome against a Spectrum

solved Problem statement

The realistic version of BA11E: only substrings of a known proteome are candidates, which is how proteomics actually works and what makes the search tractable.

BA11G — Implement PSMSearch

solved Problem statement

A real experiment produces thousands of spectra, most matching nothing. The threshold is what separates them — without it every spectrum gets a peptide and most assignments are wrong. One of the two sample spectra is correctly left unassigned.

BA11H — Compute the Size of a Spectral Dictionary

solved Problem statement

If thousands of peptides would score as well, a high score means nothing. Counted rather than enumerated, for the same reason as BA4D — and cross-checked here against brute-force enumeration, which is only possible because this vector is tiny.

BA11I — Compute the Probability of a Spectral Dictionary

solved Problem statement

What turns a match into evidence: a score of 8 means nothing alone, a score only 0.375 of random peptides reach means something. Asserted to agree with BA11H — three length-3 peptides at (1/2)^3 each.

BA11J — Find a Highest-Scoring Modified Peptide against a Spectrum

solved Problem statement

Proteins are modified after they are made, so a modified peptide's spectrum matches nothing under exact search. XXZ weighs 13 against a vector of length 14, so at least one modification is forced — which the assertion checks rather than taking on trust.

BA3K — Generate Contigs from a Collection of Reads

solved Problem statement

What assembly actually produces. BA3H asked for the genome, which needs an Eulerian path to exist and be unique — real data gives neither. Where the graph branches the reads genuinely do not say which way the genome went, so the honest output is the unambiguous stretches and no more.

BA3L — Construct a String Spelled by a Gapped Genome Path

solved Problem statement

BA3J had to find the path; here it is given, so what remains is the overlap check — a path whose two halves disagree spells nothing at all, however valid it looked in the graph.

BA3M — Generate All Maximal Non-Branching Paths in a Graph

solved Problem statement

A run of 1-in-1-out nodes carries no choice, so collapsing it loses nothing; everywhere else is a real branch. The isolated cycle has no non-branching start and is only found by a second pass — without it, it would be silently dropped. Reported from 6 rather than 7, since a cycle has no first node.

BA9R — Construct a Suffix Tree from a Suffix Array

solved Problem statement

BA9C built the tree by collapsing a suffix trie, which is quadratic before the collapse. The suffix and LCP arrays carry the same information in two flat integer arrays and rebuild the tree in one pass — which is why real tools store the arrays and never materialise the tree.