Structural disorder in prokaryotic genomes was predicted by the IUPred [37], [38] algorithm, and various measures, such as average disorder score, percent of disordered residues in proteins, percent of proteins with average disorder score above 0.5, percent of proteins with more disordered than ordered amino acids (mostly disordered proteins) and disorder in genomes were calculated (Table S1). To demonstrate that prediction of disorder is not biased by the skewed amino acid composition of extremophiles [12], we have repeated predictions with PONDR VSL2 [39], and have also carried out a very simple disorder-prediction approach that depends only on gross amino-acid composition measures (Charge-Hydropathy (CH) plot or Uversky plot [22]). Neither amino-acid composition, nor distribution of proteins in the CH-plot (Supplementary Figure S1) show a characteristic bias between the four groups, which suggests that disorder predictions by IUPred truly reflect the structural status of proteins encoded by genomes of bacteria of various OGT values (cf. Figure 1).

Average disorder of proteins (Figure 1A) and other measures of structural disorder (Table S1) in mesophiles and thermophiles varies a lot and reaches high levels in certain genomes. Hyperthermophiles, on the other hand, invariably show a low level of disorder, clustering on the lower edge of the apparently acceptable range of disorder characteristic of bacteria (above 1.5%) with the exception of one methanogen (Methanopyrus kandleri), which has 7.51% predicted disorder at an OGT of 98°C, probably reflecting the general positive deviation of disorder in methanogenes. The lifestyle of psychrophiles also appears to be compatible with only a low level of disorder. In all, bacteria with low levels of disorder are found throughout the entire OGT range, whereas the maximum of the frequency of disorder as a function of temperature shows a rather normal distribution that peaks between 40°C and 50°C.

Because several bacteria are noted for their habitat, without an exact OGT value determined, we also compared characteristic structural disorder in different temperature categories. A significant decrease of average disorder content in all non-mesophilic groups compared to mesophiles using nonparametric t-test is seen (Figure 1B). The structural and functional significance of this finding is underscored by a similar dependence on OGT of disorder found in long IDRs and mostly disordered proteins (Supplementary material, Figure S2). IUPred and VSL2 predicted a similar dependence, albeit somewhat different actual values. This distribution is unexpected, given the noted cold-resistance and heat-resistance of IDPs. We next examined possible explanations for this behavior.

A possible explanation of the observed behavior is that psychrophilic and hyperthermophilic prokaryotes are evolutionarily related to mesophiles of low disorder, whereas relatives of mesophilic prokaryotes of high disorder have not penetrated habitats of extreme temperatures. This is possible because often differences observed are not central to the process of adaptation, only represent side-effects [40]. If this were true, the lack of prokaryotes with a high level of disorder among hyperthermophiles would not reflect a selection against structural disorder driven by adaptation to high temperatures, rather it a random drift or selection for other features more related to phylogenetic relationships [40].

To probe this possibility, we have checked if predicted disorder reflects taxonomic relatedness more than optimal habitat of bacteria. To this end, predicted disorder (Table S1) was plotted on the phylogenetic tree of bacteria (Figure 2). The figure shows that except for a few cases (e.g. Actinobacteria) structural disorder correlates with the OGT rather than the taxonomical position of the species, which suggests that low levels in hyperthermophiles and psychrophiles is the result of evolutionary selection process. In principle, it is conceivable by either removal of proteins with a higher-than-average disorder or an overall diminution of disorder in all proteins, or both.

The general diminution in the frequency of structural disorder raises a very important issue with respect to how prokaryotes of low and high OGTs live without – or find substitutes for - the functions these proteins fulfill in mesophiles and thermophiles. Because structural disorder is strongly correlated with regulatory functions [19], [25], [41], a significant reduction of disorder upon thermal adaptation may correspond to the reduction of functional complexity of a species. Because the usual measure of complexity of different cell (or tissue) types cannot be applied to bacteria, we may intuitively relate complexity here with the number of genes and their encoded disorder. This is justified by observations that i) disordered proteins/regions in general are implicated in functions related to complexity, such as signaling and transcription regulation [24], [25]; ii) structural disorder correlates with complexity at the level of whole genomes, as underlined by the observation that the frequency of disorder increases with increasing complexity of the organism, with a particularly conspicuous increase in evolution between prokaryotes and eukaryotes [23]; iii) there is a direct link between complexity and disorder in transcription regulation [42], and iv) there is a significant difference between free-living bacteria, such as Actinobacteria of very complex responses and obligatory parasites, such as Mycoplasma, which are functionally “simple” because they live in a constant environment and cannot respond to many changes. Thus, we reasoned that functional simplification may also be apparent at the level of the whole genome/proteome in the thermal adaptation of bacteria, as already suggested based on observing the correlation of simple sequences of proteins and genome size [43]. Because simple sequences are related to structural disorder, we correlated the proteome size (number of proteins) with average protein disorder (Figure 3A). Clearly, proteome size is correlated with average structural disorder, and hyperthermophiles are located in the lower left corner of the plot, with small genomes and low average disorder (Figure 3B). This correlation between proteome size and average disorder applies to all bacteria, with some clear outliers, such as Actinobacteria (Figure 3C), which have a high predicted disorder at varying genome sizes, and halophilic bacteria (Figure 3D), which have small genomes but a high disorder. While high predicted disorder in Actinobacteria can be explained with their high complexity, we presume that disorder is mispredicted in prokaryotes adapted to high saline concentration because of the high surface charge of their globular proteins [44]. Overall, this correlation shows a reduction in genome size also previously observed in obligatory symbionts and parasites [45], which leaves only proteins with lower-than-average disorder.

