In analyzing the proteome using mass spectrometry, the mass values help identify the molecules, and the intensities help quantify them, relative to their abundance in other samples. Peptides that are shared across dierent protein sequences are typically discarded as being unin- formative w.r.t each of the parent proteins. In this paper, we investigate the use of shared peptides which are ubiq- uitous ( 50% of peptides) in mass spectrometric data-sets. In many cases, shared peptides can help compute the relative amounts of dier- ent proteins that share the same peptide. Also, proteins with no unique peptide in the sample can still be analyzed for relative abundance. Our paper is the first attempt to use shared peptides in protein quantifica- tion, and makes use of combinatorial optimization to reduce the error in relative abundance measurements. We describe the topological and numerical properties required for robust estimates, and use them to im- prove our estimates for ill-conditioned systems. Extensive simulations validate our approach even in the presence of experimental error. We apply our method to a model of Arabidopsis root knot nematode infec- tion, and elucidate the dierential role of many protein family members in mediating host response to the pathogen.