Abstract
IEF LC-MS/MS (Iso-Electric-Focusing Liquid-Chromatography Tandem-Mass-Spectrometry) is an analytical method that incorporates a two-step sample separation prior to MS identification of proteins. When analyzing complex samples this preparatory separation allows for higher analytical depth and improved quantification accuracy of proteins and PTMs. IEF fractionation builds upon isoelectric point (pI) differences between peptides or proteins. In standard IEF LC-MS/MS, each fraction is separately profiled using LC-MS/MS. The cost of the complete assay, therefore, is strongly dependent on the number of pI fractions being analyzed. Commonly, studies are focused on a specific group of proteins. We propose an approach that selects a subset of fractions for LC-MS/MS analysis that is highly informative in the context of the proteins of interest. Specifically, our method allows a significant reduction in cost and instrument time as compared to the standard protocol of running all fractions, with little compromise to coverage. We develop algorithmics to optimize the selection of the IEF fractions on which to run LC-MS/MS. We translate the fraction optimization task to Minimum Set Cover (MSC), a well-studied NP-hard problem. We develop heuristic solutions and compare them in terms of effectiveness and of practical running times. We provide examples to demonstrate advantages and limitations of each algorithmic approach. Finally, we test our methodology by applying it to experimental data obtained from IEF LC-MS/MS analysis of yeast and human samples. We demonstrate the benefit of this approach for analyzing complex samples with a focus on different protein sets of interest.