Improved methods of identifying peptides and proteins by mass spectrometry

CA 02303758 2000-04-06

Improved methods of identifying peptides and proteins by Mass Spectrometry

This invention relates to methods of identifying a protein, polypeptide or peptide by means of mass spectrometry and especially by tandem mass spectrometry (MS/MS). Preferred methods relate to the use of mass spectral data to identify an unknown protein where sequence is at least partially present in an existing database.

Although several well-established chemical methods for the sequencing of peptides, polypeptides and proteins are known (for example, the Edmân degradation), mass spectrometric methods are becoming increasingly important in view of their speed and ease of use. Mass spectrometric methods have been déveloped to the point at which they are capable of sequencing peptides in a mixture without any prior chemical purification or separation, typically using electrospray ionization and tandem mass spectrometry (MS/MS). For example, see Yates III (J. Mass Spectrom, 1998 vol. 33 pp. 1-19), Papayannopoulos (Mass Spectrom. Rev. 1995, vol. 14 pp. 49-73), and Yates III, McCormack, and Eng (Anal. Chem. 1996 vol. 68 (17) pp. 534A-540A). Thus, in a typical MS/MS sequencing experiment, molecular ions of a particular peptide are selected by the first mass analyzer and fragmented by collisions with neutral gas molecules in a collision cell. The second mass analyzer is then used to record the fragment ion spectrum that generally contains enough information to allow at least a partial, and often the complete, sequence to be determined.

Unfortunately, however, the interpretation of the fragment spectra is not straightforward. Manual interpretation (see, for example, Hunt, Yates III, et al, Proc. Nat. Acad. Sci. USA, 1986, vol. 83 pp 6233-6237 and Papayannopoulos, ibid) requires considerable experience and is time consuming. Consequently, many workers have developed algorithms and computer programs to automate the process, at least in part. The nature of the problem, however, is such that none of those so far developed are able to provide in reasonable time complete sequence information without either requiring some prior knowledge of the chemical structure of the peptide or merely identifying likely candidate sequences in existing protein structure databases. The reason for this will be understood from the following discussion of the nature of the fragment spectra produced.

Typically, the fragment spectrum of a peptide comprises peaks belonging to about half a dozen different ion series each of which correspond to different modes of fragmentation of the peptide parent ion. Each typically (but not invariably) comprises peaks representing the loss of successive amino acid residues from the original peptide ion. Because all but

CA 02303758 2000-04-06 two of the 20 amino adds from which most naturally occurring proteins are comprised have different masses, it is therefore possible to establish the sequence of amino acids from the difference in mass of peaks in any given series which correspond to the successive loss of an amino acid residue from the original peptide. However, difficulties arise in identifying to which series an ion belongs and from a variety of ambiguities that can arise in assigning the peaks, particularly when certain peaks are either missing or unrecognized. Moreover, other peaks are typically present in a spectrum due to various more complicated fragmentation or rearrangement routes, so that direct assignment of ions is fraught with difficulty. Further, electrospray ionization tends to produce multiply charged ions that appear at correspondingly rescaled masses, which further complicates the interpretation of the spectra. Isotopic dusters also lead to proliferation of peaks in the observed spectra. Thus, the direct transformation of a mass spectrum to a sequence is only possible in trivially small peptides.

The reverse route, transforming trial sequences to predicted spectra for comparison with the observed spectrum, should be easier, but has not been fully developed. The number of possible sequences for any peptide (20ⁿ, where n is the number of amino adds comprised in the peptide) is very large, so the difficulty of finding the correct sequence for, say, a peptide of a mere 10 amino acids (20¹⁰= 10¹³ possible sequences) will be appredated. The number of potential sequences increases very rapidly both with the size of the peptide and with the number (at least 20) of the residues being considered.

Details of the first computer programs for predicting probable amino add sequences from mass spectral data appeared in 1984 (Sakurai, Matsuo, Matsuda, Katakuse, Biomed. Mass Spectrom, 1984, vol. 11 (8) pp 397-399). This program (PAAS3) searched through all the amino acid sequences whose molecular weights coincided with that of the peptide being examined and identified the most probable sequences with the experimentally observed spectra. Hamm, Wilson and Harvan (CABIOS, 1986 vol. 2 (2) pp 115-118) also developed a similar program.

