Separation of ion types in tandem mass spectrometry data interpretation - A graph-theoretic approach

Bo Yan, Chongle Pan, Victor N. Olman, Robert L. Hettich, Ying Xu

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

4 Scopus citations

Abstract

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 b-from 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.

Original languageEnglish
Title of host publicationProceedings - 2004 IEEE Computational Systems Bioinformatics Conference, CSB 2004
PublisherIEEE Computer Society
Pages236-244
Number of pages9
ISBN (Print)0769521940, 9780769521947
StatePublished - 2004
EventProceedings - 2004 IEEE Computational Systems Bioinformatics Conference, CSB 2004 - Stanford, CA, United States
Duration: Aug 16 2004Aug 19 2004

Publication series

NameProceedings - 2004 IEEE Computational Systems Bioinformatics Conference, CSB 2004

Conference

ConferenceProceedings - 2004 IEEE Computational Systems Bioinformatics Conference, CSB 2004
Country/TerritoryUnited States
CityStanford, CA
Period08/16/0408/19/04

Fingerprint

Dive into the research topics of 'Separation of ion types in tandem mass spectrometry data interpretation - A graph-theoretic approach'. Together they form a unique fingerprint.

Cite this