Preparing peptide spectra for identification

• US 20060208185A1
• Filed: 03/18/2005
• Published: 09/21/2006
• Est. Priority Date: 03/18/2005
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Gofman, Emanuel, Barnea, Eilon, Be'er, Ilan
• Granted Patent: US 7,512,524 B2
• Time in Patent Office: Days
• US Class Current: 250/282
• CPC Class Codes: G01N 33/6848 Methods of protein analysis involving mass spectrometry
• CPC Class Codes: H01J 49/04 Arrangements for introducing or extracting samples to be analysed, e.g. vacuum locks; Arrangements for external adjustment of electron- or ion-optical components

Abstract

A method for preparing peptide spectra for identification, the method including constructing a symmetric distance matrix from a plurality of peptide spectra, where a cluster of at least one of the spectra is represented in a row of the matrix, and where the cluster is also represented in a column of the matrix, finding the minimum of each of the clusters in the matrix, constructing a vector from the minima where each element in the vector corresponds to one of the clusters, finding the global minimum of the matrix as being the minimum of the vector, merging two of the clusters identified by the global minimum into a merged cluster, and providing the merged cluster for identification of at least one peptide associated with the merged cluster.

Claims

1. A method for preparing peptide spectra for identification, the method comprising:

a) constructing a symmetric distance matrix from a plurality of peptide spectra, wherein a cluster of at least one of said spectra is represented in a row of said matrix, and wherein said cluster is also represented in a column of said matrix;

b) finding the minimum of each of said clusters in said matrix;

c) constructing a vector from said minima wherein each element in said vector corresponds to one of said clusters;

d) finding the global minimum of said matrix as being the minimum of said vector;

e) merging two of said clusters identified by said global minimum into a merged cluster; and

f) providing said merged cluster for identification of at least one peptide associated with said merged cluster.

2. A method according to claim 1 and further comprising:

g) finding the minimum of any of said clusters in said matrix where said distance between said cluster and either of said merged clusters was the smallest relative to the distance between said cluster and any other of said clusters; and

h) updating any of said elements in said vector for which a minimum was found in step g) for said cluster corresponding to said element.

3. A method according to claim 1 wherein said finding step d) comprises:

ordering said elements in said vector in hierarchical order; and

identifying the root of said hierarchy as said global minimum.

4. A method according to claim 3 and further comprising:

g) finding the minimum of any of said clusters in said matrix where said distance between said cluster and either of said merged clusters was the smallest relative to the distance between said cluster and any other of said clusters;

h) updating any of said elements in said vector for which a minimum was found in step g) for said cluster corresponding to said element; and

i) reordering said updated elements in said vector in hierarchical order.

5. A method according to claim 1 wherein each of said vector elements is associated with an index of any of said clusters for which said minimum was found with respect to said cluster to which said vector element corresponds.

6. A method according to claim 1 wherein said constructing step comprises:

representing said plurality of peptide spectra as a set of multidimensional vectors;

ordering said multidimensional vectors;

determining the closeness between any two of said ordered vectors in accordance with a measure of closeness;

determining the distance between any two of said ordered vectors using a distance function where said vectors are close to each other in accordance with said measure of closeness; and

constructing said matrix from said distances.

7. A method according to claim 6 wherein said ordering step comprises ordering said vectors according to their precursor (parent) mass (PM) of their associated peptide.

8. A method according to claim 7 wherein said determining closeness step comprises determining that said two vectors are close where their masses are within 2 Daltons of each other.

9. A method for constructing a sparse distance matrix of peptide spectra, the method comprising:

representing a plurality of peptide spectra as a set of multidimensional vectors;

ordering said vectors;

determining the closeness between any two of said ordered vectors in accordance with a measure of closeness;

determining the distance between any two of said ordered vectors using a distance function where said vectors are close to each other in accordance with said measure of closeness; and

constructing a matrix from said distances.

10. A method according to claim 9 wherein said ordering step comprises ordering said vectors according to their precursor (parent) mass (PM) of their associated peptide.