However, as pointed out by Ishikawa and Niwa (Biomed. and Environ. Mass Spectrom. 1986, vol. 13 pp 373-380), this approach is limited to peptides not exceeding 800 daltons in view of the computer time required to carry out the search. Parekh et al in UK patent application 2,325,465 (published November 1998) have resurrected this idea and give an example of the sequencing of a peptide of 1000 daltons which required 2 x 10⁶ possible sequences to be searched, but do not specify the computer time required. Nevertheless, despite the increase in the processing speed of computers between 1984 and 1999, a

CA 02303758 2000-04-06 simple search of all possible sequences for a peptide of molecular weights greater than 1200 daltons is still impractical in a reasonable time using the personal computer typically supplied for data processing with most commercial mass spectrometers.

This problem has long been recognized and several approaches to rendering the problem more tractable have been described. One of the most successful has been to correlate the mass spectral data with the known amino acid sequences comprised in a protein database rather than with every possible sequence. In the prior method known as peptide mass mapping, a protein may be identified by merely determining the molecular weights of the peptides produced by digesting it with a site-specific protease and comparing the molecular weights with those predicted from known proteins in a database. (See, for example, Yates, Speicher, et al in Analytical Biochemistry, 1993 vol 214 pp 397-408). However, mass mapping is ineffective if a protein or peptide comprises only a small number of amino acids residues or possible fragments, and is inapplicable if information about the actual amino acid sequences is required. As explained, tandem mass spectrometry (MS/MS) can be used to provide such sequence information. MS/MS spectra usually contain enough detail to allow a peptide to be at least partially, and often completely sequenced without reference to any database of known sequences (See copending application GB 9907810.7, filed 6 April 1999). There are, however, many circumstances where it is adequate, or even preferred, to establish sequences by reference to an existing database. Such methods were pioneered by Yates, et al, see, for example, PCT application 95/25281, Yates (J. Mass Spectrom 1998 vol 33 pp 1-19), Yates, Eng et al (Anal. Chem. 1995 vol 67 pp 1426-33). Other workers, including Mertz et al (Proc. Nat Acad. Sci. USA, 1996 vol 93 pp 8264-7), Figeys, et al (Rapid Commun. Mass Spectrom. 1998 vol 12 pp 1435-44), Jaffe, et al, (Biochemistry, 1998 vol 37 pp 16211-24), Arnot et al (Electrophoresis, 1998 vol 19 pp 968-980) and Shevchenko et al (J. Protein Chem. 1997 vol 16 (5) pp 481-490) report similar approaches.

As explained, it is generally easier to predict a fragmentation mass spectrum from a given amino acid sequence than to carry out the reverse procedure when comparing experimental MS data with sequence databases. A “fragmentation model” that describes the various ways in which a given amino acid sequence may fragment is therefore required. The chemical processes which result in fragmentation are fairly well understood, but because the number of possible routes increases very rapidly with the number of amino acid residues in a sequence it is difficult to build this knowledge into a definite model. The fragmentation models so far proposed (for example Eng et al, J. Am. Soc. Mass Spectrom, 1994 vol 5 pp 976-89) typically incorporate only a small number of possible fragmentation routes and typically produce a predicted spectrum in which all the

CA 02303758 2003-05-28

20208-1777 mass peaks have equal probability. This constrained approach comprises the accuracy of the comparison with an experimental spectrum, which is likely to represent the sum of many different fragmentation pathways operating simultaneously with different degrees of importance. Consequently the degree of confidence that can be placed in the identification of a sequence on the basis of the prior fragmentation models is reduced and the chance of an incorrect identification is increased.

A realistic fragmentation model is also required to predict spectra from pseudo-randomly generated trial sequences (as opposed to existing sequences comprised in a database). The fragmentation models described in the present application are applicable to both approaches.

According tc the present invention, there is provided a method of identifying a most probable amino acid sequence(s) which would account for a fragmentation mass spectrum of a protein or peptide, said method comprising the steps of:

a) producing the fragmentation mass spectrum (D) from said protein or peptide; b) providing a plurality of trial amino acid sequences; c) for each of a plurality of fragmentation routes (f) which together represent the possible ways that a trial amino acid sequence (S) will fragment, calculating:

