{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,9]],"date-time":"2025-12-09T11:28:35Z","timestamp":1765279715716},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"S1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2011,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>Determining the disulfide (S-S) bond pattern in a protein is often crucial for understanding its structure and function. In recent research, mass spectrometry (MS) based analysis has been applied to this problem following protein digestion under both partial reduction and non-reduction conditions. However, this paradigm still awaits solutions to certain algorithmic problems fundamental amongst which is the efficient matching of an exponentially growing set of putative S-S bonded structural alternatives to the large amounts of experimental spectrometric data. Current methods circumvent this challenge primarily through simplifications, such as by assuming only the occurrence of certain ion-types (<jats:italic>b<\/jats:italic>-ions and <jats:italic>y<\/jats:italic>-ions) that predominate in the more popular dissociation methods, such as collision-induced dissociation (<jats:italic>CID<\/jats:italic>). Unfortunately, this can adversely impact the quality of results.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Method<\/jats:title>\n            <jats:p>We present an algorithmic approach to this problem that can, with high computational efficiency, analyze multiple ions types (<jats:italic>a<\/jats:italic>, <jats:italic>b<\/jats:italic>, <jats:italic>b<\/jats:italic>\n              <jats:sup>\n                <jats:italic>o<\/jats:italic>\n              <\/jats:sup>\n              <jats:italic>, b<\/jats:italic>\n              <jats:sup>\n                <jats:italic>*<\/jats:italic>\n              <\/jats:sup>\n              <jats:italic>, c<\/jats:italic>, <jats:italic>x<\/jats:italic>, <jats:italic>y, y<\/jats:italic>\n              <jats:sup>\n                <jats:italic>o<\/jats:italic>\n              <\/jats:sup>\n              <jats:italic>, y<\/jats:italic>\n              <jats:sup>\n                <jats:italic>*<\/jats:italic>\n              <\/jats:sup>\n              <jats:italic>,<\/jats:italic> and <jats:italic>z<\/jats:italic>) and deal with complex bonding topologies, such as inter\/intra bonding involving more than two peptides. The proposed approach combines an approximation algorithm-based search formulation with data driven parameter estimation. This formulation considers only those regions of the search space where the correct solution resides with a high likelihood. Putative disulfide bonds thus obtained are finally combined in a globally consistent pattern to yield the overall disulfide bonding topology of the molecule. Additionally, each bond is associated with a confidence score, which aids in interpretation and assimilation of the results.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>The method was tested on nine different eukaryotic Glycosyltransferases possessing disulfide bonding topologies of varying complexity. Its performance was found to be characterized by high efficiency (in terms of time and the fraction of search space considered), sensitivity, specificity, and accuracy. The method was also compared with other techniques at the state-of-the-art. It was found to perform as well or better than the competing techniques. An implementation is available at: <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"http:\/\/tintin.sfsu.edu\/~whemurad\/disulfidebond\" ext-link-type=\"uri\">http:\/\/tintin.sfsu.edu\/~whemurad\/disulfidebond<\/jats:ext-link>.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusions<\/jats:title>\n            <jats:p>This research addresses some of the significant challenges in MS-based disulfide bond determination. To the best of our knowledge, this is the first algorithmic work that can consider multiple ion types in this problem setting while simultaneously ensuring polynomial time complexity and high accuracy of results.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1471-2105-12-s1-s12","type":"journal-article","created":{"date-parts":[[2011,2,18]],"date-time":"2011-02-18T20:12:08Z","timestamp":1298059928000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["An efficient algorithmic approach for mass spectrometry-based disulfide connectivity determination using multi-ion analysis"],"prefix":"10.1186","volume":"12","author":[{"given":"William","family":"Murad","sequence":"first","affiliation":[]},{"given":"Rahul","family":"Singh","sequence":"additional","affiliation":[]},{"given":"Ten-Yang","family":"Yen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,2,15]]},"reference":[{"issue":"2","key":"4370_CR1","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1093\/bfgp\/eln008","volume":"7","author":"R Singh","year":"2008","unstructured":"Singh R: A review of algorithmic techniques for disulfide-bond determination. Brief Funct Genomic Proteomic 2008, 7(2):157\u2013172.","journal-title":"Brief Funct Genomic Proteomic"},{"issue":"10","key":"4370_CR2","doi-asserted-by":"publisher","first-page":"787","DOI":"10.1038\/nmeth1088","volume":"4","author":"AI Nesvizhskii","year":"2007","unstructured":"Nesvizhskii AI, Vitek O, Aebersold R: Analysis and validation of proteomic data generated by tandem mass spectrometry. Nat Methods 2007, 4(10):787\u2013797.","journal-title":"Nat Methods"},{"key":"4370_CR3","first-page":"140","volume-title":"Proc, BIRD","author":"T Lee","year":"2008","unstructured":"Lee T, Singh R: Comparative Analysis of Disulfide Bond Determination Using Computational-Predictive Methods and Mass Spectrometry-Based Algorithmic Approach. In Proc, BIRD. CCIS 13; 2008:140\u2013153."},{"key":"4370_CR4","doi-asserted-by":"publisher","first-page":"699","DOI":"10.1038\/nrm1468","volume":"5","author":"H Steen","year":"2004","unstructured":"Steen H, Mann M: The abc\u2019s (and xyz\u2019s) of peptide sequencing. Nat Rev Mol Cell Biol 2004, 5: 699\u2013711.","journal-title":"Nat Rev Mol Cell Biol"},{"key":"4370_CR5","doi-asserted-by":"publisher","first-page":"2621","DOI":"10.1021\/ac00148a019","volume":"59","author":"RS Johnson","year":"1987","unstructured":"Johnson RS, Martin SA, Biemann K, Stults JT, Watson JT: Novel fragmentation process of peptides by collision-induced decomposition in a tandem mass spectrometer: differentiation of leucine and isoleucine. Analytical Chemistry 1987, 59: 2621\u20132625.","journal-title":"Analytical Chemistry"},{"issue":"8","key":"4370_CR6","doi-asserted-by":"publisher","first-page":"834","DOI":"10.1016\/S1044-0305(03)00327-1","volume":"14","author":"B Schilling","year":"2003","unstructured":"Schilling B, et al.: MS2Assign, automated assignment and nomenclature of tandem mass spectra of chemically crosslinked peptides. J Am Soc Mass Spectrom 2003, 14(8):834\u2013850.","journal-title":"J Am Soc Mass Spectrom"},{"key":"4370_CR7","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1021\/pr070363z","volume":"7","author":"H Xu","year":"2008","unstructured":"Xu H, Zhang L, Freitas MA: Identification and Characterization of Disulfide Bonds in Proteins and Peptides from Tandem MS Data by Use of the MassMatrix MS\/MS Search Engine. J Proteome Res 2008, 7: 138\u2013144.","journal-title":"J Proteome Res"},{"key":"4370_CR8","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1186\/1471-2105-8-133","volume":"8","author":"H Xu","year":"2007","unstructured":"Xu H, Freitas MA: A mass accuracy sensitive probability based scoring algorithm for database searching of tandem mass spectrometry data. BMC Bionformatics 2007, 8: 133.","journal-title":"BMC Bionformatics"},{"issue":"20","key":"4370_CR9","doi-asserted-by":"publisher","first-page":"5383","DOI":"10.1021\/ac025747h","volume":"74","author":"A Keller","year":"2002","unstructured":"Keller A, Nesvizhskii AI, Kolker E, Aebersold R: Empirical statistical model to estimate the accuracy of peptide identification made by MS\/MS database search. Analytical Chemistry 2002, 74(20):5383\u20135392.","journal-title":"Analytical Chemistry"},{"key":"4370_CR10","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1145\/369133.369177","volume-title":"Proc RECOMB","author":"T Chen","year":"2001","unstructured":"Chen T, Jaffe JD, Church GM: Algorithms for Identifying Protein Cross-links via Tandem Mass Spectrometry. Proc RECOMB 2001, 95\u2013102."},{"key":"4370_CR11","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1142\/9781860948732_0009","volume-title":"Proc. Computational Systems Bioinformatics, CSB","author":"T Lee","year":"2007","unstructured":"Lee T, Singh R, Yen TY, Macher B: An Algorithmic approach to Automated High-Throughput Identification of Disulfide Connectivity in Proteins Using Tandem Mass Spectrometry. Proc. Computational Systems Bioinformatics, CSB 2007, 41\u201351."},{"key":"4370_CR12","first-page":"397","volume-title":"Proc. IEEE International Symposiumon Computer-Based Medical Systems, CBMS","author":"T Lee","year":"2007","unstructured":"Lee T, Singh R, Yen R, Macher B: A mass-based hashing algorithm for the identification of disulfide linkage patterns in protein utilizing mass spectrometry data. Proc. IEEE International Symposiumon Computer-Based Medical Systems, CBMS 2007, 397\u2013402."},{"key":"4370_CR13","first-page":"79","volume-title":"Proc. IEEE Computational Structural Bioinformatics Workshop, CSBW","author":"W Murad","year":"2009","unstructured":"Murad W, Singh R, Yen TY: Polynomial-Time Disulfide Bond Determination Using Mass Spectrometry Data. Proc. IEEE Computational Structural Bioinformatics Workshop, CSBW 2009, 79\u201386."},{"key":"4370_CR14","doi-asserted-by":"publisher","first-page":"957","DOI":"10.1093\/bioinformatics\/17.10.957","volume":"17","author":"P Fariselli","year":"2001","unstructured":"Fariselli P, Casadio R: Prediction of disulfide connectivity in proteins. Bioinformatics 2001, 17: 957\u201364.","journal-title":"Bioinformatics"},{"key":"4370_CR15","first-page":"26","volume-title":"Proc. RECOMB","author":"A Frank","year":"2005","unstructured":"Frank A, Tanner S, Pevzner P: Peptide Sequence Tags for Fast Database Search in Mass-Spectrometry. In Proc. RECOMB. LNBI 3500; 2005:26\u2013341."},{"key":"4370_CR16","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2005","unstructured":"Cormen TH, Leiserson CE, Rivest RL, Stein C: Introduction to Algorithms. 2nd edition. MIT Press, Cambridge, MA, U.S.A; 2005.","edition":"2nd"},{"key":"4370_CR17","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1145\/321941.321942","volume":"23","author":"HN Gabow","year":"2006","unstructured":"Gabow HN: An efficient implementation of Edmonds\u2019 Algorithm for Maximum Matching on Graphs. Journal of the ACM 2006, 23: 221\u2013234.","journal-title":"Journal of the ACM"},{"key":"4370_CR18","unstructured":"Rothberg E: MATHPROG: Solver for the maximum weight matching problem.[http:\/\/elib.zib.de\/pub\/Packages\/mathprog\/matching\/weighted\/]"},{"key":"4370_CR19","first-page":"4G","volume":"12","author":"S Thomas","year":"2002","unstructured":"Thomas S, Yen TY, Macher BA: Eukaryotic glycosyltransferases: cysteines and disulfides. Glycobiology 2002, 12: 4G-7G.","journal-title":"Glycobiology"},{"key":"4370_CR20","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/S0076-6879(06)15007-7","volume":"415","author":"TY Yen","year":"2006","unstructured":"Yen TY, Macher BA: Determination of glycosylation sites and disulfide bond structures using LC\/ESI-MS\/MS analysis. Methods in enzymology 2006, 415: 103\u2013113.","journal-title":"Methods in enzymology"},{"issue":"Web Server issu","key":"4370_CR21","doi-asserted-by":"publisher","first-page":"W230","DOI":"10.1093\/nar\/gki412","volume":"33","author":"F Ferre","year":"2005","unstructured":"Ferre F, Clote P: DiANNA: A Web Server for Disulfide Connectivity Prediction. Nucleic Acids Res 2005, 33(Web Server issue):W230-W232.","journal-title":"Nucleic Acids Res"},{"issue":"Web Server issu","key":"4370_CR22","doi-asserted-by":"publisher","first-page":"W177","DOI":"10.1093\/nar\/gkl266","volume":"34","author":"A Ceroni","year":"2006","unstructured":"Ceroni A, et al.: DISULFIND: A Disulfide Bonding State and Cysteine Connectivity Prediction Server. Nucleic Acids Res 2006, 34(Web Server issue):W177-W181.","journal-title":"Nucleic Acids Res"},{"key":"4370_CR23","doi-asserted-by":"publisher","first-page":"4416","DOI":"10.1093\/bioinformatics\/bti715","volume":"21","author":"CH Tsai","year":"2005","unstructured":"Tsai CH, et al.: Improving disulfide connectivity prediction with sequential distance between oxidized cysteines. Bioinformatics 2005, 21: 4416\u20134419.","journal-title":"Bioinformatics"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-12-S1-S12.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T13:46:36Z","timestamp":1630503996000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-12-S1-S12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,2,15]]},"references-count":23,"journal-issue":{"issue":"S1","published-print":{"date-parts":[[2011,12]]}},"alternative-id":["4370"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-12-s1-s12","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,2,15]]},"assertion":[{"value":"15 February 2011","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"S12"}}