We will start analyzing spectra by first looking at an unrealistic ideal spectra, and then we'll move to real spectra. Let's start from analyzing this short peptide. Let's generate all its prefix peptides and all its suffix peptide. Let's measure the masses of all prefix peptides and all suffix peptides, and our goal is, from these masses, to reconstruct the original peptide. Can we do this? Well, an important thing to realize is that we don't know which masses correspond to prefix fragments and which masses correspond to suffix fragments, and therefore, what we are given is the ideal spectrum of the peptide, which is simply a collection of both prefix and suffix masses. We will say that a given peptide "explains" a spectrum if the ideal spectrum of this peptide is equal to the spectrum. So we have now a decoding problem, which is to reconstruct a peptide from its ideal spectrum. Input: A collection of integers, Spectrum. Output: An amino acid string Peptide that explains Spectrum. To solve it, let's construct a graph. We will form a set of nodes of this graph by designing a single node for every element of the spectrum, and we will construct edges of the graph by connecting two nodes if the difference between their corresponding labels is equal to the mass of amino acids, and we will label this edge by the mass of this amino acid. Here's the graph we construct for our ideal spectrum, and what will be the solution of our problem of decoding an ideal spectrum problem? Of course, we need to walk from the source node 0 to the sink, and the path that we'll spell will correspond to the peptide we are trying to find. As a result, I propose the following Decoding Ideal Spectrum Algorithm: First, construct a graph from Spectrum. Second, find a path from source to sink in the resulting graph. And finally, return the amino acid string spelled by this path. That sounds simple, but does it really work for all spectra? It clearly worked for the simple spectrum that we considered before. Let's take a look at this spectrum, and I will tell you that this is an ideal spectrum of an unknown peptide. Let's construct the graph of Spectrum and let's consider this path in this graph. This graph spells out the peptide NTTAG. But if we take the ideal spectrum of NTTAG, it will turn out that it is not equal to the original spectrum, which means that we are doing something wrong. Of course, in this graph, there is a path that spells the correct solution of the problem, but we don't know how to find it. What we can do, however, is to consider all possible paths in the graph, and this is done by a new version of the Decoding Ideal Spectrum Algorithm, that first constructs the graph of Spectrum, explores all paths in the resulting graph, but for each path, it first checks the condition, if the ideal spectrum of the peptide is really equal to the spectrum. If this condition is met, then it returns the peptide. So this is definitely a correct solution of the problem, but is it an efficient solution? You will see it that it's actually an exponential algorithm, but there are polynomial solutions for this problem that we will not cover in this course. Our goal, however, is to move from decoding ideal spectra to the decoding real spectra. And on this line you see an ideal spectrum will be some false and missing masses and the real spectrum. And the reality is that, in spectra generated by mass spectrometers, there are usually many false and missing masses, thus complicating our problem of decoding a real spectrum, that we will consider in the next lecture. An important thing about decoding a real spectrum is that its objective is to find an amino acid string Peptide that explains Spectrum the best. But what does it mean to be the "best" peptide explaining the spectrum? We will learn about this in the next segment.