1C i) the probability P(D given f) of the fragmentation mass spectrum (D), assuming a particular fragmentation route (f) ; and ii) the probability P(f given S) of having the fragmentation route (f) from each of said trial sequences (S) ;

d) calculating a likelihood factor P(D given S) that each trial sequence (S) is the true amino acid sequence of said peptide or protein by summing probabilistically over said plurality of fragmentation routes, such that:

P(D given S) P(D given f given S) _r e) selecting one or more of

CA 02303758 2003-05-28

20208-1777

4a said trial sequences (S) which have the highest likelihood factors calculated in step d) as being the most probable amino acid sequence(s) of said protein or peptide.

Embodiments of the present invention provide an improved method of modelling the fragmentation of a peptide or protein in a tandem mass spectrometer to facilitate comparison with an experimentally determined spectrum. Embodiments of the invention provide such a fragmentation model which takes account of all possible fragmentation pathways which a particular sequence of amino acids may undergo. Embodiments of the invention provide methods of identifying a peptide or protein by comparing an experimentally determined mass spectrum with spectra predicted using such a fragmentation model from a library of known peptides or proteins. Embodiments of the invention provide a de novo method of determining the amino acid sequence of an unknown peptide using sues a fragmentation model.

Embodiments of the invention provide a method of identifying the most prooaole ammo acid sequences which would account for the mass spectrum of a protein or peptide, the method comprising the steps of:

a) producing a processable mass spectrum from said peptide; and

b) using a fragmentation model to calculate the likelihood that any given trial amino acid sequence would account for said processable spectrum, said fragmentation model· comprising the step of summing probabilistically a plurality of fragmentation routes which together represent the possible ways that said trial sequence might fragment in accordance with a set of predefined rules, each said fragmentation route being assigned a prior probability appropriate to the chemical processes involved.

CA 02303758 2003-05-28

20208-1777

4b

In preferred methods, said plurality of fragmentation routes represent all the possible ways that a said trial sequence might fragmenz.

CA 02303758 2000-04-06

Preferably the fragmentation model is based on the production of at least two series of ions, the b series (which comprises ions representing the N-terminal residue of the trial sequence and the loss of C-terminal amino acid residues), and the y series (which comprises ions representing the C-terminal residue and the loss of N-terminal amino acid residues). Each family of ions behaves as a coherent series, with neighbouring ions likely to be either both present or both absent. This behaviour may be described by a Markov chain, in which the probability of an ion being observed is influenced by whether or not its predecessor was observed. The parameters of the chain may be adjusted to take account of the proton affinities of the residues and their physical bond strengths. The fragmentation model may be refined by including other ion series, particularly the a series (b ions which have lost CO), the z series (y” ions which have lost NH₃), and the more general loss of NH₃ or H₂O, again taking account of the probability of the chemical processes involved. Immonium ions equivalent to the loss of CO and H from the various amino acid residues may also be included. Further, the fragmentation model may comprise the generation of sub-sequences of amino acids, that is, sequences that begin and end at amino acid residues internal to the unknown peptide. It will be appreciated that the more realistic is the fragmentation model, the better will be the accuracy and fidelity of the computation of the most probable sequences. It is therefore envisaged that different fragmentation models may be employed if advances are made in understanding the chemical mechanism by which the mass spectrum of the peptide is produced.

Each of the chemical processes described above may be assigned a prior probability on the basis of the physical strength of the bonds broken in the proposed fragmentation step and the proton affinities of the various amino acid residues, thereby enabling the prior probability of each complete fragmentation route to be calculated. However, using Markov chains to model each of the ion series produced (eg, the b or y” series) means that it is unnecessary to compute an explicit spectrum for every possible fragmentation route for comparison with the processable spectrum. Instead, the method of the invention arrives at the same result by using the Markov chain representation of the various ion series to factorize the comparison, so that the likelihood summed over all the fragmentation routes can be computed in polynomial time (in the most preferred embodiment, linear time). This summed likelihood is a better basis for comparison with the processable spectrum than the likelihood or other score derived from a single fragmentation route, such as would be produced by prior fragmentation models, because the fragmentation of a real peptide involves many simultaneous routes. By the use of a

CA 02303758 2003-05-28

