Post-translational modifications (PTMs) are pivotal in cellular regulations, and their crosstalk is related to various diseases such as cancer. Given the prevalence of PTM crosstalk within close amino acid ranges, identifying peptides with multiple PTMs is essential. However, this task is an NP-hard combinatorial problem with exponential complexity, posing significant challenges for existing analysis methods. Here, we introduce PIPI-C (PTM-Invariant Peptide Identification with a Combinatorial model), a novel search engine that addresses this challenge through a mixed integer linear programming (MILP) model, thereby overcoming the limitations of existing approaches that struggle with high-order PTM combinations. Rigorous validation across diverse datasets confirms PIPI-C's superior performance in detecting PTM combinations. When applied to over 72 million mass spectra of three human cancers-lung squamous cell carcinoma (LSCC), colorectal adenocarcinoma (COAD), and glioblastoma (GBM)-PIPI-C reveals significantly upregulated PTM combinations. In LSCC, 50% of 860 upregulated unique PTM site patterns (UPSPs) (when comparing cancer vs. normal samples) carried at least two PTMs, including literature-supported crosstalks such as di-methylation with trifluoroleucine substitution and amidation with proline-to-valine substitution. Similar findings in COAD and GBM highlight PIPI-C's utility in uncovering cancer-relevant PTM combination landscapes. Overall, PIPI-C provides a robust mathematical framework for decoding complex PTM patterns, advancing our understanding of PTM-driven cellular processes in diseases.

Amino acid (AA) substitutions play a critical role in regulating cellular activities, including complex signaling and cell cycle processes. Recent research on AA substitutions has primarily relied on genomic and transcriptomic data. The identification at the proteomic scale remains underexplored, despite evidence suggesting that DNA and RNA biosynthesis are not the sole sources of these substitutions. This gap persists due to challenges in analyzing large-scale proteomic data. In this study, we address this limitation by analyzing multiple independent datasets across five cancer types using PIPI-C, a novel mass spectrometry data analysis tool. And we propose AA substitutomics, a pipeline for characterizing AA substitutions arising after protein translation and dissecting the regulatory functions of key proteins with AA substitutions. Among our identified AA substitutions, 87% are novel findings and not recorded in genomic/transcriptomic databases, which indicates that the post-translational AA substitutions are prevalent. Our findings reveal biologically significant AA substitutions linked to cancer, such as F43S and E91D in hemoglobin subunit beta, P584T in filamin A, and A175N in fructose-bisphosphate aldolase B. Furthermore, our pipeline enables direct investigation of drug resistance and immune escape. By capturing functional protein-level alterations beyond genomic and transcriptomic profiling, it establishes a robust framework to advance cancer research.

Amino acid (AA) substitutions are pivotal modulators of cellular signaling and homeostasis. Current studies of AA substitutions rely mainly on genomic and transcriptomic evidence, while proteome-level characterization remains underexplored, even though such substitutions can arise beyond DNA and RNA mutations. Here we address this gap with PIPI-C, an open-search mass spectrometry tool, and establish an integrated AA substitutomics pipeline to profile AA substitutions across five cancer cohorts and dissect the regulatory roles of substitution-bearing proteins. By cross-referencing 13,399 identified AA substitutions with matched whole-exome sequencing data, we observed no overlap with patient somatic mutations. Specifically, 61% of these substitutions required two or more base alterations and could not be derived from single-nucleotide variants, rendering them exclusively detectable at the proteomic level. The remaining 39% of substitutions were compatible with single-base variations. PIPI-C captured these candidate substitutions at the proteome scale, consistent with a translational-stage origin as reported for alternate RNA decoding in mammals. We further identified notable substitutions, including F43S and E91D in hemoglobin subunit beta, P584T in filamin A, and A175N in fructose-bisphosphate aldolase B, and our pipeline provides a framework for generating hypotheses about AA substitutions in cancer escape.

Post-translational modifications (PTMs) are pivotal in cellular regulations, and their crosstalk is related to various diseases such as cancer. Given the prevalence of PTM crosstalk within close amino acid ranges, identifying peptides with multiple PTMs is essential. However, this task is an NP-hard combinatorial problem with exponential complexity, posing significant challenges for existing analysis methods. Here, we introduce PIPI-C (PTM-Invariant Peptide Identification with a Combinatorial model), a novel search engine that addresses this challenge through a mixed-integer linear programming (MILP) model, thereby overcoming the limitations of existing approaches that struggle with high-order PTM combinations. Rigorous validation across diverse datasets confirms PIPI-C's superior performance in detecting PTM crosstalks. When applied to over 72 million mass spectra of three human cancer--lung squamous cell carcinoma (LSCC), colorectal adenocarcinoma (COAD), and glioblastoma (GBM)--PIPI-C reveals significantly upregulated PTM crosstalks. In LSCC, 50% of 860 upregulated unique PTM site patterns (UPSPs) (when comparing cancer vs. normal samples) carried at least two PTMs, including literature-supported crosstalks such as di-methylation with trifluoroleucine substitution and amidation with proline-to-valine substitution. Similar findings in COAD and GBM highlight PIPI-C's utility in uncovering cancer-relevant PTM crosstalk landscapes. Overall, PIPI-C provides a robust mathematical framework for decoding complex PTM patterns, advancing our understanding of PTM-driven cellular processes in diseases.

Cross-linking mass spectrometry (XL-MS) is a technique for investigating protein-protein interactions (PPIs) and protein structures. In the realm of biology, post-translational modifications (PTMs) play a critical role in regulating PPIs and reshaping protein structures. However, the identification of PTMs in XL-MS data poses a great computational challenge and thus remains unexplored. In this study, we introduce SeaPIC, the first XL-MS tool that enables biologists to investigate PTMs in PPIs and protein structures. Our experiments demonstrate the successful identification of PTMs within cross-linked peptides, which were previously undiscovered.