CSE182-L12Ion mass computationsPeptide chainsM/Z values for b/y-ionsDe novo interpretationDe Novo Interpretation: ExampleComputing possible prefixesPutative Prefix MassesSpectral GraphSlide 10Re-defining de novo interpretationTwo problemsToo many nodesMultiple InterpretationNon-Intersecting Forbidden pairsThe forbidden pairs methodD.P. for forbidden pairsSlide 18Slide 19The complete algorithmDe Novo: Second issueDe novo: Weighting nodes in Spectrum GraphDe novo: Weighting nodesDe Novo Interpretation SummaryThe dynamic nature of the cellWhat happens to the spectrum upon modification?Effect of PT modifications on identificationDb matching in the presence of modificationsScoring spectra in the presence of modificationModificationsFast identification of modified peptidesFiltering Peptides to speed up searchBasic FilteringTag-based filteringTag generationTag based search using triesModification SummaryMS based quantitationThe consequence of signal transductionTranscriptionTranslationQuantitation: Gene/Protein ExpressionGene ExpressionFa 06 CSE182CSE182-L12Mass SpectrometryPeptide identificationFa 06 CSE182Ion mass computations•Amino-acids are linked into peptide chains, by forming peptide bonds•Residue mass–Res.Mass(aa) = Mol.Mass(aa)-18–(loss of water)Fa 06 CSE182Peptide chains•MolMass(SGFAL) = resM(S)+…res(L)+18Fa 06 CSE182M/Z values for b/y-ions•Singly charged b-ion = ResMass(prefix) + 1•Singly charged y-ion= ResMass(suffix)+18+1•What if the ions have higher units of charge? RNH+3-CH-CO-NH-CH-COOH R RNH+3-CH-CO-NH-CH-CO R H+ RNH2-CH-CO-………-NH-CH-COOH RIonized PeptideFa 06 CSE182De novo interpretation•Given a spectrum (a collection of b-y ions), compute the peptide that generated the spectrum.•A database of peptides is not given!•Useful?–Many genomes have not been sequenced, but are very useful.–Tagging/filtering–PTMsFa 06 CSE182De Novo Interpretation: ExampleS G E K0 88 145 274 402 b-ions420 333 276 147 0 y-ionsbyy2100 500400300200M/Zb112Ion Offsetsb=P+1y=S+19=M-P+19Fa 06 CSE182Computing possible prefixes•We know the parent mass M=401.•Consider a mass value 88• Assume that it is a b-ion, or a y-ion•If b-ion, it corresponds to a prefix of the peptide with residue mass 88-1 = 87.•If y-ion, y=M-P+19.–Therefore the prefix has mass •P=M-y+19= 401-88+19=332•Compute all possible Prefix Residue Masses (PRM) for all ions.Fa 06 CSE182Putative Prefix MassesPrefix MassM=401 b y88 87 332145 144 275147 146 273276 275 144 S G E K0 87 144 273 401•Only a subset of the prefix masses are correct. •The correct mass values form a ladder of amino-acid residuesFa 06 CSE182Spectral Graph•Each prefix residue mass (PRM) corresponds to a node.•Two nodes are connected by an edge if the mass difference is a residue mass.•A path in the graph is a de novo interpretation of the spectrum87144GFa 06 CSE182Spectral Graph•Each peak, when assigned to a prefix/suffix ion type generates a unique prefix residue mass.•Spectral graph: –Each node u defines a putative prefix residue M(u).–(u,v) in E if M(v)-M(u) is the residue mass of an a.a. (tag) or 0.–Paths in the spectral graph correspond to a interpretation 3001004012000SGEK27387 146144 275332Fa 06 CSE182Re-defining de novo interpretation•Find a subset of nodes in spectral graph s.t.–0, M are included–Each peak contributes at most one node (interpretation)(*)–Each adjacent pair (when sorted by mass) is connected by an edge (valid residue mass)–An appropriate objective function (ex: the number of peaks interpreted) is maximized3001004012000SGEK27387 146144 27533287144GFa 06 CSE182Two problems•Too many nodes.–Only a small fraction are correspond to b/y ions (leading to true PRMs) (learning problem)•Multiple Interpretations–Even if the b/y ions were correctly predicted, each peak generates multiple possibilities, only one of which is correct. We need to find a path that uses each peak only once (algorithmic problem).–In general, the forbidden pairs problem is NP-hard3001004012000SGEK27387 146144 275332Fa 06 CSE182Too many nodes•We will use other properties to decide if a peak is a b-y peak or not.•For now, assume that (u) is a score function for a peak u being a b-y ion.Fa 06 CSE182Multiple Interpretation•Each peak generates multiple possibilities, only one of which is correct. We need to find a path that uses each peak only once (algorithmic problem).•In general, the forbidden pairs problem is NP-hard•However, The b,y ions have a special non-interleaving property•Consider pairs (b1,y1), (b2,y2)–If (b1 < b2), then y1 > y2Fa 06 CSE182Non-Intersecting Forbidden pairs3001004002000SGEK•If we consider only b,y ions, ‘forbidden’ node pairs are non-intersecting, •The de novo problem can be solved efficiently using a dynamic programming technique.87332Fa 06 CSE182The forbidden pairs method•Sort the PRMs according to increasing mass values.•For each node u, f(u) represents the forbidden pair•Let m(u) denote the mass value of the PRM.•Let (u) denote the score of u•Objective: Find a path of maximum score with no forbidden pairs.300100400200087332uf(u)Fa 06 CSE182D.P. for forbidden pairs•Consider all pairs u,v–m[u] <= M/2, m[v] >M/2•Define S(u,v) as the best score of a forbidden pair path from –0->u, and v->M•Is it sufficient to compute S(u,v) for all u,v?300100400200087332u vFa 06 CSE182D.P. for forbidden pairs•Note that the best interpretation is given by€ max((u,v )∈E )S(u,v)300100400200087332u vFa 06 CSE182D.P. for forbidden pairs•Note that we have one of two cases.1. Either u > f(v) (and f(u) < v)2. Or, u < f(v) (and f(u) > v)•Case 1.–Extend u, do not touch f(v)3001004002000uf(v) v€ S(u,v) = max(u':(u',u)∈Eu'≠ f (v))S(u',v) + δ(u')Fa 06 CSE182The complete algorithm for all u /*increasing mass values from 0 to M/2 */for all v /*decreasing mass values from M to M/2 */ if (u < f[v]) else if (u > f[v])If (u,v)E /*maxI is the score of the best interpretation*/maxI = max {maxI,S[u,v]}€ S[u,v] = max(w,u)∈Ew≠ f (v ) ⎛ ⎝ ⎜ ⎞ ⎠ ⎟S[w,v] + δ(w)€ S[u,v] = max(v,w )∈Ew≠ f (u) ⎛ ⎝ ⎜ ⎞ ⎠ ⎟S[u,w] + δ(w)Fa 06 CSE182De Novo: Second issue•Given only b,y ions, a forbidden pairs path will solve the problem.•However, recall that there are MANY