July 29, 2015, 1:08 a.m. by Rosalind Team

In “Generate the Theoretical Spectrum of a Cyclic Peptide”, we generated the theoretical spectrum of a known cyclic peptide. Although this task is relatively easy, our aim in mass spectrometry is to solve the reverse problem: we must reconstruct an unknown peptide from its experimental spectrum. We will start by assuming that a biologist is lucky enough to generate an **ideal experimental spectrum** *Spectrum*, which is one coinciding with the peptide’s theoretical spectrum. Can we reconstruct a peptide whose theoretical spectrum is *Spectrum*?

Denote the total mass of an amino acid string *Peptide* as *Mass*(*Peptide*). In mass spectrometry experiments, whereas the peptide that generated a spectrum is unknown, the peptide’s mass is typically known and is denoted *ParentMass*(*Spectrum*). Of course, given an ideal experimental spectrum, *Mass*(*Peptide*) is given by the largest mass in the spectrum.

A brute force approach to reconstructing a peptide from its theoretical spectrum would
generate all possible peptides whose mass is equal to *ParentMass*(*Spectrum*) and then check which of these peptides has theoretical spectra matching *Spectrum*. However, we should be concerned about the running time of such an approach: how many peptides are there having mass equal to *ParentMass*(*Spectrum*)?

*Compute the number of peptides of given total mass.*

Given: An integer *m*.

Return: The number of linear peptides having integer mass *m*.

1024

14712706211

## Note

If you have difficulty solving this problem or getting the runtime down, please return to it after learning more about dynamic programming algorithms in Chapter 5.