Proteomics, or the measurement of all proteins present in a biological system under defined conditions, is a relatively young field that is rapidly developing. Currently the best method to achieve high proteome coverage is with bottom-up proteomics, in which the proteome is digested into peptides that are identified followed by inference of their protein origin. Several steps in the bottom-up proteomics workflow leave room for improvement, especially proteome digestion. This work investigates novel bottom-up proteomics methods for improved sensitivity, proteome coverage, and ultimately PTM detection. Chapter II investigates the effect of two chemicals on peptide electrospray sensitivity. We postulated that peptide supercharging combined with ETD would improve the identification efficiency of peptides, especially nontryptic peptides. We measured the charge state distributions, the total signal, and the number of identified peptides for peptides produced from trypsin, elastase, or pepsin digestion. Unexpectedly, the results show that addition of 5% DMSO to mobile phases used for peptide separation with online ESI resulted in charge state coalescence of peptide signal towards a single charge state, therefore improving signal to noise. In Chapter III the novel application of two proteases, WaLP and MaLP, for proteome digestion are explored. The results show that the combination of data from separate proteome digestion with trypsin, LysC, WaLP, and MaLP double the observed proteome sequence coverage. The increased coverage was most beneficial for coverage for protein sequences containing too many or too few tryptic cleavage sites. The increased coverage was also beneficial for coverage of proteins with many transmembrane helices. Chapter IV presents a computational study that attempts to optimize proteome digestion using various real and theoretical cleavage agents. Individual digestions and iterative digestion strategies were simulated. One conclusion of this work is that the greatest proteome coverage can be obtained using iterative digestion with cleavage starting at the rarest residues first. Chapter V demonstrates a novel method for untargeted, site-level identification of endogenous SUMO attachment sites in the human proteome. When proteins modified by SUMO are digested with WaLP, a SUMO-remnant diglycyl-lysine modification is left at the site of SUMOylation, which is then detected by tandem mass spectrometry. The results demonstrate identification of 707 unique SUMO modification sites in 443 proteins, of which 414 are previously unknown SUMOylation sites