Rosalind — Bioinformatics Textbook Track — Mass spectrometry

BA4C — Generate the Theoretical Spectrum of a Cyclic Peptide

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.

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.