L'inférence de protéine correspond au problème visant à retrouver quelles protéines sont présentes dans un échantillon tout en ayant connaissance des peptides présents dans ce même échantillon après digestion. Les peptides sont des morceaux de protéines obtenus après la digestion de celle-ci. Il est clair qu'avoir connaissance des peptides présents dans l'échantillon digéré va aider à retrouver les protéines présentes dans l'échantillon d'origine. Cependant, plusieurs protéines différentes peuvent amener à un même peptide après digestion, ce qui correspond à une ambiguïté. Ce sont ces mêmes ambiguïtés qui rendent le problème difficile. Notre but est de proposer plusieurs modélisations du problème d'inférence de protéine tout en apportant pour chacun d'eux, un certain nombre de résultats théoriques liés à leur complexité. Ce sont ces différents modèles ainsi que ces différents résultats que nous présentons dans cet article.