title: A linear programming model for protein inference problem in shotgun proteomics.
abstract: BACKGROUND
  Assembling peptides identified from tandem mass spectra into a list of proteins, referred to as protein inference, is an important issue in shotgun proteomics. The objective of protein inference is to find a subset of proteins that are truly present in the sample. Although many methods have been proposed for protein inference, several issues such as peptide degeneracy still remain unsolved.
  
  
  RESULTS
  In this article, we present a linear programming model for protein inference. In this model, we use a transformation of the joint probability that each peptide/protein pair is present in the sample as the variable. Then, both the peptide probability and protein probability can be expressed as a formula in terms of the linear combination of these variables. Based on this simple fact, the protein inference problem is formulated as an optimization problem: minimize the number of proteins with non-zero probabilities under the constraint that the difference between the calculated peptide probability and the peptide probability generated from peptide identification algorithms should be less than some threshold. This model addresses the peptide degeneracy issue by forcing some joint probability variables involving degenerate peptides to be zero in a rigorous manner. The corresponding inference algorithm is named as ProteinLP. We test the performance of ProteinLP on six datasets. Experimental results show that our method is competitive with the state-of-the-art protein inference algorithms.
  
  
  BACKGROUND
  The source code of our algorithm is available at: https://sourceforge.net/projects/prolp/.
  
  
  BACKGROUND
  zyhe@dlut.edu.cn.
  
  
  BACKGROUND
  Supplementary data are available at Bioinformatics Online.
authors.affiliation: School of Software, Dalian University of Technology, Dalian 116621, China.
authors.forename: Ting
authors.initials: T
authors.lastname: Huang
authors.forename: Zengyou
authors.initials: Z
authors.lastname: He
mesh_terms: D000465:Algorithms; D030562:Databases, Protein; D006801:Humans; D016014:Linear Models; D013058:Mass Spectrometry; D010455:Peptides / Q000737:chemistry; D011336:Probability; D011382:Programming, Linear; D011506:Proteins / Q000737:chemistry*; D040901:Proteomics / Q000379:methods*; D015003:Yeasts / Q000737:chemistry
chemical_list: D010455:Peptides; D011506:Proteins