For untargeted volatile metabolomics analyses, comprehensive two-dimensional gas chromatography (GC×GC) is a powerful tool for separating complex mixtures and can provide highly specific information about the chemical composition of a variety of samples. With respect to human disease, the application of GC×GC in untargeted metabolomics is contributing to the development of diagnostics for a range of diseases, most notably bacterial infections. Pseudomonas aeruginosa, in particular, is an important human pathogen, and for individuals with cystic fibrosis (CF), chronic P. aeruginosa lung infections significantly increase morbidity and mortality. Developing non-invasive tools that detect these infections earlier is critical for improving patient outcomes, and untargeted profiling of P. aeruginosa volatile metabolites could be leveraged to meet this challenge. The work presented in this dissertation serves as a case study of the application of GC×GC in this area.Using headspace solid-phase microextraction and time-of-flight mass spectrometry coupled with GC×GC (HS-SPME GC×GC-TOFMS), the volatile metabolomes of P. aeruginosa isolates from early and late chronic CF lung infections were characterized. Through this study, the size of the P. aeruginosa pan-volatilome was increased by almost 40%, and differences in the relative abundances of the volatile metabolites between early- and late-infection isolates were identified. These differences were also strongly associated with isolate phenotype. Subsequent analyses sought to connect these metabolome-phenome trends to the genome by profiling the volatile metabolomes of P. aeruginosa strains harboring mutations in genes that are important for regulating chronic infection phenotypes. Subsets of volatile metabolites that accurately distinguish between wild-type and mutant strains were identified. Together, these results highlight the utility of GC×GC in the search for prognostic volatile biomarkers for P. aeruginosa CF lung infections. Finally, the complex data sets acquired from untargeted GC×GC studies pose major challenges in downstream statistical analysis. Missing data, in particular, severely limits even the most robust statistical tools and must be remediated, commonly through imputation. A comparison of imputation strategies showed that algorithmic approaches such as Random Forest have superior performance over simpler methods, and imputing within replicate samples reinforces volatile metabolite reproducibility.