20208-1777 fully probabilistic fragmentation model, therefore, the method of the invention automatically accounts in a quantitative sense, for this multiplicity of routes.

As explained, using Markov chains to model the fragmentation process allows the sum over all the possible fragmentation patterns to oe calculated in linear time (ie, in a time proportional to the number of amino acid residues in the peptide) rather than in a time proportional to the exponentially large number of fragmentation patterns themselves. However, it will be appreciated that the invention is not limited to the particular fragmentation model described above, but includes any probabilistic fragmentation model that can be integrated computationally in polynomial time.

It will be appreciated that trial sequences used in the method of the invention may be obtained from one or more libraries or databases containing sequences or partial sequences of known peptides and proteins, or may be generated pseudo-randomly in a ce-novo sequencing method. For example, a fragmentation model according to the invention may be used to

2C calculate the likelihood of amino acid sequences comprised in an existing protein or peptide database accounting for an experimentally observed mass spectrum of a peptide. In this way the peptide, and/or the protein from which it is derived, may be identified. Conveniently, in such a method, only sequences or partial sequences having a molecular weight in a given range are selected from the database for input to the fragmentation model.

In one embodiment, the method assigns a likelihood factor to each trial amino acid sequence considered. The most 30 probable amino acid sequences in the database (or pseudorandomly generated sequences) which wouLd account for the processable

CA 02303758 2003-05-28

20208-1777 a

spectrum may then be identified as the trial sequences with the highest likelihood factors. However, a more precise method that is particularly appropriate in the case of de novo sequencing, is to use a Bayesian approach. Each trial sequence is assigned a prior probability on the basis of whatever information is known about it, including its relationship to the sample from which the processable spectrum is obtained. For example, m true de novo sequencing the prior probability of a trial sequence may be based on the average natural

1C abundances of the amino acid residues it comprises. In the case of database searches, it may be known, for example, that the sample is derived from a yeast protein, in which case, sequences in the database derived from yeasts may be assigned a higher prior probability.

CA 02303758 2000-04-06

The probability of a trial sequence accounting for the processable spectrum is then calculated by Bayes’ theorem, that is:

Probability (trial sequence AND processable spectrum ) =

Prior probability (trial sequence) x likelihood factor

In Bayesian terminology, the likelihood factor is:Probability (processable spectrum GIVEN trial sequence).

Although in certain simple cases the processable mass spectrum may simply be the observed mass spectrum, it is generally preferable to convert the observed spectrum into a more suitable form before attempting to sequence the peptide. Preferably, the processable spectrum is obtained by converting multiply-charged ions and isotopic clusters of ions to a single intensity value at the mass-to-charge ratio corresponding to a singly-charged ion of the lowest mass isotope, and calculating an uncertainty value for the actual mass and the probability that a peak at that mass-to-charge ratio has actually been observed. Conveniently, the uncertainty value of a peak may be based on the standard deviation of a Gaussian peak representing the processed peak and the probability that a peak is actually observed may be related to the signal-to-noise ratio ofthe peak in the observed spectrum. The program “MaxEnt3™” available from Micromass UK Ltd. may be used to produce the processable spectrum from an observed spectrum.

In order to carry out the methods of the invention a sample comprising one or more unknown peptides may be introduced into a tandem mass spectrometer and ionized using electrospray ionization. The molecular weights of the unknown peptides may typically be determined by observing the molecular ion groups of peaks in a mass spectrum of the sample. The first analyzer of the tandem mass spectrometer may then be set to transmit the molecular ion group of peaks corresponding to one of the unknown peptides to a collision cell, in which the molecular ions are fragmented by collision with neutral gas molecules. The second mass analyzer of the tandem mass spectrometer may then be used to record an observed fragmentation mass spectrum of the peptide. A processable mass spectrum may then be derived from the observed spectrum using suitable computer software, as explained. If the sample comprises a mixture of peptides, for example as might be produced by a tryptic digest of a protein, further peptides may be analyzed by selecting the appropriate molecular ion group using the first mass analyzer.

CA 02303758 2003-05-28

20208-1777

