{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T14:30:09Z","timestamp":1774449009507,"version":"3.50.1"},"reference-count":29,"publisher":"Oxford University Press (OUP)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005,3,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>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.<\/jats:p>\n               <jats:p>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 \u223c90% for the separation of b and y ions was achieved.<\/jats:p>\n               <jats:p>Availability: The executable code of PRIME is available upon request.<\/jats:p>\n               <jats:p>Contact: \u00a0xyn@bmb.uga.edu<\/jats:p>","DOI":"10.1093\/bioinformatics\/bti044","type":"journal-article","created":{"date-parts":[[2004,9,29]],"date-time":"2004-09-29T01:27:46Z","timestamp":1096421266000},"page":"563-574","source":"Crossref","is-referenced-by-count":32,"title":["A graph-theoretic approach for the separation of b and y ions in tandem mass spectra"],"prefix":"10.1093","volume":"21","author":[{"given":"Bo","family":"Yan","sequence":"first","affiliation":[]},{"given":"Chongle","family":"Pan","sequence":"additional","affiliation":[]},{"given":"Victor N.","family":"Olman","sequence":"additional","affiliation":[]},{"given":"Robert L.","family":"Hettich","sequence":"additional","affiliation":[]},{"given":"Ying","family":"Xu","sequence":"additional","affiliation":[]}],"member":"286","published-online":{"date-parts":[[2004,9,28]]},"reference":[{"key":"2023013107213186100_B1","unstructured":"Aebersold, R. and Mann, M. 2003Mass spectrometry-based proteomics. Nature422198\u2013207"},{"key":"2023013107213186100_B2","doi-asserted-by":"crossref","unstructured":"Altschul, S.F., Madden, T.L., Schaffer, A.A., Zhang, J., Zhang, Z., Miller, W., Lipman, D.J. 1997Gapped BLAST and PSI-BLAST: a new generation of protein database search programs. Nucleic Acids Res.253389\u20133402","DOI":"10.1093\/nar\/25.17.3389"},{"key":"2023013107213186100_B3","doi-asserted-by":"crossref","unstructured":"Andersen, J.S., Wilkinson, C.J., Mayor, T., Mortensen, P., Nigg, E.A., Mann, M. 2003Proteomic characterization of the human centrosome by protein correlation profiling. Nature426570\u2013574","DOI":"10.1038\/nature02166"},{"key":"2023013107213186100_B4","unstructured":"Bartels, C. 1990Fast algorithm for peptide sequencing by mass spectroscopy. Biomed. Environ. Mass Spectrom.19363\u2013368"},{"key":"2023013107213186100_B5","doi-asserted-by":"crossref","unstructured":"Boeckmann, B., Bairoch, A., Apweiler, R., Blatter, M.C., Estreicher, A., Gasteiger, E., Martin, M.J., Michoud, K., O\u2019Donovan, C., Phan, I., Pilbout, S., Schneider, M. 2003The SWISS-PROT protein knowledgebase and its supplement TrEMBL in 2003. Nucleic Acids Res.31365\u2013370","DOI":"10.1093\/nar\/gkg095"},{"key":"2023013107213186100_B6","doi-asserted-by":"crossref","unstructured":"Chen, T., Kao, M.Y., Tepel, M., Rush, J., Church, G.M. 2001A dynamic programming approach to de novo peptide sequencing via tandem mass spectrometry. J. Comput. Biol.8325\u2013337","DOI":"10.1089\/10665270152530872"},{"key":"2023013107213186100_B7","doi-asserted-by":"crossref","unstructured":"Clauser, K.R., Baker, P., Burlingame, A.L. 1999Role of accurate mass measurement (+\/\u221210\u2009ppm) in protein identification strategies employing MS or MS\/MS and database searching. Anal. Chem.712871\u20132882","DOI":"10.1021\/ac9810516"},{"key":"2023013107213186100_B8","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C. Introduction to Algorithms2001, Cambridge, MA  The MIT Press"},{"key":"2023013107213186100_B9","doi-asserted-by":"crossref","unstructured":"Dancik, V., Addona, T.A., Clauser, K.R., Vath, J.E., Pevzner, P.A. 1999De novo peptide sequencing via tandem mass spectrometry. J. Comput. Biol.6,  pp. 327\u2013342","DOI":"10.1089\/106652799318300"},{"key":"2023013107213186100_B10","doi-asserted-by":"crossref","unstructured":"Eng, J.K., McCormack, A.L., Yates, J.R., III. 1994An approach to correlate tandem mass spectral data of peptides with amino acid sequences in a protein database. J. Am. Soc. Mass Spectrom.5976\u2013989","DOI":"10.1016\/1044-0305(94)80016-2"},{"key":"2023013107213186100_B11","unstructured":"Fenyo, D. 2000Identifying the proteome: software tools. Curr. Opin. Biotechnol.11391\u2013395"},{"key":"2023013107213186100_B12","doi-asserted-by":"crossref","unstructured":"Fenyo, D., Qin, J., Chait, B.T. 1998Protein identification using mass spectrometric information. Electrophoresis19998\u20131005","DOI":"10.1002\/elps.1150190615"},{"key":"2023013107213186100_B13","doi-asserted-by":"crossref","unstructured":"Gauthier, J.W., Trautman, T.R., Jacobson, D.B. 1991Sustained off-resonance irradiation for collision-activated dissociation involving Fourier transform mass spectrometry. Collision-activated dissociation technique that emulates infrared multiphoton dissociation. Anal. Chim. Acta246211\u2013225","DOI":"10.1016\/S0003-2670(00)80678-9"},{"key":"2023013107213186100_B14","doi-asserted-by":"crossref","unstructured":"Gooley, A.A. and Packer, N.H. 1997The importance of co- and post-translational modifications in proteome projects. In Wilkins, W.R., Williams, K.L., Appel, R.D., Hochstrasser, D.F. (Eds.). Proteome Research: New Frontiers in Functional Genomics , NY  Springer-Verlag,  pp. 65\u201391","DOI":"10.1007\/978-3-662-03493-4_4"},{"key":"2023013107213186100_B15","unstructured":"Ho, Y., Gruhler, A., Heilbut, A., Bader, G.D., Moore, L., Adams, S.L., Millar, A., Taylor, P., Bennett, K., Boutilier, K., et al. 2002Systematic identification of protein complexes in Saccharomyces cerevisiae by mass spectrometry. Nature415180\u2013183"},{"key":"2023013107213186100_B16","doi-asserted-by":"crossref","unstructured":"Lasonder, E., Ishihama, Y., Andersen, J.S., Vermunt, A.M., Pain, A., Sauerwein, R.W., Eling, W.M., Hall, N., Waters, A.P., Stunnenberg, H.G., Mann, M. 2002Analysis of the Plasmodium falciparum proteome by high-accuracy mass spectrometry. Nature419537\u2013542","DOI":"10.1038\/nature01111"},{"key":"2023013107213186100_B17","unstructured":"Lu, B. and Chen, T. 2003A suboptimal algorithm for de novo peptide sequencing via tandem mass spectrometry. J. Comput. Biol.101\u201312"},{"key":"2023013107213186100_B18","doi-asserted-by":"crossref","unstructured":"Ma, B., Zhang, K., Hendrie, C., Liang, C., Li, M., Doherty-Kirby, A., Lajoie, G. 2003PEAKS: powerful software for peptide de novo sequencing by tandem mass spectrometry. Rapid Commun. Mass Spectrom.172337\u20132342","DOI":"10.1002\/rcm.1196"},{"key":"2023013107213186100_B19","doi-asserted-by":"crossref","unstructured":"MacCoss, M.J., McDonald, W.H., Saraf, A., Sadygov, R., Clark, J.M., Tasto, J.J., Gould, K.L., Wolters, D., Washburn, M., Weiss, A., Clark, J.I., Yates, J.R., III. 2002Shotgun identification of protein modifications from protein complexes and lens tissue. Proc. Natl. Acad. Sci. USA997900\u20137905","DOI":"10.1073\/pnas.122231399"},{"key":"2023013107213186100_B20","unstructured":"Mann, M. and Jensen, O.N. 2003Proteomic analysis of post-translational modifications. Nat. Biotechnol.21255\u2013261"},{"key":"2023013107213186100_B21","doi-asserted-by":"crossref","unstructured":"Mann, M. and Wilm, M. 1994Error-tolerant identification of peptides in sequence databases by peptide sequence tags. Anal. Chem.664390\u20134399","DOI":"10.1021\/ac00096a002"},{"key":"2023013107213186100_B22","doi-asserted-by":"crossref","unstructured":"Nesvizhskii, A.I. and Aebersold, R. 2004Analysis, statistical validation and dissemination of large-scale proteomics datasets generated by tandem MS. Drug Discov. Today9173\u2013181","DOI":"10.1016\/S1359-6446(03)02978-7"},{"key":"2023013107213186100_B23","doi-asserted-by":"crossref","unstructured":"Perkins, D.N., Pappin, D.J., Creasy, D.M., Cottrell, J.S. 1999Probability-based protein identification by searching sequence databases using mass spectrometry data. Electrophoresis203551\u20133567","DOI":"10.1002\/(SICI)1522-2683(19991201)20:18<3551::AID-ELPS3551>3.0.CO;2-2"},{"key":"2023013107213186100_B24","unstructured":"Pevzner, P.A., Dancik, V., Tang, C.L. 2000Mutation-tolerant protein identification by mass spectrometry. J. Comput. Biol.7777\u2013787"},{"key":"2023013107213186100_B25","doi-asserted-by":"crossref","unstructured":"Tabb, D.L., Smith, L.L., Breci, L.A., Wysocki, V.H., Lin, D., Yates, J.R., III. 2003Statistical characterization of ion trap tandem mass spectra from doubly charged tryptic peptides. Anal. Chem.751155\u20131163","DOI":"10.1021\/ac026122m"},{"key":"2023013107213186100_B26","doi-asserted-by":"crossref","unstructured":"Taylor, J.A. and Johnson, R.S. 1997Sequence database searches via de novo peptide sequencing by tandem mass spectrometry. Rapid Commun. Mass Spectrom.111067\u20131075","DOI":"10.1002\/(SICI)1097-0231(19970615)11:9<1067::AID-RCM953>3.0.CO;2-L"},{"key":"2023013107213186100_B27","doi-asserted-by":"crossref","unstructured":"Taylor, J.A. and Johnson, R.S. 2001Implementation and uses of automated de novo peptide sequencing by tandem mass spectrometry. Anal. Chem.732594\u20132604","DOI":"10.1021\/ac001196o"},{"key":"2023013107213186100_B28","doi-asserted-by":"crossref","unstructured":"Washburn, M.P., Wolters, D., Yates, J.R., III. 2001Large-scale analysis of the yeast proteome by multidimensional protein identification technology. Nat. Biotechnol.19242\u2013247","DOI":"10.1038\/85686"},{"key":"2023013107213186100_B29","doi-asserted-by":"crossref","unstructured":"Yates, J.R., III, Eng, J.K., McCormack, A.L., Schieltz, D. 1995Method to correlate tandem mass spectra of modified peptides to amino acid sequences in the protein database. Anal. Chem.671426\u20131436","DOI":"10.1021\/ac00104a020"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/21\/5\/563\/48962580\/bioinformatics_21_5_563.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/21\/5\/563\/48962580\/bioinformatics_21_5_563.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T10:01:23Z","timestamp":1675159283000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/21\/5\/563\/220105"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,9,28]]},"references-count":29,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2005,3,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bti044","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2005,3,1]]},"published":{"date-parts":[[2004,9,28]]}}}