11. A method according to claim 10 wherein said determining closeness step comprises determining that said two vectors are close where their masses are within 2 Daltons of each other.

12. A system for preparing peptide spectra for identification, the system comprising:

a) means for constructing a symmetric distance matrix from a plurality of peptide spectra, wherein a cluster of at least one of said spectra is represented in a row of said matrix, and wherein said cluster is also represented in a column of said matrix;

b) means for finding the minimum of each of said clusters in said matrix;

c) means for constructing a vector from said minima wherein each element in said vector corresponds to one of said clusters;

d) means for finding the global minimum of said matrix as being the minimum of said vector;

e) means for merging two of said clusters identified by said global minimum into a merged cluster; and

f) means for providing said merged cluster for identification of at least one peptide associated with said merged cluster.

13. A system according to claim 12 and further comprising:

g) means for finding the minimum of any of said clusters in said matrix where said distance between said cluster and either of said merged clusters was the smallest relative to the distance between said cluster and any other of said clusters; and

h) means for updating any of said elements in said vector for which a minimum was found in step g) for said cluster corresponding to said element.

14. A system according to claim 12 wherein said means for finding d) is operative to:

order said elements in said vector in hierarchical order; and

identify the root of said hierarchy as said global minimum.

15. A system according to claim 14 and further comprising:

g) means for finding the minimum of any of said clusters in said matrix where said distance between said cluster and either of said merged clusters was the smallest relative to the distance between said cluster and any other of said clusters;

h) means for updating any of said elements in said vector for which a minimum was found in step g) for said cluster corresponding to said element; and

i) means for reordering said updated elements in said vector in hierarchical order.

16. A system according to claim 12 wherein each of said vector elements is associated with an index of any of said clusters for which said minimum was found with respect to said cluster to which said vector element corresponds.

17. A system according to claim 12 wherein said means for constructing is operative to:

represent said plurality of peptide spectra as a set of multidimensional vectors;

order said multidimensional vectors;

determine the closeness between any two of said ordered vectors in accordance with a measure of closeness;

determine the distance between any two of said ordered vectors using a distance function where said vectors are close to each other in accordance with said measure of closeness; and

construct said matrix from said distances.

18. A system according to claim 17 wherein said means for ordering is operative to order said vectors according to their precursor (parent) mass (PM) of their associated peptide.

19. A system according to claim 18 wherein said means for determining closeness is operative to determine that said two vectors are close where their masses are within 2 Daltons of each other.

20. A system for constructing a sparse distance matrix of peptide spectra, the system comprising:

means for representing a plurality of peptide spectra as a set of multidimensional vectors;

means for ordering said vectors;

means for determining the closeness between any two of said ordered vectors in accordance with a measure of closeness;

means for determining the distance between any two of said ordered vectors using a distance function where said vectors are close to each other in accordance with said measure of closeness; and

means for constructing a matrix from said distances.

21. A system according to claim 20 wherein said means for ordering is operative to order said vectors according to their precursor (parent) mass (PM) of their associated peptide.

22. A system according to claim 21 wherein said means for determining closeness is operative to determine that said two vectors are close where their masses are within 2 Daltons of each other.

23. A computer-implemented program embodied on a computer-readable medium, the computer program comprising:

a first code segment operative to construct a symmetric distance matrix from a plurality of peptide spectra, wherein a cluster of at least one of said spectra is represented in a row of said matrix, and wherein said cluster is also represented in a column of said matrix;

a second code segment operative to find the minimum of each of said clusters in said matrix;

a third code segment operative to construct a vector from said minima wherein each element in said vector corresponds to one of said clusters;

a fourth code segment operative to find the global minimum of said matrix as being the minimum of said vector;

a fifth code segment operative to merge two of said clusters identified by said global minimum into a merged cluster; and

a sixth code segment operative to provide said merged cluster for identification of at least one peptide associated with said merged cluster.