This thesis contributes with methodologies for analyzing shotgun proteomic data. Firstly, we introduce PatternLab for proteomics, a computational environment that can pinpoint differentially expressed proteins when analyzing data from complex peptide mixtures, leverage the Gene Ontology to aid in experimental interpretation, discriminate trends in time-course experiments, and easily generate approximately area proportional Venn diagrams. Secondly, we introduce Charge Prediction Machine (CPM). CPM infers precursor ion charge based on its low resolution tandem mass spectrum (~1000) acquired using electron transfer dissociation; knowledge of the precursor charge is necessary for protein identification. CPM relies on a new approach inspired in the Bayesian discriminant function; it correctly classified 98% of the precursor charges in a test database while the only competing methodology (Charger, Thermo Fisher, San Jose – CA) correctly classified 86%. Thirdly, we introduce YADA, a new algorithm for deconvolution of high-resolution, high-accuracy mass spectra (<50 ppm). When compared to the commercially available solution (Xtract, Thermo Fisher, San Jose, CA), YADA identified 20% more unique peptides and was 700% faster. Lastly, we introduce a new experimental / computational approach for shotgun data acquisition called Extended Data Independent Analysis (XDIA). When tested on a yeast lysate, the number of identified spectra and unique peptides increased by 250% and 30%, respectively, as when compared to the state-of-the-art and widely adopted data-dependent analysis.