A major challenge in shotgun proteomics has been the assignment of identified 
peptides to the proteins from which they originate, referred to as the protein 
inference problem. Redundant and homologous protein sequences present a 
challenge in being correctly identified, as a set of peptides may in many cases 
represent multiple proteins. One simple solution to this problem is the 
assignment of the smallest number of proteins that explains the identified 
peptides. However, it is not certain that a natural system should be accurately 
represented using this minimalist approach. In this paper, we propose a 
reformulation of the protein inference problem by utilizing the recently 
introduced concept of peptide detectability. We also propose a heuristic 
algorithm to solve this problem and evaluate its performance on synthetic and 
real proteomics data. In comparison to a greedy implementation of the minimum 
protein set algorithm, our solution that incorporates peptide detectability 
performs favorably.