We first encountered brute force algorithms when looking for motifs. In this chapter, we will discuss how to speed up brute force algorithms for peptide sequencing to make them practical.

Let’s design a straightforward brute force algorithm for the Cyclopeptide Sequencing Problem. We denote the total mass of an amino acid string Peptide as Mass(Peptide). In mass spectrometry experiments, whereas the peptide that generated Spectrum is unknown, Mass(Peptide) can be inferred from Spectrum and is denoted ParentMass(Spectrum). For the sake of simplicity, we will assume that for all experimental spectra, ParentMass(Spectrum) is equal to the largest mass in Spectrum.

The brute force cyclopeptide sequencing algorithm BFCyclopeptideSequencing generates all possible peptides whose mass is equal to ParentMass(Spectrum) and then checks which of these peptides has theoretical spectra matching Spectrum.

BFCyclopeptideSequencing(Spectrum) 
  for every peptide with Mass(Peptide) equal to ParentMass(Spectrum) 
    if Spectrum = Cyclospectrum(Peptide) 
      output Peptide

There should be no question that BFCyclopeptideSequencing will solve the Cyclopeptide Sequencing Problem. However, we should be concerned about its running time: how many peptides are there having mass equal to ParentMass(Spectrum)?

Counting Peptides with Given Mass Problem: Compute the number of peptides of given mass.

Input: An integer m.
Output: The number of linear peptides having integer mass m.

Exercise Break (Optional): Solve the Counting Peptides with Given Mass Problem. (Solve at Cogniterra or Rosalind.) The integer mass table is reproduced below; recall that we assume that peptides are formed from only 18 amino acid masses. That is, I/L are considered the same and K/Q are considered the same, so we would count AIKD and ALQD as just one peptide, not two.

Integer mass table

Suggestion: This exercise is optional because you may have difficulty solving this problem; if so, please return to it after learning more about dynamic programming algorithms in a future lesson.

It turns out that there are trillions of peptides that have the same integer mass (1322) as Tyrocidine B1 (figure below). Therefore, BFCyclopeptideSequencing is completely impractical, and we will not even bother asking you to implement it.

Exercise Break This figure suggests that for large m, the number of peptides with given integer mass m can be approximated as k · C^m, where k and C are constants. If you solved the exercise break above, use your solution to find C. Test your solution at Cogniterra.

Counting peptides

Figure: The number of peptides with given integer mass grows exponentially.

A Brute Force Algorithm for Cyclopeptide Sequencing