Also according to the present invention, there is provided an apparatus for identifying tne most probable amino acid sequence(s) in an unknown protein or peptide, the apparatus comprising: a mass spectrometer for generating a fragmentation mass spectrum (D) from a protein or peptide, and data processing means comprising (a) means for calculating, for each of a plurality of fragmentation routes (f) which together represent the possible ways that a trial amino acid sequence (S) will fragment, (i) the probability ? (D given f) of the fragmentation mass spectrum (D), assuming a particular fragmentation route (f’, and (ii) the probability P (f given S) of having the fragmentation route (f) from each of said trial sequences (S); (b) means for calculating a likelihood factor P (D given S) that each trial sequence (S_; is the true amino acid sequence of said protein or peptide by summing probabilistically over said plurality of fragmentation routes, such that : P(D given S) -- 5 P(D given f).P(f given S), whereby the most probable amino acid sequence(s) of said protein or peptide corresponds to said trial amino acid sequence(s) (S) having the highest likelihood factor(s).

An embodiment of the apparatus comprises a mass spectrometer for generating a mass spectrum of a said unknown peptide and data processing means programmed tc:

a) process data generated by said mass spectrometer to produce a processable mass spectrum; and

b) calculate the likelihood that any given trial amino-acid sequence would account for said processable spectrum using a fragmentation model which sums probabilistically over a plurality of fragmentation routes which together represent the possible ways that said trial sequence might fragment in accordance with a set of predefined rules, each said

CA 02303758 2003-05-28

20208-1777

8a fragmentation route being assigned a prior probability appropriate to the chemical processes involved.

In preferred embodiments, the apparatus comprises a tandem mass spectrometer, and most preferably a tandem mass spectrometer that comprises a Time-of-Flight mass analyzer at least as its final stage. A Time-of-FLight mass analyzer is preferred because it is generally capable of greater mass measurement accuracy than a quadrupole analyzer. Preferably also the mass spectrometer comprises an electrospray ionization source into which an unknown peptide sample may be introduced.

Embodiments of the invention will now be described in greater detail by reference to the figures, wherein:

Figure 1 is a schematic drawing of a tandem TOF mass spectrometer suitable for generating a mass spectrum from an unknown peptide sample; and

Figure 2 is a flow chart representing the operation of a method according to an embodiment of the invention.

Referring first to figure 1, the principal components of a tandem tcme-of-f1ight mass spectrometer suitable for carrying out methods according to the invention are shown in schematic form. An unknown peptide sample, or a mixture of such samples, is introduced into a capillary 17 comprised in an electrospray ion source generally indicated by 1. A jet 18 comprising ions characteristic of said peptide is generated in the source 1, and at least some these ions pass through an aperture in a sampling cone 2 into a first evacuated chamber 3. From the chamber 3 the ions pass through an aperture in a skimmer cone 4

CA 02303758 2000-04-06 into a second evacuated chamber 5, and are then transported by means of a hexapole ion guide 6 into a quadrupole mass analyzer 7 disposed in a third evacuated chamber 8.

In a spectrometer of the kind illustrated in figure 1, the molecular weight of the peptide may be determined by using the mass analyzer 7 in a non mass-selective mode while a mass spectrum of the sample is acquired. Preferably, the molecular weight is determined to within ± 0.5 daltons.

In order to record a fragmentation spectrum of an unknown peptide, the mass analyzer 7 may be set to transmit only the molecular ions of the unknown peptide (or a selected one of several peptides, if more than one is present in the sample). Molecular ions of the unknown peptide then pass from the mass analyzer 7 into a hexapole collision cell 9 which contains a collision gas (typically helium or argon) at a pressure between 10‘³ and 10’² torr and are fragmented to produce fragment ions which are indicative of the sequence of the unknown peptide. Typically, these fragment ions include ions formed by various losses of the amino acid residues from both the C and N termini of the peptide molecule, as discussed in more detail below.

The fragment ions formed in the collision cell 9 pass into a time-of-flight mass analyzer generally indicated by 10 via an electrostatic lens 11. In the time-of-flight analyzer 10, the ions are received by an ion-pusher 12 which causes bunches of ions to travel through a drift region 13 from the pusher to an ion-reflector 14, then back to an ion detector 15, as shown in figure 1. The mass of the ions is then determined by measuring the time taken for them to reach the detector 15 relative to the time they were ejected from the ionpusher 12. A data acquisition system 16 controls this process and is programmed to carry out a method of the invention as discussed below. The mass range of the entire spectrometer should be at least 2500 daltons and it should preferably be capable of determining the masses of the fragment ions to at least ± 0.5, and preferably ± 0.05 daltons. A suitable mass spectrometer is obtainable from Micromass UK Ltd as the “QTof”.

