Separation of ion types in tandem mass spectrometry data interpretation -- a graph-theoretic approach.
Mass spectrometry is one of the most popular analytical techniques for identification of individual proteins in a protein mixture, one of the basic problems in proteomics. It identifies a protein through identifying its unique mass spectral pattern. While the problem is theoretically solvable, it remains a challenging problem computationally. One of the key challenges comes from the difficulty in distinguishing the N- and C-terminus ions, mostly b- and y-ions respectively. In this paper, we present a graph algorithm for solving the problem of separating bfrom y-ions in a set of mass spectra. We represent each spectral peak as a node and consider two types of edges: a type-1 edge connects two peaks possibly of the same ion types and a type-2 edge connects two peaks possibly of different ion types, predicted based on local information. The ion-separation problem is then formulated and solved as a graph partition problem, which is to partition the graph into three subgraphs, namely b-, y-ions and others respectively, so to maximize the total weight of type-1 edges while minimizing the total weight of type-2 edges within each subgraph. We have developed a dynamic programming algorithm for rigorously solving this graph partition problem and implemented it as a computer program PRIME. We have tested PRIME on 18 data sets of high accurate FT-ICR tandem mass spectra and found that it achieved ~90% accuracy for separation of b- and y- ions.
Yan
Bo
B
Department of Biochemical and Molecular Biology, University of Georgia, USA.
Pan
Chongle
C
Olman
Victor N
VN
Hettich
Robert L
RL
Xu
Ying
Y
D000465:Algorithms; D003198:Computer Simulation; D020869:Gene Expression Profiling / Q000379:methods*; D007477:Ions; D013058:Mass Spectrometry / Q000379:methods*; D008956:Models, Chemical; D010449:Peptide Mapping / Q000379:methods*; D011506:Proteins / Q000032:analysis* / Q000737:chemistry* / Q000145:classification; D016415:Sequence Alignment / Q000379:methods; D020539:Sequence Analysis, Protein / Q000379:methods*
D007477:Ions; D011506:Proteins