Degradation graphs reveal hidden proteolytic activity in peptidomes

Protein degradation is a regulated process that reshapes the proteome and generates bioactive peptides. Peptidomics and degradomics enables large-scale measurement of these peptides, yet most data analyses approaches treat peptides as isolated endpoints rather than intermediates produced by sequential cleavage. Here, we introduce degradation graphs, a probabilistic framework that represents proteolysis as a directed acyclic network of cleavage events with explicit absorption. From single-snapshot peptidomes, we infer graph weights by gradient descent or linear-flow optimization, quantify flows through branches and bottlenecks, and correct a core bias in conventional quantification. Across three biological datasets, failure to model downstream trimming leads to 3–4-fold underestimation of upstream proteolytic activity. Moreover, degradation graphs provide graph-structured features that enable machine learning models to capture protease-specific signatures from both graph topology and sequence context. Taken together, these findings establish explicit degradation modeling as a practical approach to mechanistic and interpretable peptidomics, bridging the fields of degradomics and peptidomics.Author summary: Proteins are continuously broken down into smaller fragments called peptides, a process known as proteolysis. This controlled degradation shapes the proteome, regulates signaling, and generates bioactive molecules involved in immunity, inflammation, and disease. Modern mass spectrometry techniques can measure thousands of such peptides, yet most analytical methods treat these peptides as isolated snapshots rather than as part of an ongoing proteolytic process.