Referring next to Figure 2, a preferred method according to the invention begins by acquiring fragmentation mass spectrum of the unknown, peptide using the tandem mass spectrometer of Figure 1.

The fragmentation spectrum is in practice complicated by the occurrence of multiplycharged ions and isotopic clusters (that is, several peaks associated with a single ion of a

CA 02303758 2003-05-28

20208-1777 particular nominal mass consequent upon the natural abundance of different carbon, hydrogen, oxygen, nitrogen, and sulphur isotopes comprised in the ion). The method is therefore facilitated by conversion of the raw fragmentation spectrum to a processable spectrum. In such a spectrum, the multiplycharged ions may be converted to a corresponding singly charged ion at the appropriate nominal mass and the minor peaks comprised in each isotopic cluster are subsumed into the main peak representing the parent isotopic variant (i.e. that

IC comprising ¹²C, ^lbO, ¹⁵N, ^kH, ^3z:S). The program MaxEnt3™ available from Micromass UK Ltd. may be used for this purpose, but other software capable of these operations may be employed.

It is also preferable to represent each peak in the processable mass spectrum as a single nominal mass value together with an uncertainty value, for example 512.30 ± 0.05 daltons, rather than as a series of real data points forming an approximately Gaussian peak as it would appear in the raw spectrum. The program MaxEnt3™ also carries out this conversion, but any suitable peak recognition software could be

2C employed. However, it has been found that the fidelity of the final most probable sequences predicted by methods according to the invention is strongly dependent on the range of the masses assigned to the constituent peaks in the processable mass spectrum. Consequently, both the calibration of the mass scale of the tandem mass spectrometer and tne conversion of the raw peaks to their normal masses and their uncertainties must be carried out carefully and rigorously. It has been found that the intensities of the peaks in the fragmentation spectrum have little value in predicting the sequence of an unknown peptide.

Instead of intensities, therefore, the peak recognition software should calculate a probability that each peak actually has been detected in the fragmentaotion spectrum, rather than

CA 02303758 2003-05-28

20208-1777

10a being due to noise or an interfering background. The program MaxEnt3™ is also capable of this operation.

Once a processable spectrum has been produced from the sample protein or peptide, trial sequences may be generated 5 pseudo-randomly in the case of a de novo sequencing method or randomly or pseudo randomly selected from a library or database of protein sequences. Typically, these randomly generated or selected sequences may be constrained by the molecular weight of the peptide; when that has been determined. In the case of sequences comprised in a database, partial sequences having the requisite molecular weight may be extracted from longer sequences in the database. According co the invention, the likelihood of each trial sequence accounting for the processable spectrum is calculated using a fragmentation model which sums probabilistically over all

CA 02303758 2000-04-06 the ways in which a trial sequence might fragment and give rise to peaks in the processable mass spectrum. This model should incorporate as much chemical knowledge concerning the fragmentation of peptides in the tandem mass spectrometer as is available at the time it is constructed. A preferred model incorporates the production of the following series of ions.-

a) The b series, (ions representing the N-terminal amino acid residues and the loss of Cterminal amino acid residues);

b) The y series, (ions representing the C-terminal amino acid residues and the loss of N-terminal amino acid residues);

c) The a series, (Z» ions which have lost CO); and

d) z series, {yions which have lost NH₃) ;

e) more general loss of NH₃ or H₂O.

