It turns out that most prolines in the T-Rex peptides identified by Asara were actually modified version of prolines called hydroxyprolines. And in this segment, we will talk about searches for post-translationally modified peptides. The central dogma doesn't mention it, but many proteins are subject to a large number of post-translational modifications that are important for cell-signaling and metabolic regulation. In fact, most proteins are post-translationally modified and over 600 types of modifications of amino acids are known today. Some of them are extremely important, such as phosphorylation, shown on this slide. How does a modification affect a peptide vector? If you think about this, modification is simply changing the mass of the amino acid. If we limit ourselves to computational analysis of modification and a modification of mass "delta". applied to an amino acid results in adding data to its mass. For phosphorylation, for example, delta = 80. For hydroxyproline in collagens, it is equal to 16, and for a modification of lysine into allysin, it is equal to -1. Therefore, modifications essentially increase the number of letters in the amino acid alphabet and complicate peptide identifications. In the beginning of this lecture, we looked at the ideal spectrum of this peptide. Let's now look at how this ideal spectrum changes if we introduce a modification on this peptide. Here's this modification on C+16, and this modification affects two prefix peptides and, in fact, three suffix peptides. So, the ideal spectrum has changed in this case. But please note that we don't know in advance what is the mass of modifications, and we don't know on which amino acid this modification is residing. Let's also take a look at how a modification affects a peptide vector. In this particular example, a modification of mass 3 on the i-th amino acids essentially amounts to inserting a block of 3 consecutive 0s before the i-th occurrence of 1 in the peptide vector. This is for the modification of positive mass. For a modification of negative mass, -2 in this case, the modification corresponds to deleting the block of 2 0s before the i-th occurrence of 1 in the peptide. And after we figure out how modifications affect the peptide vector, we are ready to formulate the spectral alignment problem. Before we do this, let's define the notion of Variants_k(Peptide) as the set of all modified variants of Peptide with up to k modifications. We want to solve the spectral alignment problem, which is: Given a peptide and a spectral vector, find a modified variant of this peptide that maximizes the peptide-spectrum score among all variants of the peptide with up to k modifications. Of course, there is a very simple solution of this problem: We simply check all possible peptides in the set Variants_k(Peptide) and see which of them has the maximum score. But this will be too slow because our more ambitious goal is to solve the following modification search problem: Given a Spectrum and a Proteome, find a peptide of a maximum score against this Spectrum among all modified peptides in the Proteome with up to k modifications. Obviously, to efficiently solve the modification search problem, we need to come up with a very fast algorithm for solving the spectrum alignment problem. And, if we figure out how to search for modified peptides, we will immediately be able to search for mutated peptides as well because the mutation search problem results from simply substituting the word modifications for mutations, like shown in this slide.