In "Number of peptides with a given total mass1" we first encountered the problem of reconstructing a cyclic peptide from its theoretical spectrum. This problem is called the cyclopeptide sequencing problem: given an ideal experimental spectrum, find a cyclic peptide whose theoretical spectrum matches the experimental spectrum. It is solved by the following algorithm.

CyclopeptideSequencing(Spectrum)
    Peptides ← a set containing only the empty peptide
    while Peptides is nonempty
        Peptides ← Expand(Peptides)
        for each peptide Peptide in Peptides
            if Mass(Peptide) = ParentMass(Spectrum)
                if Cyclospectrum(Peptide) = Spectrum
                    output Peptide
                remove Peptide from Peptides
            else if Peptide is not consistent with Spectrum
                remove Peptide from Peptides

Assignment

Write a function cyclopeptide_sequencing that takes an ideal experimental spectrum $$s$$. The function must return a set containing all amino acid strings $$p$$ such that

Cyclospectrum($$p$$) = $$s$$

Example

>>> cyclopeptide_sequencing((0, 113, 128, 186, 241, 299, 314, 427))
{(113, 128, 186), (113, 186, 128)}
>>> cyclopeptide_sequencing((0, 113, 114, 128, 129, 227, 242, 242, 257, 355, 356, 370, 371, 484))
{(113, 129, 128, 114), (113, 114, 128, 129)}

Note

Remind that the tuple representation of cyclic peptide is cyclic as well, and we choose the representation that comes first in lexicographic order.

Resources