The two main series of ions (yand b ) are represented in the preferred fragmentation model by Markov Chains, one for each series. In each chain, the probability that a particular ion is observed is dependent on the probability of its predecessor. For example, principally because of charge location, the observed y” ions in a fragmentation spectrum tend to form a coherent series starting with y_t and usually continuing for some way with j,, y₃......, perhaps fading out for a time but likely appearing again towards y_n_, and finally the full molecule. A Markov chain models this behaviour by setting up the probability (PJofj ions being present as a recurrence relation:PM = Pi

P(y_r)= p_rP(y_r-i)+^(¹ - P(y_r-i)) for r = 2,3,4,...,« where P(y) is the probability of y_r being present and the probability oty_r being absent is 1-P(y_r). The coefficients p and q are transition probabilities that determine how likely the series is to begin, to end, and to (re-)start. A similar Markov chain may be set up to represent the b ions.

This is illustrated in Figure 2 (in which represents “not present”). Here the y” series starts with y_t , which has probability p, of being present and hence probability 1 - p_x of not being present. Similarly the b series starts with b_x, which has its probability p, of being present. The numerical values of these and other probabilities depend on the

CA 02303758 2000-04-06 chemistry involved: in fact p_} for the b series can be set at or near zero, to incorporate the observation that the b_A ion is usually absent. If the y_} ion is present, it induces y₂with probability p₂, and if not, y₂ is induced with probability q₂, as shown on the rightward arrows in Figure 2. The fact that presence of y₂ would usually follow from presence of , and conversely, is coded by setting p₂ > f and q₂ < |.

This correlated structure, known as a Markov chain, is continued from y₂ to y₂ and similarly up to y_n. Another such chain defines the b series. Note that all combinatoric patterns of presence or absence occur in the model, although the transition probabilities are usually assigned so as to favour correlated presences and absences. Transition probabilities can be set according to the charge affinity of the residues, allied to physical bond strengths. For example, a y series is likely to be present at and after a proline residue, so that p_T and q_r would be assigned higher values if the residue r were proline than if it were another residue.

The primary Markov chains are supplemented by introducing probabilities that the b series ions may also suffer loss of CO to form ions in the a series, and that y series ions can lose NH₃ to form z” series ions and there may be more general loss of NH₃ or H₂O. Each possible process is assigned a probability which depends on the chemistry involved, for example, the probability of water loss increases with the number of hydroxyl groups on the fragments side chains and would be zero if there are no such hydroxyl groups that could be lost. The fragmentation model also allows for the formation of internal sequences starting at any residue, according to a probability appropriate for that particular residue. Internal sequences are often observed starting at proline residues, so that the probability of one starting at a proline residue is therefore set high. Figure 2 also illustrates these extensions.

The formation of Immonium ions (which are equivalent to the loss of CO and H from a single residue) is also incorporated in the fragmentation model. Only certain residues can generate these ions, and for those that do, appropriate probabilities are set. For example, histidine residues generally result in the formation of an immonium ion at mass 110.072 daltons, and the probability of this process is therefore set close to 100%.

CA 02303758 2000-04-06

It will be appreciated that the more realistic is the fragmentation model the faster and more faithful will be the inference of the sequence of the unknown peptide. Consequently, as the understanding of the chemical processes involved in the formation of the fragmentation spectra of peptides advances, it is within the scope of the invention to adjust the fragmentation model accordingly.

The fragmentation model is explicitly probabilistic, meaning that it produces a probability distribution over all the ways that a trial sequence might fragment (based on the fragmentation model) rather than a list of possible masses in a predicted spectrum. Thus, the likelihood factor is computed as the sum over all these many fragmentation possibilities, so that the fragmentation pattern for a trial sequence is automatically and individually adapted to the data comprised in the processable spectrum. In terms of probability theory, the likelihood factor of the processable spectrum!), given a particular trial sequence S is

P(£> GIVEN S') = ΣΡ (D GIVEN/) P{f GIVENS) f

where £ represents the sum over all the permitted fragmentation patterns f, f

P(D GIVEN f) is the probability of the processable spectrum assuming the particular fragmentation pattern f, andP(/ GIVENS) is the probability of having fragmentation f from the trial sequence S. P(Z) GIVEN /) is evaluated as the product over all the fragment masses of the probabilities that the individual fragment masses are present in the processable mass spectrum. As explained, this sum can be computed in polynomial time rather than in a time proportional to the exponentially large number of fragmentation patterns themselves.

Further, methods according to the invention calculate not only a meaningful probability figure for any given trial sequence, but also the probability of the assignment of each peak in the processable spectrum to a given amino acid residue loss. This quantifies confidence in the identification of the peptide and indicates the regions in a sequence about which some doubt may exist if a single match of very high probability cannot be achieved.