{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T10:11:37Z","timestamp":1782900697081,"version":"3.54.5"},"reference-count":29,"publisher":"Oxford University Press (OUP)","issue":"14","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013,7,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Label-free quantification is an important approach to identify biomarkers, as it measures the quantity change of peptides across different biological samples. One of the fundamental steps for label-free quantification is to match the peptide features that are detected in two datasets to each other. Although ad hoc software tools exist for the feature matching, the definition of a combinatorial model for this problem is still not available.<\/jats:p>\n               <jats:p>Results: A combinatorial model is proposed in this article. Each peptide feature contains a mass value and a retention time value, which are used to calculate a matching weight between a pair of features. The feature matching is to find the maximum-weighted matching between the two sets of features, after applying a to-be-computed time alignment function to all the retention time values of one set of the features. This is similar to the maximum matching problem in a bipartite graph. But we show that the requirement of time alignment makes the problem NP-hard. Practical algorithms are also provided. Experiments on real data show that the algorithm compares favorably with other existing methods.<\/jats:p>\n               <jats:p>Contact: \u00a0binma@uwaterloo.ca<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btt274","type":"journal-article","created":{"date-parts":[[2013,5,11]],"date-time":"2013-05-11T01:47:48Z","timestamp":1368236868000},"page":"1768-1775","source":"Crossref","is-referenced-by-count":65,"title":["A combinatorial approach to the peptide feature matching problem for label-free quantification"],"prefix":"10.1093","volume":"29","author":[{"given":"Hao","family":"Lin","sequence":"first","affiliation":[{"name":"David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lin","family":"He","sequence":"additional","affiliation":[{"name":"David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bin","family":"Ma","sequence":"additional","affiliation":[{"name":"David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2013,5,10]]},"reference":[{"key":"2023012810455267900_btt274-B1","first-page":"S20","article-title":"iPRG 2011: a study on the identification of electron transfer dissociation (ETD) mass spectra","volume":"22","author":"Askenazi","year":"2011","journal-title":"J. Biomol. Tech."},{"key":"2023012810455267900_btt274-B2","doi-asserted-by":"crossref","first-page":"1902","DOI":"10.1093\/bioinformatics\/btl276","article-title":"A suite of algorithms for the comprehensive analysis of complex protein mixtures using high-resolution LC-MS","volume":"22","author":"Bellew","year":"2006","journal-title":"Bioinformatics"},{"key":"2023012810455267900_btt274-B3","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/S0021-9673(02)00588-5","article-title":"Chromatographic alignment by warping and dynamic programming as a pre-processing tool for parafac modelling of liquid chromatography\u2013mass spectrometry data","volume":"961","author":"Bylund","year":"2002","journal-title":"J. Chromatogr. A"},{"key":"2023012810455267900_btt274-B4","doi-asserted-by":"crossref","first-page":"1087","DOI":"10.1007\/s00726-012-1289-8","article-title":"Current challenges in software solutions for mass spectrometry-based quantitative proteomics","volume":"43","author":"Cappadona","year":"2012","journal-title":"Amino Acids"},{"key":"2023012810455267900_btt274-B5","volume-title":"Data Analysis and Signal Processing in Chromatography","author":"Felinger","year":"1998"},{"key":"2023012810455267900_btt274-B6","doi-asserted-by":"crossref","first-page":"e132","DOI":"10.1093\/bioinformatics\/btl219","article-title":"Semi-supervised LC\/MS alignment for differential proteomics","volume":"22","author":"Fischer","year":"2006","journal-title":"Bioinformatics"},{"key":"2023012810455267900_btt274-B7","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1145\/28869.28874","article-title":"Fibonacci heaps and their uses in improved network optimization algorithms","volume":"34","author":"Fredman","year":"1987","journal-title":"J. ACM"},{"key":"2023012810455267900_btt274-B8","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1586\/14789450.1.3.317","article-title":"Mass spectrometry-based quantitative proteomics","volume":"1","author":"Heck","year":"2004","journal-title":"Expert Rev. Proteomics"},{"key":"2023012810455267900_btt274-B9","doi-asserted-by":"crossref","first-page":"7397","DOI":"10.1021\/ac052197p","article-title":"Robust algorithm for alignment of liquid chromatography-mass spectrometry analyses in an accurate mass and time tag data analysis pipeline","volume":"78","author":"Jaitly","year":"2006","journal-title":"Anal. Chem."},{"key":"2023012810455267900_btt274-B10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.18637\/jss.v018.i04","article-title":"amsrpm: robust point matching for retention time alignment of LC\/MS data with R","volume":"18","author":"Kirchner","year":"2007","journal-title":"J. Stat. Softw."},{"key":"2023012810455267900_btt274-B11","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1186\/1471-2105-14-49","article-title":"Multialign: a multiple LC-MS analysis tool for targeted omics analysis","volume":"14","author":"LaMarche","year":"2013","journal-title":"BMC bioinformatics"},{"key":"2023012810455267900_btt274-B12","doi-asserted-by":"crossref","first-page":"i273","DOI":"10.1093\/bioinformatics\/btm209","article-title":"A geometric approach for the alignment of liquid chromatography\u2013mass spectrometry data","volume":"23","author":"Lange","year":"2007","journal-title":"Bioinformatics"},{"key":"2023012810455267900_btt274-B13","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1186\/1471-2105-9-375","article-title":"Critical assessment of alignment procedures for LC-MS proteomics and metabolomics measurements","volume":"9","author":"Lange","year":"2008","journal-title":"BMC bioinformatics"},{"key":"2023012810455267900_btt274-B14","doi-asserted-by":"crossref","first-page":"1328","DOI":"10.1074\/mcp.M500141-MCP200","article-title":"A software suite for the generation and comparison of peptide arrays from sets of data collected by liquid chromatography-mass spectrometry","volume":"4","author":"Li","year":"2005","journal-title":"Mol. Cell. Proteomics"},{"key":"2023012810455267900_btt274-B15","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1109\/FOCS.2004.40","article-title":"Maximum matchings via gaussian elimination","volume-title":"Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science","author":"Mucha","year":"2004"},{"key":"2023012810455267900_btt274-B16","doi-asserted-by":"crossref","first-page":"3470","DOI":"10.1002\/pmic.200700057","article-title":"SuperHirn\u2013a novel tool for high resolution LC-MS-based peptide\/protein profiling","volume":"7","author":"Mueller","year":"2007","journal-title":"Proteomics"},{"key":"2023012810455267900_btt274-B17","doi-asserted-by":"crossref","first-page":"M111.013722","DOI":"10.1074\/mcp.M111.013722","article-title":"System-wide perturbation analysis with nearly complete coverage of the yeast proteome by single-shot ultra HPLC runs on a bench top orbitrap","volume":"11","author":"Nagaraj","year":"2012","journal-title":"Mol. Cell. Proteomics"},{"key":"2023012810455267900_btt274-B18","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1186\/1471-2105-11-395","article-title":"MZmine 2: modular framework for processing, visualizing, and analyzing mass spectrometry-based molecular profile data","volume":"11","author":"Pluskal","year":"2010","journal-title":"BMC bioinformatics"},{"key":"2023012810455267900_btt274-B19","doi-asserted-by":"crossref","first-page":"758","DOI":"10.1093\/bioinformatics\/btp052","article-title":"Retention time alignment algorithms for LC\/MS data must consider non-linear shifts","volume":"25","author":"Podwojski","year":"2009","journal-title":"Bioinformatics"},{"key":"2023012810455267900_btt274-B20","doi-asserted-by":"crossref","first-page":"984","DOI":"10.1074\/mcp.M400061-MCP200","article-title":"Informatics platform for global proteomic profiling and biomarker discovery using liquid chromatography-tandem mass spectrometry","volume":"3","author":"Radulovic","year":"2004","journal-title":"Mol. Cell. Proteomics"},{"key":"2023012810455267900_btt274-B21","doi-asserted-by":"crossref","first-page":"2187","DOI":"10.1021\/ac048455k","article-title":"Quantitative proteomic analysis by accurate mass retention time pairs","volume":"77","author":"Silva","year":"2005","journal-title":"Anal. Chem."},{"key":"2023012810455267900_btt274-B22","article-title":"The decontools framework: an application programming interface enabling flexibility in accurate mass and time tag workflows for proteomics and metabolomics","volume-title":"Proceedings of 58th ASMS Conference on Mass Spectrometry and Allied Topics","author":"Slysz","year":"2010"},{"key":"2023012810455267900_btt274-B23","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1186\/1471-2105-9-163","article-title":"OpenMS\u2013an open-source software framework for mass spectrometry","volume":"9","author":"Sturm","year":"2008","journal-title":"BMC bioinformatics"},{"key":"2023012810455267900_btt274-B24","doi-asserted-by":"crossref","first-page":"959","DOI":"10.1038\/nmeth.1260","article-title":"Decision tree\u2013driven tandem mass spectrometry for shotgun proteomics","volume":"5","author":"Swaney","year":"2008","journal-title":"Nat. Methods"},{"key":"2023012810455267900_btt274-B25","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/978-1-60761-780-8_2","article-title":"Overview of quantitative LC-MS techniques for proteomics and activitomics","volume":"658","author":"Timms","year":"2010","journal-title":"LC-MS\/MS in Proteomics: Methods in Molecular Biology"},{"key":"2023012810455267900_btt274-B26","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1074\/mcp.M900177-MCP200","article-title":"IDEAL-Q, an automated tool for label-free quantitation analysis using an efficient peptide alignment approach and spectral data validation","volume":"9","author":"Tsou","year":"2010","journal-title":"Mol. Cell. Proteomics"},{"key":"2023012810455267900_btt274-B27","doi-asserted-by":"crossref","first-page":"650","DOI":"10.1002\/pmic.200700791","article-title":"Alignment of LC-MS images, with applications to biomarker discovery and protein identification","volume":"8","author":"Vandenbogaert","year":"2008","journal-title":"Proteomics"},{"key":"2023012810455267900_btt274-B28","doi-asserted-by":"crossref","first-page":"388","DOI":"10.2174\/138920209789177638","article-title":"Review of peak detection algorithms in liquid-chromatography-mass spectrometry","volume":"10","author":"Zhang","year":"2009","journal-title":"Curr. Genomics"},{"key":"2023012810455267900_btt274-B29","doi-asserted-by":"crossref","first-page":"M111.01058","DOI":"10.1074\/mcp.M111.010587","article-title":"PEAKS DB: de novo sequencing assisted database search for sensitive and accurate peptide identification","volume":"11","author":"Zhang","year":"2012","journal-title":"Mol. Cell. Proteomics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/29\/14\/1768\/48892107\/bioinformatics_29_14_1768.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/29\/14\/1768\/48892107\/bioinformatics_29_14_1768.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,28]],"date-time":"2023-01-28T12:30:47Z","timestamp":1674909047000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/29\/14\/1768\/229937"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,5,10]]},"references-count":29,"journal-issue":{"issue":"14","published-print":{"date-parts":[[2013,7,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btt274","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2013,7,15]]},"published":{"date-parts":[[2013,5,10]]}}}