Mass-Spec Peptide ID

Every living cell is driven by proteins, and proteins are chains of amino acids called peptides. To understand disease, drug action, or cell behaviour, scientists need to know which peptides are present in a sample — and in what amounts. The tool they reach for is a mass spectrometer.

The instrument works by fragmentation. A peptide is ionized, selected, and then deliberately broken apart inside a collision chamber. The resulting fragments — called b-ions and y-ions — are measured by the mass their charged pieces carry. The output is a spectrum: a list of peaks, each at a mass-to-charge ratio that corresponds to a particular fragment.

The puzzle is now a matching problem. Given the observed spectrum, which amino-acid sequence would produce exactly those fragment masses? The answer is not obvious: twenty amino acids can be chained in astronomically many ways, and real spectra are noisy and incomplete. The field has spent decades turning this needle-in-a-haystack search into a tractable computation — and it is still an open engineering challenge.

Below is a simulated tandem-MS experiment. An unknown peptide was fragmented; the observed spectrum shows the resulting peaks (mass values in Daltons). Four candidate sequences are listed. For each candidate the demo computes the theoretical b- and y-ions and counts how many match the observed peaks within a tolerance window.

<p class="hint">{{hint_para}}</p>
<div class="spectrum-wrap">
  <div class="spectrum-label">{{observed_label}}</div>
  <canvas id="spectrum" width="560" height="120"></canvas>
</div>
<div class="candidates" id="candidates"></div>
<div class="status" id="status"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.spectrum-wrap { margin-bottom: .5rem; }
.spectrum-label { font-size: .78rem; color: #666; margin-bottom: .2rem; font-weight: 600; text-transform: uppercase; letter-spacing: .04em; }
canvas { display: block; width: 100%; border: 1px solid #cdd9e3; border-radius: 6px; background: #f8fafc; }
.candidates { display: flex; flex-direction: column; gap: .45rem; }
.cand-row { display: flex; align-items: center; gap: .5rem; flex-wrap: wrap; padding: .4rem .6rem; background: #f1f5f9; border-radius: 8px; border: 1.5px solid transparent; transition: border-color .15s; }
.cand-row.selected { border-color: #1d3557; background: #e8eef3; }
.cand-seq { font: 700 15px ui-monospace, monospace; color: #1d3557; min-width: 90px; }
.cand-score { font-size: .82rem; color: #555; flex: 1; }
.cand-score b { color: #0a7d33; }
button.show-btn { font: 600 13px system-ui, sans-serif; padding: .3rem .7rem; border: 1px solid #1d3557; background: #1d3557; color: #fff; border-radius: 6px; cursor: pointer; white-space: nowrap; }
button.show-btn.active { background: #c92f3c; border-color: #c92f3c; }
.status { font-size: .95rem; font-weight: 600; margin-top: .5rem; min-height: 1.3em; color: #0a7d33; }

// Code not found

Click Show ions for any candidate to see its theoretical fragment masses laid over the observed spectrum. The candidate whose ions overlap the most peaks is the best match — but notice that two candidates can share many peaks, making the decision ambiguous when the spectrum is noisy.

How hard is it to recover a sequence from a spectrum?

• Verification is easy. Given a candidate sequence and a spectrum, computing the theoretical ions and counting matches takes linear time in the sequence length.
• Database search is tractable in practice — but not in theory. Modern tools (Sequest, Mascot, MaxQuant) score every entry in a protein database against the spectrum. If the database has $N$ peptides the search is $O(N \cdot L)$ where $L$ is the average peptide length. That is fast when databases are small, but genomic databases now contain billions of candidates.
• De novo sequencing is NP-hard. When no database is available, the algorithm must reconstruct the sequence from scratch. This is equivalent to finding a path in a spectrum graph — a directed acyclic graph whose nodes are observed peaks and whose edges correspond to amino-acid mass differences. Finding the highest-scoring path through this graph with variable modifications (oxidation, phosphorylation, …) and missing peaks is NP-hard in the general case, as shown by Pevzner and colleagues in work on the Spectral Alignment Problem (2000).
• The search space explodes with modifications. Each residue can carry one of dozens of chemical modifications. With $k$ possible modifications per position and a peptide of length $L$, the candidate space grows as $O(k^{L})$ — the same exponential barrier that limits knapsack and sequence alignment.

The field bypasses this wall through heuristics, index structures, and machine-learning scoring functions — but the underlying combinatorial hardness never goes away.

Matching a spectrum to a sequence is not just an academic puzzle — it underpins much of modern biology and medicine:

• Proteomics and biomarker discovery: identifying which proteins (and in what abundance) differ between healthy and diseased tissue drives the search for cancer, Alzheimer's, and cardiovascular biomarkers.
• Drug target validation: mass-spec confirms that a drug binds its intended protein and not off-target sites, reading the modification directly from the fragment spectrum.
• Vaccine and antigen design: peptide mapping tells immunologists exactly which fragments of a pathogen trigger immune responses, guiding epitope-based vaccine design.
• Food authenticity and safety: species-specific peptides act as fingerprints; a single spectrum run can detect meat fraud or allergen contamination.
• Microbiome research: metaproteomics identifies the proteins expressed by thousands of microbial species at once, matching millions of spectra against enormous databases — a sequence alignment problem at planetary scale.

Every one of these applications ultimately runs the same combinatorial engine: score candidates, rank them, decide. The computational complexity of that decision is what separates a 10-minute database search from a week-long de novo reconstruction.

A mass spectrometer does not read a protein like a book. It shatters it into pieces and hands you a list of masses. Reassembling the original sequence from that debris is a combinatorial search — easy to verify, hard to solve from scratch, and explosive when chemical modifications enter the picture.

The tools proteomics has built to tame this search — fast scoring heuristics, indexed databases, learned ranking models — are engineering marvels. But they are workarounds for an underlying hardness that touches the same territory as sequence alignment and de novo reconstruction more broadly. The next time a lab report names a protein from a single drop of blood, remember: behind that answer sits a search through an exponential forest of candidates, pruned by decades of algorithmic ingenuity.