One way to determine the amino acid composition of a peptide from its experimental spectrum would be to take the smallest masses present in the spectrum (between 57 and 200 Da). However, even if only a single amino acid mass is missing, then this approach will fail to reconstruct the peptide's amino acid composition.

Let’s take a different approach. Say that our experimental spectrum contains the masses of subpeptides NQE and NQ. If we subtract these two masses, then we will obtain the mass E for free, even if it was not present in the experimental spectrum! If the underlying peptide is NQEL, then we can also find the mass of E by subtracting the masses of QE and Q or NQEL and LNQ.

Following this example, we define the convolution of a spectrum by taking all positive differences of masses in the spectrum. The tables on the next steps show the convolutions of the theoretical and simulated spectra of NQEL that we encountered before (spectra reproduced below).

Theoretical simulated spectrum nqel

Spectral convolution nqel

Figure: Spectral convolution for the theoretical spectrum of NQEL. The most frequent elements in the convolution between 57 and 200 are (multiplicities in parentheses): 113 (8), 114 (8), 128 (8), 129 (8).

As predicted, some of the values in these tables appear more frequently than others. For example, 113 (the mass of L) has multiplicity 8 in the table above; we say that 113 has multiplicity 8. Six of the eight occurrences of 113 in the table above correspond to subpeptide pairs differing in an L: L and ""; LN and N; EL and E; LNQ and NQ; QEL and QE; NQEL and NQE.

Spectral convolution simulated nqel

Figure: Spectral convolution for the simulated spectrum of NQEL. The most frequent elements in the convolution between 57 and 200 are (multiplicities in parentheses): 113 (4), 114 (4), 128 (4), 99 (3), 129 (3).

Interestingly, 129 (the mass of E) pops up three times in the above convolution of the simulated spectrum, even though 129 was missing from the spectrum itself.

We now should feel confident about using the most frequently appearing integers in the convolution as a guess for the amino acid composition of an unknown peptide. In our simulated spectrum for NQEL, the most frequent elements of the convolution in the range from 57 to 200 are (multiplicities in parentheses):

113 (4), 114 (4), 128 (4), 99 (3), 129 (3)

Note that these most frequent elements capture all four amino acids in NQEL.

Spectral Convolution Problem: Compute the convolution of a spectrum.

Input: A collection of integers Spectrum.
Output: The list of elements in the convolution of Spectrum. If an element has multiplicity k, it should appear exactly k times; you may return the elements in any order.

Code Challenge Solve the Spectral Convolution Problem at Cogniterra or Rosalind.Solve it with the autograderFree to start in the interactive text

Recall that LeaderboardCyclopeptideSequencing failed to reconstruct Tyrocidine B1 from Spectrum₁₀ when using the extended alphabet of amino acids. The ten most frequent elements of its spectral convolution in the range from 57 to 200 are (with multiplicities in parentheses):

147 (35) 128 (31) 97 (28) 113 (28) 114 (26)

186 (23) 57 (21) 163 (21) 99 (18) 145 (18)

Every mass in this list except for 57 and 145 captures an amino acid in Tyrocidine B1! The figure on the next step shows the convolution of Spectrum₁₀.

Figure: The spectral convolution of the experimental spectrum Spectrum₁₀ for Tyrocidine B1. For each element of the spectral convolution (shown as a number within a box), its y-coordinate represents the number of times that the element appears in the spectral convolution. Green boxes represent masses of amino acids from Tyrocidine B1.

We now have the outline for a new cyclopeptide sequencing algorithm. Given an experimental spectrum, we first compute the convolution of an experimental spectrum. We then select the M most frequent elements between 57 and 200 in the convolution to form an extended alphabet of candidate amino acid masses. In order to be fair, we should include the top M elements of the convolution "with ties". Finally, we run the algorithm LeaderboardCyclopeptideSequencing, where the amino acid masses are restricted to this alphabet. We call this algorithm ConvolutionCyclopeptideSequencing.

Code Challenge Implement ConvolutionCyclopeptideSequencing. (Solve at Cogniterra or Rosalind.)Solve it with the autograderFree to start in the interactive text

Input: An integer M, an integer N, and a collection of (possibly repeated) integers Spectrum.
Output: A cyclic peptide LeaderPeptide with amino acids taken only from the top M elements (and ties) of the convolution of Spectrum that fall between 57 and 200, and where the size of Leaderboard is restricted to the top N (and ties).

Exercise Break Run ConvolutionCyclopeptideSequencing on Spectrum₂₅ (reproduced below) with N = 1000 and M = 20. Identify the 86 highest-scoring linear peptides. Solve at Cogniterra.

Tyrocidine spectrum 25

ConvolutionCyclopeptideSequencing (with N = 1000 and M = 20) now correctly reconstructs Tyrocidine B1 from Spectrum₁₀. The true test of this algorithm is whether it will work on a noisier spectrum. Recall that our previous algorithm failed to identify the correct peptide for Spectrum₂₅. In contrast, ConvolutionCyclopeptideSequencing (with N = 1000 and M = 20) now correctly identifies Tyrocidine B1 from this spectrum!

The Spectral Convolution Saves the Day