Statistics of the PTMs in the data set. (A) Number of residues and proteins per PTM type, PTM types are abbreviated as Ph (phosphorylation), NG (N-linked glycosylation), Ac (acetylation), OG (O-linked glycosylation), Ub (ubiquitination), Me (methylation), SM (SUMOylation), Hy (hydroxylation), Ca (carboxylation), Pa (palmitoylation), Su (sulfation), Ni (nitrosylation) and CG (C-linked glycosylation). (B) Breakdown of modified proteins by the number of PTM types per protein; the proteins with the highest PTM type frequency have all been intensively studied, e.g., coagulation factors, hypoxia-inducible factor or p53. (C) Co-occurrence of different types of PTMs within proteins, nodes size represent the abundance of proteins with a particular PTM type, the edge widths represent the number of proteins modified by the two respective PTM types normalized by the total number of proteins with the less abundant PTM type. Phosphorylated and glycosylated (O- or N-linked) residues are found in combination with all other PTM types followed by acetylation which it is not present together with C-linked glycosylation and carboxylation; only carboxylation and C-linked glycosylation (with the fewest sites in our data set) co-occur together with less than six other PTMs. (D) Breakdown of experimentally validated PTMs per species for each PTM type, the total number of proteins per PTM type, and the fractions of residues targeted by each PTM type (O* means others amino acids).

Differential conservation of PTM types. (A) The RCS is composed of two components: the MBL that is the longest evolutionary distance among species that contain a conserved modified residue and the RCR that quantifies the conservation ratio of the modified residue across the species in a taxonomic group in which a least one conserved site residue has been observed. The score is illustrated by a modified serine (circled) within a column of a MSA of orthologs where the species with the longest branch length containing the residue are Macaca mulatta and Rattus norvergicus; In the respective taxonomic group, 3 out of 4 species maintain the serine in the same position and thus the RCR is 0.75. (B) Average of the relative RCS (rRCS, obtained via comparison of RCSs of other residues in the protein, see Materials and methods for details) per each PTM type in human and in all species together. (C) Distribution of the mean of the rRCS in each PTM type across 8 eukaryotes. Colors indicate the degree of conservation (blue for more conserved residues and red for fastest evolving ones). PTM types are sorted according to the human values.

Global map of co-evolving PTMs. (A) Illustration of the co-evolving score based on MI: Two PTMs (acetylation in blue and phosphorylation in red) are pairwise evaluated in three different situations in which both residues are present in half of the orthologs from 10 species. The score includes the capacity of MI to address the level of dependency of two variables (maximum in both the right and left sequence alignments), and the degree of conservation of the amino acid across the species in the alignment (which is maximal in the left coupling). (B) Global network of co-evolving PTM types. PTMs types are represented as nodes whereby the size of the nodes indicate the number of proteins with such modification. Inside the nodes, the proportion of proteins with co-evolution is given for each PTM type: with the same (light gray) and with any other PTM type (dark gray). Red edges represent a predicted global functional association between two PTM types, the intensity of the color (from dark to light red) represents the fraction of the significantly co-evolving pairs of residues of all possible pairs within the proteins. The edge width indicates the fraction of proteins with the two co-evolving PTM types. Thus, thin dark red edges denote PTM pairs that have a low level of co-occurrence within proteins but if this happen they show a high level of co-evolution, thick light red edges link PTM pairs with a high co-occurrence in proteins of which only a few are co-evolving, yet significantly. The degree of association between PTM types (color intensity) does not always correlate with their frequency of co-occurrence in proteins (width). For example, although ubiquitination and SUMOylation are not frequently found to co-occur in proteins, almost in all of these instances they are predicted to be functionally associated. Furthermore, most nitrosylated proteins are also phosphorylated or acetylated but there is a much higher degree of co-evolution with phosphorylation. Blue edges represent known crosstalk between PTM types extracted from the literature, either well established (dark blue) or mentioned only in one case studies (light blue). (C) Network of co-evolving PTM types showing the preferred cell locations of the respective proteins.

Properties and functional implications of functionally associated PTMs. Residues of several co-evolving PTM types are found to be close in sequence (A) or structure (B) compared with equivalent modified, but not co-evolving residues in the same proteins. All PTM types pairs shown in (A, B) have co-evolving sites significantly closer than control sets with an adjusted P-value by FDR <0.05 in some of the 100 repetitions the analysis was repeated as we work with random sets as background. The bootstrapping values for the number of times the difference was found significant is showed by * (>50 times) and ** (100 times). The PTM types pairs are classified according to their status in our prediction, in black the pairs that we predict to be functionally associated, in red the ones that did not show a global co-evolution and in blue the pairs found to be associated only in the literature, in this two last cases even if a global co-evolution was not significant, several residues were found to be significantly co-occurring. For more distance analysis see Supplementary Figure 14. (C) Co-evolving PTM types are associated to protein domains probably regulating their activity, illustrated by phosphorylated and acetylated residues in the spectrin repeats of the protein ACTN4, spectrin repeats are in general enriched in the association between these two PTM types. (D) Protein RelA is phosphorylated inside the cell surface receptor domain in four residues (S205, T254, S276 and S281) that are found co-evolving with both, methylated and acetylated residues. As suggested by the reported co-regulation between phosphosite S256 and acetylated and methylated residues, a more general scenario is proposed where four phosphorylation would be enhancing the acetylation of seven lysines that would lead to protein degradation. In the absence of phosphorylation, four residues would become methylated and the protein translocated to the nucleus. (E) The DLF motif is associated with the co-evolution of phosphorylations and methylations, illustrated by the example of the PABPC1 protein. (F, G) Co-evolving methylated and SUMOylated residues can regulate protein localization in different ways depending on which type of modification is placed inside the nuclear localization signal (NLS) motif.