MOTIVATION: 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.
AVAILABILITY: The source code of our algorithm is available at: 
https://sourceforge.net/projects/prolp/.
CONTACT: zyhe@dlut.edu.cn.
SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics 
Online.