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.