These foregoing results suggest that the observed low disorder in hyperthermophiles reflects genuine adaptation at the level of genomes and/or individual proteins. Such an adaptation raises a very serious question with respect to the regulatory functions carried out by IDPs/IDRs in mesophiles: either these functions have been lost or simplified in prokaryotes of low/high OGT, or they have been substituted by ordered proteins/regions. We thought to answer this question by studying transcription factors (TFs), because they represent a prominent and indispensable functional group with a high level of functionally important disorder in both prokaryotes and eukaryotes [25], [46], [47], life in general cannot exist without them and their disorder is correlated with the number of genes they regulate, which suggests that their disorder is directly linked with functional complexity of the organism [42], [45]. Their function-related disorder is most apparent in trans-activation, but also in DNA-binding [46], [47], as also raised in the classic paper on the link between flexibility and specificity in DNA binding [48]. The function of long IDRs in several prokaryotic transcription-regulatory proteins, such as FlgM anti-sigma factor [26], plasmid partition protein KorB ([49], small DNA binding protein H-NS [50] and CcdA antitoxin [27], for has been directly established.

We used the GO annotation (GO:0003700) to filter out TFs from the high-quality SwissProt database in the four OGT groups and the two mesophilic control groups with the same proteome size as thermophiles (meso-thermo) and hyperthermophiles (meso-hyper) as defined above. As it was previously reported [46], the length of TFs is reduced in prokaryotes compared to eukaryotes, so first we checked if the average length of TFs in psychrophiles and hyperthermophiles is different from that in mesophiles. We found that TFs in both groups are significantly shorter (Figure 4A), but the difference between thermophiles and mesophiles is not significant. The difference between hyperthermophiles and their proteome-size-matched mesophilic controls (meso-hyper) was not significant (Figure 4A). On the other hand, the average predicted disorder content of TFs in hyperthermophiles is significantly decreased (P<0.0001), compared to either mesophiles or the meso-hyper controls (Figure 4B).

These observations are compatible with a general shortening of TFs at the expense of IDRs in adaptation to extremely high temperatures, but they also allow some more drastic changes removing the most highly disordered TFs upon adapting to high-temperature habitats. To check whether this latter has taken place, we assessed if the frequency of TFs has been lowered in hyperthermophiles vs. mesophiles. In doing this, we noted a possible source of error because the ratio of annotated genes is lower in hyperthermophiles than in mesophiles. Thus, by complementing the Swiss-Prot dataset with TrEMBL, we checked the frequency of TFs in all annotated proteins in the four thermal groups (Figure 4C). There is a lower number of TFs in thermophiles than in the thermo-meso group, but not so in the hyperthermophiles vs. the meso-hyper group. This suggests that the number of TFs correlates with the genome size, but structural disorder is under separate selection pressure, not directly linked with the number of TFs.

These observations suggest that hyperthermophiles reduce the level of disorder of their TFs, i.e. even if they find ordered substitutes for some disordered TFs, they experience a significant reduction of functional complexity that primarily affects regulatory functions.

While the frequency of protein disorder in hyperthermophiles is extremely low, it should be noted that there is a residual predicted disorder throughout the entire OGT range, i.e. life appears to be incompatible with less than about 1.5% disorder (cf. Figure 1A and Figure 3A). Given the major reduction of disorder in TFs, it is possible that there are certain functions which depend even more on disorder that account for this residual disorder. On the contrary, if this low disorder content is distributed with the same pattern among functional groups in hyperthermophiles as in mesophiles, it would rather suggest a noise, i.e. that disorder-related functions can be generally disposed of or substituted by ordered proteins in hyperthermophiles.

Thus, we filtered out proteins with long IDRs, which are likely to mark specific disorder-related functions, and categorized them by their GO biological process annotation. Hyperthermophiles were compared to two mesophilic group, one with low average disorder content (MLD, 1–4%, comparable to that in hyperthermophiles), and the other with higher disorder content (MMD, 8–11%). We reasoned that a comparison with the MLD group reveals the signs of adaptation to high temperatures, not obscured by the effect of reduction in genome size. In accord, we observed that the residual disorder is concentrated in hyperthermophiles in a few functions (Table 1). Most significantly, about 35% of proteins with long IDRs are associated with translation, many of them associated with ribosomal functions. Proteins annotated to transport process (e.g. protein translocases), regulation of transcription and ribosome biogenesis are also significantly overrepresented in hyperthermophiles.

Genome sequences of 332 prokaryotes with known temperature (or temperature range) for optimal growth were downloaded from the NCBI Genome Project database (Supplementary material, Table S1). In terms of their OGTs, prokaryotes are classified into four groups as psychrophiles (OGT: 5–17°C), mesophiles (20–42°C), thermophiles (45–75°C) and hyperthermophiles (75–105°C), as suggested in the NCBI database. If exact OGT is not specified, we searched the PGTdb [36] for temperature range. Of the 332 cases, exact OGT is given in 195 cases, whereas a respective temperature range (e.g. 20–30°C, cf. Table S1) in 124 cases. In these latter cases, the average of the range was taken as the OGT characteristic of that species. In the remaining 13 cases, no value or range of OGT is reported, but the organism is clearly classified to belong to one of the above four categories.

Structural disorder of proteins was predicted by two predictors, IUPred [37], [38] available at http://iupred.enzim.hu/ and PONDR VSL2 [39] available at http://www.ist.temple.edu/disprot/Predictors.html. A residue was classified as locally disordered if its score was above the threshold of 0.5. From the pattern of disorder of proteins, various measures were calculated, such as the average disorder score of proteins, the percentage of disordered residues in the whole proteome, and the percentage of proteins with more than 50% of their residues disordered (mostly disordered proteins). The frequency of residues in long IDRs (≥30 consecutive residues predicted as disordered), which is generally thought of as functionally important, was also calculated [23].

The amino acid composition of proteins in the four thermal categories were extracted from a non-redundant SwissProt dataset by analyzing all proteins from the studied species. CH values were calculated as described by Uversky et al. [22] on 2000 randomly selected proteins from a non-redundant SwissProt dataset in each thermal category. The CH plot is divided into two regions by a line (equation H = (R+1.151)/2.785, R: mean net charge, H: mean hydrophobicity) which best separates disordered (left side) and ordered (right side) proteins. In the calculation, a normalized Kyte-Doolittle scale was used to obtain hydropathy values, while Arg, Lys, Glu and Asp residues were considered in calculating mean net charge values.

Evolutionary relatedness of prokaryotes in terms of disorder was asked by looking whether the level of predicted structural disorder shows characteristic taxonomical distribution, or rather, a correlation with lifestyle. To this end, species of bacteria and archea were categorized according to their taxonomic classification (order and genera within, source: UniProt).

We asked if a functionally indispensable and usually highly disordered [46], [47] group of proteins, transcription factors, were differentially represented in prokaryotes of various OGTs. To this end, transcription factors in the four groups of bacteria and archea were selected by Gene Ontology (GO) annotation from UniProt SwissProt database. The search resulted in 18 transcription factors in psychrophiles, 1581 in mesophiles, 62 in thermophiles and 101 in hyperthermophiles (Supplementary material, Table S2). For comparisons of length and disorder content, we also created two subsets from mesophiles, with the same average proteome size as thermophiles (meso-thermo) and hyperthermophiles (meso-hyper), respectively. These datasets enabled us to address whether the reduction of disorder in TFs is a result of genome reduction or structural-functional alteration. For each group, the average length was calculated and the frequency of structural disorder was predicted by IUPred and VSL2.

To check for functional correlations, we categorized the proteins containing at least one long IDR (≥30 consecutive disordered residues) by their GO cellular process annotations. We then looked for the prevalence of distinct functional categories in three groups of prokaryotes, hyperthermophiles, mesophiles with a low level of average disorder (1–4%, group MLD) and mesophiles with a medium level of average disorder (8–11%, MMD).

We used the Mann Whitney test and Chi-square analysis with a 95% confidence interval to evaluate the significance of differences between selected groups. All programs were written in BOS(v3.0) [64] – an integrative biological programming environment - (http://www.biobhasha.org) and Perl language. BOS and Perl scripts and other compiled software (e.g., IUPred, etc.) were executed locally.