Bioinformatics Advance Access originally published online on September 28, 2004
Bioinformatics 2005 21(5):563-574; doi:10.1093/bioinformatics/bti044
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
A graph-theoretic approach for the separation of b and y ions in tandem mass spectra
1 Computational Systems Biology Laboratory, Department of Biochemical and Molecular Biology, University of Georgia Athens, GA 30602, USA
2 Computational Biology Institute, University of Tennessee Oak Ridge, TN 37831, USA
3 Genome Science and Technology Graduate School, University of Tennessee Oak Ridge, TN 37831, USA
4 Organic and Biological Mass Spectrometry Group, Chemical Sciences Division, Oak Ridge National Laboratory Oak Ridge, TN 37831, USA
*To whom correspondence should be addressed.
Motivation: Ion-type identification is a fundamental problem in computational proteomics. Methods for accurate identification of ion types provide the basis for many mass spectrometry data interpretation problems, including (a) de novo sequencing, (b) identification of post-translational modifications and mutations and (c) validation of database search results.
Results: Here, we present a novel graph-theoretic approach for solving the problem of separating b ions from y ions in a set of tandem mass spectra. We represent each spectral peak as a node and consider two types of edges: type-1 edge connecting two peaks probably of the same ion types and type-2 edge connecting two peaks probably of different ion types. The problem of ion-separation is formulated and solved as a graph partition problem, which is to partition the graph into three subgraphs, representing b, y and others ions, respectively, through maximizing the total weight of type-1 edges while minimizing the total weight of type-2 edges within each partitioned subgraph. We have developed a dynamic programming algorithm for rigorously solving this graph partition problem and implemented it as a computer program PRIME (PaRtition of Ion types in tandem Mass spEctra). The tests on a large amount of simulated mass spectra and 19 sets of high-quality experimental Fourier transform ion cyclotron resonance tandem mass spectra indicate that an accuracy level of 
90% for the separation of b and y ions was achieved.
Availability: The executable code of PRIME is available upon request.
Contact: xyn{at}bmb.uga.edu
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  B.-J. M. Webb-Robertson and W. R. Cannon Current trends in computational inference from mass spectrometry-based proteomics Brief Bioinform, September 1, 2007; 8(5): 304 - 317. [Abstract] [Full Text] [PDF]
|
|