Peptide Sequencing

One question that often comes up is, given a peptide, what is the string of amino acids that form the peptide string $P$?

Overall, this problem is hard, and not well solved. The techniques in this post provide the biologically relevant sequence about 30% of the time, according to Pevzner and Compeau in Bioinformatics Algorithms.

Mass Spectrometry

A mass spectrometer breaks molecules apart and weighs the fragments. We assume that the break point selected by the mass spectrometer will be uniformly-randomly distributed such that every sub-peptide if $P$ is massed, with roughly equal probability. Given millions of identical peptides, mass spectrum will provide the mass of every sub-peptide.

The theoretical spectrum, therefore, will simply be the mass of every sub-peptide of $P$. A sub-peptide Depending on if the peptide is circular or not, the

Amino Acid Mass Table

The table below shows the mass (in Daltons) of each amino acid, based on its composition.

A simplified version, the integer mass table, is given here (in the form of a C++ map):

  static auto* kIntegerMassTable = new std::map<char, int>({
    {'G', 57},
    {'A', 71},
    {'S', 87},
    {'P', 97},
    {'V', 99},
    {'T', 101},
    {'C', 103},
    {'I', 113},
    {'L', 113},
    {'N', 114},
    {'D', 115},
    {'K', 128},
    {'Q', 128},
    {'E', 129},
    {'M', 131},
    {'H', 137},
    {'F', 147},
    {'R', 156},
    {'Y', 163},
    {'W', 186},
  });

Note that I and L; K and Q have the same integer masses.

Consistency

Two spectrums $S_1$ and $S_2$ are consistent if one is a subset of the other. For example, the empty spectrum is consistent will all other spectra:

$S_1 = Spectrum(P = \epsilon) = \emptyset$ is a subset of all possible spectra.

And importantly, any sub-peptide of $P$ has a consistent spectrum with $Spectrum(P)$

$P_1 = Substring(P_2) \implies IsConsistent(Spectrum(P_1), Spectrum(P_2))$

When growing a peptide sequence $P$ of length $L \to L + 1$ using amino acid $A$, we will add $A$ to each mass in the spectrum.

Note that the consistency need only be for the linear spectrum.

Algorithm

Consistency properties allow reverse-engineering candidate amino acid sequences for specturm $S$, by:

1. Initializing candidate sequences with a single candidate, $P_0 = \epsilon$ (empty string),
2. Extending every candidate sequence with every possible amino acid, followed by
3. Prune every candidate whose spectrum is not consistent with $S$
4. Continue steps 2 and 3 until either (a) one or more candidate $P$ has $Spectrum(P) = S$, or (b) all candidates are pruned.

Beam Search

Of course, the algorithm above assumes no errors. In practice, the spectrum will not match the ideal. Therefore, user can modify step (3), from requiring strict consistency, to keeping the most promising candidates. The score of a candidate is determined by how many masses in the generated spectrum are present in the target spectrum.

Missing Masses: Spectral Convolution

To find missing masses, find the modal positive differences between elements of the spectrum. The common elements are likely to be individual amino acids (or other sub-components) of the molecule.

The masses with the top-k count, in the range of 57..200, can correlate with the amino acids present in the sequence.

Statistical Significance

It can be helpful to compare any matches discovered, against a randomly generated baseline.