Many efforts have been made to discover novel bio-markers for early disease detection in oncology. However, the lack of efficient computational strategies impedes the discovery of disease-specific biomarkers for better understanding and management of treatment outcomes. In this study, we propose a novel graph-based scoring function to rank and identify the most robust biomarkers from limited proteomics data. The proposed method measures the proximity between candidate proteins identified by mass spectrometry (MS) analysis utilizing prior reported knowledge in the literature. Recent advances in mass spectrometry provide new opportunities to identify unique biomarkers from peripheral blood samples in complex treatment modalities such as radiation therapy (radiotherapy), which enables early disease detection, disease progression monitoring, and targeted intervention. Specifically, the dose-limiting role of radiation-induced lung injury known as radiation pneumonitis (RP) in lung cancer patients receiving radiotherapy motivates the search for robust predictive biomarkers. In this case study, plasma from 26 locally advanced non-small cell lung cancer (NSCLC) patients treated with radiotherapy in a longitudinal 3 × 3 matched-control cohort was fractionated using in-line, sequential multiaffinity chromatography. The complex peptide mixtures from endoprotease digestions were analyzed using comparative, high-resolution liquid chromatography (LC)-MS to identify and quantify differential peptide signals. Through analysis of survey mass spectra and annotations of peptides from the tandem spectra, we found candidate proteins that appear to be associated with RP. On the basis of the proposed methodology, α-2-macroglobulin (α2M) was unambiguously ranked as the top candidate protein. As independent validation of this candidate protein, enzyme-linked immunosorbent assay (ELISA) experiments were performed on independent cohort of 20 patients' samples resulting in early significant discrimination between RP and non-RP patients (p = 0.002). These results suggest that the proposed methodology based on longitudinal proteomics analysis and a novel bioinformatics ranking algorithm is a potentially promising approach for the challenging problem of identifying relevant biomarkers in sample-limited clinical applications.