Genotype space as a graph

A simple exact model (SEM) consists of three main parameters: sequence length (), monomer alphabet () and the potential (). Genotype space (), is composed of sequences. Where . (, is the cardinality of the set ). The dimension of , , is defined as the total number of single point mutant neighbors of a given sequence, as: . For 2, is called a generalized hypercube (). A sequence , is composed of monomers . A hamming distance metric, , over , defines a n-cube or hypercube, where (,), corresponds to the number of point mutations needed to transform genotype into [62]. Similarly, the space of phenotypes, , corresponds to the set of all possible conformations. The enumerable conformational space is independent of and growths exponentially as a function of .

The potential energy function, , specifies the energy associated to the interaction between monomers and . The total stability () of a sequence , folded onto conformation , is defined as:(1)

The function , adopts a value of 1 if monomers at positions and are in contact and non-adjacent along the chain, 0 otherwise. The degeneracy () of sequence corresponds to the number of conformations adopted at ( = min()). According to the thermodynamic hypothesis of protein folding, a sequence folds onto a conformation , if and only if, is non-degenerate on (i.e.  = 1). In that case, is called the native structure of .

Genotype neighborhoods and phenotypic diversity

The k- neighborhood of a sequence is defined as the set of sequences at a hamming distance equal or lower than k, respect to (). The number of sequences of a k-neighborhood increases as . For and  = 18; 1, 3, and 5-neighborhood contain 18; 987; and 12,615 sequences, respectively.

In order to quantify the relative distribution of phenotypes across sequence space, I consider the phenotypic diversity of a k-neighborhood centered at a sequence (). is simply defined as the set of phenotypes encoded by sequences in the k-neighborhood of . for small k values, informs on the fraction of immediate accessible phenotypes, those expected to be available after few point mutations; whereas larger k values, tell us about the overall diversity of phenotypes across sequence space.

Sequences, networks and components

By applying Eq. 1 over all sequences in , a given potential , induces the folding (i.e. mapping) of a set of non-degenerate sequences (), which represents a fraction of genotype space ( ); into the set , a fraction of phenotype space ( ). We say that is the accessible conformational space induced by the potential on . The total fraction of non-degenerate sequences induced by , is called non- degeneracy ( =  = ). Similarly, encodability can be defined as:  = .

The non-degenerate fraction of sequence space induced by , can be treated as a network of genotypes () (Figure 1). Sequences are nodes, and edges are formed between pairs of sequences that differ in one point mutation (h(,) = 1). When two nodes in can be connected by a series of single point mutations, we say there is a mutational path () between them. The diameter of a graph corresponds to its largest .

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Figure 1. A two-dimensional caricature of a genotype network ().

Sequences are represented as nodes. Edges are drawn between sequences that differ in 1 mutation. Degenerate sequences (1) are in grey, open squares. In this example,  = 192 nodes;  = 84 nodes;  = 0.43. is composed of 3 genotype components ( = ()). Top left,  = 53; top right,  = 24; bottom,  = 7. Non-degenerate sequences in this example, fold onto 5 phenotypes represented by the neutral sets in colors blue,  = 12; green,  = 19; orange,  = 15; magenta,  = 23; and yellow,  = 15. Genotype components and are composed of more than 1 neutral network.  = {} and  = {}. Phenotype 1 (blue) can be found in genotype components and :  = {}. Phenotype 2 (orange) can be found in all three genotype components:  = {}. Genotype component , is also a neutral network: .

https://doi.org/10.1371/journal.pcbi.1003946.g001

A connected component of a genotype network, or genotype component (), is a subset of nodes in , for which there is at least one between every possible pair of sequences (,). A genotype network can be composed of one or more than one genotype component (); and the total number of sequences in the network is the sum of the number of sequences in each component (). Note that represents the set of genotype components, represents the number of genotype components, whereas , the size, in number of sequences, of genotype component . For instance, in Figure 1, is composed of three : . (I drop the subscript G, since all genotype components are necessarily part of ).

The distinction of genotypes according to the phenotypes they map onto, induces subgraphs, whose properties have important consequences for the architecture of the map and can be characterized quantitatively in terms of the statistics of their expected size, diameter and distances. Sequences that fold onto the same phenotype are called neutral sets () and are, by definition, subsets of the genotype network (). Note that the number of is equivalent to the number of accessible phenotypes (). For instance, in Figure 1, is composed of 5 , represented by different colors.

Sequences are known to distribute heterogeneously over conformations and this property of a phenotype, traditionally called designability (C) [16], has important implications for evolution and design. The designability of a phenotype j is equivalent to the size, in terms of number of sequences, of the neutral set associated to phenotype j (C = ).

As in the case of , a neutral set () can also be composed of more than one connected component. These connected subsets of non-degenerate sequences, that map to the same phenotype, are called neutral networks (). Note the subscript distinction. refers to genotype, as in genotype network () and genotype component (). refers to phenotype. However, instead of using phenotype network () and phenotype component (), I stick to the terms traditionally used in the literature: neutral sets and neutral networks, respectively [5], [42].

A neutral set can be composed of more than one neutral network (). refers to the neutral network in the neutral set of phenotype (); and genotype component . As is the case of , all pairs of sequences in are connected by at least one mutational path. For instance, Figure 1, shows 9 . The largest genotype component in (), is composed of 4 and 5 .

Similar to the idea of designability (C), here I define a network's neutrality as the size, in number of sequences, of a neutral network, as: C = . Whereas the neutrality of a single sequence (), is defined as the fraction of mutants in the 1-neighborhood of , that are part of .

A genotype component () in , can be composed of more than one neutral network (). But, note that not all neutral networks () of a given neutral set (), are necessarily part of the same genotype component (). Sequences in are the sum of sequences in neutral networks () that can be part of different genotype components: . For instance, (Fig. 1, in blue), can be expressed as  = (). (See Table S2 in Text S1 for a summary of symbols and abbreviations).

Ideal and excess parts of a potential

A binary potential can be represented as a vector composed of 3 values, that describe 2 types of interactions (Figure 2A). First, those between the same type of monomers, or homomonomeric (i.e. , ); and second, the heteromonomeric interaction (i.e. ). The heteromonomeric interaction of a binary potential can be decomposed into ideal and excess parts [12], [30]. These parts describe the extent to which the potential favors two different hypothetical stages of the folding process. The ideal part represents an heteromonomeric interaction as in an ideal liquid. That is, as if there was no energetic contribution by the heteromonomeric interaction, and therefore it could just be approximated by the arithmetic mean of their homomonomeric values, as:  = (+)/2. In contrast, the excess part ( =  - ), aims to capture the contribution of the heteromonomeric interaction, and describe the extent to which the native conformation differs from an ideal mixture of amino acids, its additivity (). Here, I quantify the additivity of a given potential as:  = [E/E]+1 = /E.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Figure 2. Potentials for the canonical HP and AB models.

(A) General structure of a binary potential, composed of monomers and . Potentials of the HP model (B), AB model (C), HP shifted (D), AB shifted (E).

https://doi.org/10.1371/journal.pcbi.1003946.g002

The L18 model

In this study I use a two-dimensional SEM of sequence length 18 mer. In the following I refer to this model as L18. The motivations for using this model, are fourfold. First, L18 represents a good compromise in relation to the number of sequences versus the number of conformations. Second, inspired by globular proteins, some previous studies assume that foldable sequences must adopt a maximum number of contacts. Because the restriction of phenotype space to maximally compact conformations introduces artifacts, as inflated values of designabilities [50], here I consider sequences folding onto any possible conformation, as long as, the thermodynamic criterion is met. Third, compared to three-dimension, two-dimension SEM show a surface-core ratio more similar to natural proteins [13]. Finally, the L18 model has been extensively used to evaluate different alphabets and potentials [42], [43], which will allows us to compare our results to previous findings.

In the case of L18, is composed of 5,808,335 total conformations, and , of 262,144 sequences. Because the energy of a sequence folded onto a given conformation is here approximated by the contact of non-adjacent monomers along the chain, conformations in a lattice are usually represented as contact sets, a binary symmetric L by L matrix that describes the interactions of non-adjacent monomers [63]. Due to the larger degrees of freedom of conformations with few contacts, different conformations may correspond to the same contact set. The total 5,808,335 conformations of the L18 model, can be described by 170,670 non-redundant contact sets. Only 77,635 out of the 170,670 contact sets, are unique (ie. each one of them correspond to a single conformation) and therefore potentially encodable () under the thermodynamic hypothesis criterion [39]. The accessible conformational space of a sequence-structure map, represents a subset of the uniquely encodable set of conformations ().

Foldability

A sequence's foldability (), is mathematically described as the deviation of the energy minimum from the energy distribution of the ensemble of all possible conformations in [50]:(2) is the expected stability of sequence , over all possible conformations in the ensemble; , the standard deviation over the same distribution; and , the minimum observed energy of folded onto . A more negative value describes a steeper folding funnel and therefore protein-like behavior.

Types of binary potentials and the space of phenotypes

The potential of a binary alphabet is described by three values: , and (with  = , see Figure 2A). values are real numbers. If negative, they correspond to attractive interactions. If positive, repulsive. Neutral interactions () do not contribute to stability. Because of the symmetry () of the cube (), homomonomeric interactions ( and ) are interchangeable. In other words, if all monomers were exchanged by monomers, properties of genotype space would remain the same.

The first protein lattice model ever studied was the HP model [12]. It is composed of two types of amino acids, polar (P) and hydrophobic (H). The potential is detailed in Fig. 2B. Only homomonomeric hydrophobic interactions () contribute to the stability of a folded sequence.

An alternative to the HP model, the AB model, was introduced in order to explore the impact of the potential on protein design [64]. The AB potential introduces equivalent interactions between homomonomers ( =  = −1.0) and a repulsive interaction ( = 1.0), (Fig. 2C). The HP and AB potentials have been modified (the so called shifted potentials) to study explicitly the impact of repulsive interactions [39]. Figures 2D and 2E show the shifted versions of HP and AB potentials. I refer to these 4 potentials as canonical.

In order to investigate the impact of the potential on the sequence-structure map, I begin our analysis by sampling the space of possible binary potentials, with −1.00, −0.75, −0.50, −0.25, 0.00, 0.25, 0.50, 0.75, 1.00; of which, canonical potentials are a small subset. Since a binary potential is composed of three values, our sample produces a total of possible . From these total possible combinations one must ignore potentials with no relative favorable interactions ( =  = ), potentials with only repulsive or neutral interactions (, , 0.0), scaled potentials of the form , , (with ), take into account the symmetry at homomonomeric interactions (i.e. ,, = ,,), and, the symmetry between homo versus heteromonomeric interactions (i.e. if  = ; then, , , , , , , ). These considerations result on a total of 245 potentials.

Potentials can be represented as vectors. Due to the symmetry of the cube (), half of the space contains all possible non-redundant binary potentials. As suggested by previous studies, many properties of the potential energy function are determined by the proportion of repulsive, attractive and neutral interactions [39], [50]. I use this criterion to distinguish among 7 types of potentials, that correspond to the 6 non-redundant octants in the 3d -coordinates representation, plus any potential with at least one 0 (Table 1, Figure 3). The octant in black (Fig. 3), that corresponds to all-repulsive interactions (, , 0.0); is defined as potential type VII and, by definition, does not stabilize any conformation (see Eq. 1). The 245 potentials described above are an homogeneous sample from this space.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Figure 3. Binary potentials as vectors of values.

Figure show a graphic representation of the 7 types of potentials described in Table 1. These potentials (type I-V, VII), correspond to the 6 non-redundant octants in the 3d representation of coordinates. Potentials type VI, those with at least one  = 0.0, are represented by grey planes between octants.

https://doi.org/10.1371/journal.pcbi.1003946.g003

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Table 1. Type of potentials for binary alphabets.

https://doi.org/10.1371/journal.pcbi.1003946.t001

For each of the 245 potentials I proceed as follows. I enumerate all possible sequences. I fold each sequence onto every contact set and calculate its stability and foldability using equation 1 and 2, respectively. (The raw data of the 245 sequence-structure maps studied here, is available at: www.santafe.edu/eferrada, see Table S1 in Text S1.).

In order to compare different potentials and their impact on properties of the sequence-structure map, I use hierarchical clustering (see Supplementary Methods). The Jaccard similarity index, between the sets and (), (with , ; ), is defined as:  = . , measures the similarity between the sets of conformations and (with ), induced by the potentials and , respectively. Similarly, , compares sets of sequences and (with ) (see Supplementary Methods).

Figure 4 presents a hierarchical clustering of phenotype space based on (and ), for all possible pair combinations of binary potentials and (, 1,…, 245). Here I arbitrarily choose to focus on , however, similar conclusions arise from the analysis of the Jaccard index on genotype space () (Figure S1). Each tip of the tree represents an independent sequence-structure map. Maps that cluster closely in this tree have similar sets of accessible phenotypes (), that is, values close to 1.0. values that compose each potential are specified on a color scale at the branches' tips, with , specified at the outermost value. Branches are colored according to the potential, as described above (Table 1, Figure 3). Green and blue stacked bars following the color-coded potentials, correspond to non-degeneracy and encodability values, respectively. Boxplots, in black, represent the distribution of foldability over all non-degenerate sequences of each map.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Figure 4. Hierarchical clustering of phenotype spaces generated by the sequence-structure maps of binary potentials.

Potentials are sampled by considering −1.00, −0.75, −0.50, −0.25, 0.00, 0.25, 0.50, 0.75, 1.00 (see main text and Table S1 in Text S1). Hierarchical clustering was carried out using similarity measure and the group-average method. values of each potential are specified on a color scale at the branches' tips, with specified by the outermost value. Branches are colored according to the 7 different potentials described in Fig. 3 (see also main text and Table 1). Green and blue stacked bars following the color-coded potentials, correspond to non-degeneracy and encodability, respectively. Boxplots, in black, represent the distribution of foldability values over non-degenerate genotypes for each map. Canonical potentials are the HP and AB models and their shifted versions (Fig. 2). They are highlighted with red dots.

https://doi.org/10.1371/journal.pcbi.1003946.g004

A first observation from Figure 4 is the impact of the potential on non-degeneracy, encodability and foldability, as well as the overall consistency of these properties across potentials with similar values. The potential can induce considerable differences in non-degeneracy and foldability. Confront, for instance, potentials type IV and potentials type II (green and orange branches, respectively). A similar observation applies in the case of clustering based on . In both cases, results are independent of the clustering method (Fig. S2, and Supplementary Methods).

A second general observation regards the abrupt changes in the use of phenotype space between some of the maps with potentials of the same type. While potentials type I, II and V (blue, orange and red branches, respectively) are highly clustered, potentials type III and IV (magenta and green branches, respectively), distribute across different clusters.

Figure 4 also reveals that canonical potentials are part of a larger family of potentials, which represent only 3 out of the 7 different types described above (Table 1; Fig. 3 and 4). Most notably, other combinations of values, in particular, potentials type I and II; induce sequence-structure maps that are as protein-like as the HP model (see below, section Foldability). Moreover, potentials that induce similar fractions of sequences and structures, present considerable variation in their average foldability.

I now turn to a closer look at these differences.

Non-degeneracy and encodability

Non-degeneracy () is the fraction of genotype space that yields viable, folding sequences. It ranges from 2 to 28% across maps generated by the binary potentials sampled in this study (green bars in Fig. 4). Similarly, encodability (c), the fraction of accessible phenotypes, varies from 1 to 19% (Fig. 4, blue bars). Both, and vary considerably across types of potentials (Fig. S3).

and are not independent and overall, correlate positively. Their association, however, depends on the type of potential (Fig. 5). In the case of potentials type I, II and IV, an increase in leads to larger c values. Potentials type III, however, preserve similar c despite large variation in . With the exception of few potentials type I and VI, maps induced by binary potentials, use a larger fraction of sequence than structure space (dashed line, Figure 5).

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Figure 5. Association between non-degeneracy and encodability.

For each potential sampled in this study, the plot shows non-degeneracy () versus encodability (c). Non-degeneracy corresponds to the fraction of genotype space that yields viable sequences; encodability, to the fraction of accessible conformations (see Models). Colors match the potentials types described in Fig. 3 and Table 1.

https://doi.org/10.1371/journal.pcbi.1003946.g005

Two main features of the potential account for and c. First, low negative values of , that is, average attractive homomonomeric interactions (0.0), promote both increasing and (see Fig. S4). The lowest values of are observed in the case of potentials types II and III. Second, positive values seem to be sufficient to promote , but not (Fig. S4 and S5). Potentials type I and II are the only potentials with positive values. They present encodabilities that are on average one order of magnitude larger than the rest of the potentials sampled in this study.

These two features provide some intuition as to why potentials type II and III reach large values of , but only type II present also large values of c (Fig. 5); whereas potentials type V show low and conserved values of and . The component of the potential does account for both 0.0 and 0.0. Therefore, and c are expected to correlate positively with (Fig. S4B, S4D).

As observed before, repulsive interactions reduce the average sequence degeneracy, increasing and [39]. However, our analysis of a large sample of potentials shows that not any type of repulsive interaction possess this effect, but only the heteromonomeric component of the potential, and that the effect is favored in the context of overall attractive .

Most notably, these observations suggest that, by controlling for the components of the potential, both, the fraction of sequence and structures can be increased and furthermore, optimized independently of one another. For instance, the average number of sequences per conformation (i.e. designability) can be optimized by increasing while keeping c constant, as is the case of potentials type III (i.e. increasing attractive interactions in both, homo and heteromonomeric components, Fig. 3 and 5).

The use of sequence and structure space

Although can be seen as the probability of finding a viable sequence, the distribution of sequences in genotype space is not uniform, and depends on their monomer composition.

Sequences can be classified according to their composition into classes. Compositional classes correspond to the frequency of the relative fraction of monomers across non-degenerate sequences induced by a given potential. In the case of maps composed of binary potentials, compositional classes distribute binomially. If all 2 sequences in the L18 model were non-degenerate, there would be 19 compositional classes, ranging from the unique two sequences composed of only one of the two monomer types (compositional classes 0 and 18 in Fig. 6; with 0 and 100 of monomer , respectively) to 48,620 sequences composed of 50 of each monomer (compositional class 9).

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Figure 6. Observed versus expected compositional classes of potentials types I to VI.

Compositional classes correspond to set of sequences with a given fraction of and monomers. A given compositional class contains 18- monomers type . Expected number of sequences per compositional class are estimated by sampling, for a given potential , random sequences from genotype space. Error bars represent one standard deviation from the mean. Colors code each potential type according to Fig. 3 and Table 1.

https://doi.org/10.1371/journal.pcbi.1003946.g006

In order to study the distribution of non-degenerate sequences across genotype space, I compare observed versus expected frequencies of different compositional classes. Expected compositional classes are estimated for a given potential , by sampling random sequences from genotype space, assuming that every sequence is equally likely to be non-degenerate.

Potentials present considerable biases toward certain compositional classes (Fig. 6). In particular, genotype spaces of potentials type I are enriched in monomers, with compositional classes near 61. In contrast, potentials type IV show significant deviations toward monomers. In addition, consistent with the abrupt transitions between similar potentials (, Fig. S1), potentials type III, IV and VI show considerable variation (error bars, Fig. 6).

Deviations from expected distributions can be explained by the proportion of attractive and repulsive values at homo versus heteromonomeric interactions (Fig. 3, Table 1). In the case of perfectly symmetric interactions between homo and heteromonomers, as is the case of potentials type II and V (Fig. 3, 6), there are no major deviations toward compositional classes enriched in either of the monomers. In these two cases, the diversity of repulsive and attractive interactions do not favor any compositional class. In the case of potentials type I and IV, however, one of the homomonomeric interactions breaks the symmetry of the potential, favoring the monomer that better counteracts stability respect to , increasing the diversity of competing interactions. Thus, potentials type I favor monomers type (0 and 0); whereas potentials type IV, monomers (0 and 0).

Similarly, deviations in structural space can be estimated by considering the distribution of number of contacts across the conformations induced by a potential (i.e. compactness). The distribution of expected number of contacts can be estimated by assuming that every uniquely encodable conformation is equally likely to be accessed by non-degenerate sequences. Therefore, for a given potential (), I sample conformations and calculate their number of contacts. Where , is the encodability of sequence-structure map , and , the set of uniquely encodable conformations of phenotype space (see Models).

All types of potentials deviate significantly from the expected distributions and in particular, compact conformations are more underrepresented than open ones (Fig. S6). Error bars indicate that deviations from expected distributions of contacts, are more consistent across potentials type I, V and VI. This is not the case of potentials type II, III and IV (Fig. S6).

Potentials type I favor structures with less number of contacts (i.e. open conformations), and types II deviate toward compact conformations. Figure S7 shows examples of the most and least common structures per type of potential. Notice the reduced number of contacts in potentials type I, even for the most common conformation (Fig. S7A). As shown before, repulsive heteromonomeric interactions (0) promote c (Fig. 3 and 5). In the case of an additional repulsive homomonomeric interaction (0 in potentials type I), the distribution of conformations shifts considerably towards open conformations (Fig. S6, I & II). A similar effect is observed by comparing potentials type III, IV and V. The addition of repulsive interactions in potentials type IV and V, have a slight impact on the unfavored open conformations observed in potentials type III (Fig. S6, III).

In summary, the potential energy function affects the monomer composition of non-degenerate sequences and the compactness of conformations. The symmetry of the potential, defined as the proportion of attractive and repulsive forces in homo versus heteromonomeric interactions, favors the unbiased use of genotype space and viceversa. Moreover, the relative increase of repulsive over attractive interactions, favors open conformations.

The designability of phenotypes

In the previous sections I observed that first, potentials vary in their propensity to induce the folding of sequences and structures. Second, potentials favor the viability of regions of sequence and structure space with biased sequence composition and compactness. Here I turn more closely to the relation between sequence and structure across maps. In particular, the relation between the number of sequences per structure, or designability (see Models).

Designability (C) is known to distribute heterogeneously over conformations [16], and this property of a phenotype, has important implications for protein evolution and design. Designable structures, those that map to many sequences, are more likely to be found by a random search across genotype space and are, by definition, more resistant to mutations.

In order to study C across the phenotype space of a sequence-structure map, I calculate the probability of finding, among non-degenerate sequences, a genotype that folds onto a phenotype with designability C or larger. Figure 7 shows such probabilities as logarithmic cumulative distributions for different types of potentials. As studied before, in the case of the HP model, the probability of finding a phenotype with C, distributes approximately exponential in the 2D lattice [16], [50]. I confirm this trend for potentials type I and II. Other potentials, however, deviate strongly from an exponential distribution.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Figure 7. Cumulative probability distributions of the designability of neutral sets for potential types I-VI.

For each sequence-structure map I calculate the probability of finding, among non-degenerate sequences, a genotype that folds onto a phenotype with designability C or larger. Here, designability is defined as the number of sequences per neutral set: C =  (see Models). Color codes according Fig. 3 and Table 1. Dashed black line, HP potential.

https://doi.org/10.1371/journal.pcbi.1003946.g007

In the case of potentials type I and II, the probability of finding sequences that map to increasingly designable phenotypes decreases fast compared to the rest of the potentials and is similar to the HP model (black dashed line, Fig. 7). The opposite is true for potentials type III and VI. For instance, in the case of potentials type I, the probability of finding a non-degenerate sequence that maps to a phenotype with C 10, is approximately 0.05; while in the case of potentials type III, with the same probability, one finds maps with C 110 sequences. Potentials type V, on the other hand, distribute narrowly and with probability 0.05, presents neutral sets of at least 40 sequences.

Different degrees of variation across potentials of the same type (e.g. contrast potentials type V and III), are the result of the differential distribution of and . For instance, potentials type III, that show increasing , while keeping relatively constant values of , present the broadest C distributions. In contrast, potentials type I, with increasing almost linearly with , the probability of finding larger C, decreases rapidly. In contrast, potentials type V present conserved values of and , which translates on narrower probability distributions (confront Fig. 5 and 7).

As suggested by a previous study, the identity of designable phenotypes is largely influenced by the potential [50]. As noted above, there is considerable overlap among the phenotypes induced by the potentials studied here. In order to explore this observation further, I group potentials according to their type, rank phenotypes by designability and consider the top and bottom 1 percentiles. There are only 122 conformations (2% of the average number of conformations per potential) encoded by every potential. There are no universally designable phenotype across the potentials studied in this work. I observe that with the exception of potentials type V, the most and least designable phenotypes are unique to each type of potential. Figure S7 shows examples of these phenotypes.

Recall that genotypes of the same neutral set () are not necessarily connected (see Models). Therefore, from an evolutionary standpoint, instead of and C, one should rather look at the size of neutral networks (C). The reason is that the connectivity of genotypes that are part of the same , allows them to mutate while preserving the same phenotype (). Here, the super and subscripts, stand for the neutral network of phenotype , in genotype component (see Models). Figure S8 shows the cumulative probability distribution of size, across maps. As expected, the probability of finding C, decays faster compared to C of neutral sets. This trend is particularly clear for potentials type II, III and V. In the case of potentials type III, for instance, the probability of finding neutral sets with 10 or more sequences, reaches values of 0.8; whereas finding neutral networks of similar size, only occurs at probabilities of 0.25. The trend is also evident for potentials type II and V. For instance, with probability of 0.05, one finds neutral sets of 20 and 40 sequences, respectively; whereas, with the same probability, one finds on average neutral networks of only 6 and 8 sequences, respectively. In contrast, the probability distributions of neutral networks and sets, are very similar in the case of potentials type I (see below). In both cases, with probability of 0.07, one finds cluster of sequences of approximately 10 sequences or larger.

These observations suggest that, in addition to variation on the available fraction of sequences and conformations (i.e. and ), there are considerable differences in C and C across potentials. Although different types of potentials induce similar sets of phenotypes, the identity of the most and least common phenotypes vary considerably. Additionally, potentials induce differential allocation of sequences across connected components (), which suggests influences on the size and distribution of neutral sets and neutral networks across genotype space. In the next section, I explore this aspect in more detail.

Networks of sequences and connected components in genotype space

As described in Models, non-degenerate sequences in genotype space can be construed as graphs. In order to investigate the impact of the potential on the distribution of sequences in genotype space from a network perspective, I look at the expected size of connected components (), neutral sets () and neutral networks () across different maps. I calculate the expected size of a cluster of sequences () from a collection of sets, x, as: ; where are particular instantiations in the set x: , or . simply computes the weighted average of sequences by their corresponding component size. Because every sequence is multiplied by its component's size; is equivalent to sum over the squares of the size of each component. If we were to choose a random non-degenerate sequence, from genotype space; would represent the expected size of the genotype component to which belongs; , the expected designability of its phenotype and , the expected neutrality of the neutral network associated to the same phenotype.

Figure 8 shows the distributions of and per type of potential. In order to compare maps generated by different potentials, I scale expected size by non-degeneracy (see legend of Fig. 8). Potentials type I, II and V, show genotype components that span on average 97, 99 and 93% of non-degenerate sequences, respectively (insets Fig. 8I, II, V). Note, however, that these distributions of expected size are generally due to the presence of a large genotype component. Figure S9 shows the distribution of the diameter () of genotype components per type of potential (see Models). While 60 to 90% of genotype components of potentials are composed of a single sequence ( = 0), all types of potentials show at least one large spanning genotype component ( = 18) (Fig. S9).

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Figure 8. Distribution of expected size of clusters of sequences in genotype space for potentials type I-VI.

For each sequence-structure map , generated by potential , plots present the expected size of sequence clusters (), where x is: or (see main text). Panels present the relative distribution of for potentials type I-VI. Distributions are normalized by , the non-degeneracy of sequence-structure map . Color code according to Fig. 3 and Table 1. Insets, relative distribution of expected size of genotype components (), normalized by the total number of non-degenerate sequences ( = ).

https://doi.org/10.1371/journal.pcbi.1003946.g008

In addition, potentials type I, II and V, as confirmed by designability of neutral networks in the previous section (Fig. S8), present small neutral networks mostly composed of 2 sequences (Fig. 8). Figure S10 shows the distribution of neutral networks diameter across potentials. Potentials type I and V do not show neutral networks with 9. Maximum diameter observed for potentials type II is 11.

In contrast to potentials type I, II and V; III, IV and VI, present genotype components and neutral networks that deviate towards smaller and larger expected size, respectively (Fig. 8, S9, S10). Although giant components dominate in the case of potentials type III and IV (Fig 8), they also show cases where genotype components' expected sizes reduce to 60 and 40% of non-degenerate sequences, respectively. In both cases the expected size of neutral networks increases up to 120 and 60 sequences, respectively (without scaling by ). Potentials type IV and VI present neutral networks of diameters up to 14 and potentials type III show cases of neutral networks that cross genotype space ( = 18).

Random graph theory predicts that the diameter of a neutral network (D()) is a function of the average neutrality of sequences that compose the network (see Models). The theory predicts the existence of a critical value [65]. If the average neutrality of sequences in a network of phenotype (), is larger than the critical value (), then, sequence in , percolate across genotype space and form a giant component. For a binary alphabet,  = 0.5.

Overall, potentials sampled in this work show low ( = 0.33) (Figure S11); and, the maximum diameter of neutral networks for potentials type I, II, IV, V and VI; are 9, 11, 14, 9, and 14, respectively (Fig. S10). Five potentials type III, however, present at least one neutral network with D = 18. Moreover, the average neutrality of these neutral networks is 0.15–0.19. There are at least 2 reasons for this disagreement with the theory. First, random graphs may not be a good approximation for neutral networks in the L18 model and/or potentials type III. Results presented in a previous section (i.e. the use of sequence and structure space), support this hypothesis. Second, it might be the result of finite size effects in the L18 model. In order to test the second hypothesis, should be calculated at the asymptotic limit [65], an analysis that is beyond the scope of this work.

Relative distribution of genotype components and networks

As explained in Models, sets of sequences that fold onto the same conformation (i.e. neutral set) can be composed of more than one neutral network (). Similarly, genotype components can be composed of more than one neutral set () (Fig. 1).

In order to explore these differences on the architecture of sequence-structure maps from a broader perspective, I look at and as a function of the number of genotype components () and number of neutral sets (), respectively (Figure 9). Each point in Figure 9 is a sequence-structure map induced by a potential of a given type (color code, Fig. 3, Table 1).

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Figure 9. Number of genotype components and neutral sets versus the expected size of neutral sets and neutral networks.

(A) Number of genotype components versus the expected size of neutral sets. (B) Number of neutral sets versus the expected size of neutral networks. Expected size of () and (), are calculated as the weighted average of sequences across neutral sets and neutral networks, respectively (see main text). Color code according to Fig. 3 and Table 1

https://doi.org/10.1371/journal.pcbi.1003946.g009

The number of and , vary approximately one order of magnitude across different potentials. However, compared to , there are ten times more (Fig. 9). As the number of increases, the space gets partitioned into more components and the expected designability of phenotypes () decreases proportionately (Fig. 9A). Potentials type I show few number of components (100–400) that contain on average, a large number of neutral sets (5,000–10,000 - Fig. 9B), of small expected size (10 sequences - Fig. 9A). Similarly, potentials type II (and V), induce maps with fewer (and larger) , with relatively larger (and smaller) , respectively (Fig 9B). Potentials type I, II and V show, on average, small (i.e. low neutralities).

In contrast, potentials type III and IV show genotypes components of vastly different sizes. These potentials are enriched on sequences of the same phenotype and consequently, their maps show low encodabilities (x-axis, Fig. 9B). Strikingly, the expected designability of some potentials type III, decreases almost linearly as function of the decimal logarithm of , approximately as 15% per order of magnitude (Fig. 9A). The number of decreases rapidly once encodability reaches values of 5,000 phenotypes (Fig. 9B).

The ratio of the expected size of different sequence clusters shows that genotype components are approximately 1,000 to 3,000 fold larger than the expected size of an average neutral set across potentials (/1,000–3,000) (Figure 10A). Although in general the expected size of an average neutral network follows a similar proportion, potentials type II and V, show large deviations, with genotype components: / 9,000 to 12,000 fold larger than the expected size of neutral networks. These ratios are particularly well conserved across potentials type V (Fig. 10A).

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Figure 10. Ratio between expected size of sequence clusters for different types of potentials.

(A) Ratio between the expected size of genotype components () and neutral networks () in black. Ratio between the expected size of genotype components () and neutral sets () in blue. (B) Ratio between the expected size of neutral sets () and the expected size of neutral networks (). Color code as in Fig. 3 and Table 1. The expected size of a cluster of sequence is calculated as the weighted average of sequences per cluster size (see main text).

https://doi.org/10.1371/journal.pcbi.1003946.g010

A similar analysis comparing the expected sizes between neutral sets and neutral networks, shows major differences across potentials (Fig. 10B). Strikingly, and as anticipated (see section the designability and neutrality of phenotypes), potentials type I show exclusively fully connected neutral sets (/ 1). In contrast, potentials type V present neutral sets on average 5 to 6 times consistently larger than the expected neutral network. With the exception of potentials type II, that shows on average 4 to 5 neutral networks per phenotype (Fig. 10B); the rest of the potentials show large variation with predominantly 1 to 2 neutral networks per phenotype.

In summary, potentials type I, II and V, induce sequence-structure maps of relatively similar organizations. These potentials show large genotype components and on average few sequences per phenotype. With the exception of potentials type V, however, I and II show on average few genotype components.

Potentials type I show neutral sets composed of a single neutral network and on average, 3,000 networks per genotype components. As seen before, these networks possess short diameters. Similar to potentials type I, type II show approximately 3,000 neutral sets per genotype component. These types of potentials, however, show on average, neutral sets 4 times larger than the expected size of a neutral network. Potentials type V, on the other hand, show on average, 1,800 neutral sets per genotype component and these neutral sets are consistently composed of 5.5 to 6 times more neutral networks.

In contrast, potentials type III, IV and VI, induce sequence structure maps with genotype components and neutral sets of a wide variety of sizes. These potentials show long-tailed distributions of neutral networks per phenotypes, with on average 1 to 2 networks per neutral set. In addition, they show approximately 1,000 to 2,000 neutral sets per genotypes component. While potentials IV and VI reach neutral sets and networks of expected size up to 70 sequences, potentials type III shows neutral networks of up to 120 sequences.

The phenotypic diversity of genotype neighborhoods

Although the distribution of sequences in genotype space, and in particular of neutral networks, informs on the abundance of phenotypes and their expected mutational robustness, it does not tell us about the mutational divergence between different phenotypes. The differential accessibility to phenotype variants across genotype space has a profound impact on the ability of sequences to produce new, unobserved phenotypes.

In order to study the relative accessibility of sequences to new phenotypes, I consider the phenotypic diversity of a pair of -neighborhoods centered at and (, ) (see Models). I calculate the overall fraction of phenotypes unique to each of the two k-neighborhoods at distance , and constant , as: . measures the overall diversity of two phenotype neighborhoods as a function of their divergence in genotype space. Note that non-overlapping k-neighborhoods only occur at [8], [66].

Figure 11 presents and as a function of distance for potentials type I-VI. At very short distances (with even overlapped neighborhoods), shows 50 to 70% of unique phenotypes (Fig 11A). As expected, at short and larger , decreases as a function of (Fig. 11B). In the case of 2-neighborhoods, the fraction of unique phenotypes increases rapidly with distance and, at short , there are only slight differences between types of potentials. At the overlapping threshold of (, dashed line Fig. 11), approximately 85 to 95% of phenotypes are unique to pairs of neighborhoods. At larger distances, however, differ considerably across potentials. For instance, at , potentials type I access 2-neighborhoods with 100% new phenotypes; whereas, distant 2-neighborhoods of potentials types II, III, IV and VI, share from 10 to 15% phenotypes. This trend intensifies in the case of potentials type V, that reach similar values compared to 2-neighborhoods at short distances (Figure 11A).

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Figure 11. Fraction of new phenotypes across k-neighborhoods at distance d.

For each of the 245 potentials analysed in this study (Table S1 in Text S1), I draw 1,000 random non-degenerate sequences and for each pair of sequences (), calculate , and , at constant k and variable distances d. I average values according to their type of potential (I-VI) (color code, see Fig. 3 and Table 1). (A) k = 2. (B) k = 4. Error bars represent one standard deviation from the mean. Grey dashed lines illustrate the overlapping threshold: .

https://doi.org/10.1371/journal.pcbi.1003946.g011

In the case of larger -neighborhoods, differences between potentials discussed above become more evident (Fig. 11B and S12). Strikingly, potentials type I consistently find unique phenotypes at . In stark contrast, potentials type V, recover completely the levels of observed at short distances in a fairly symmetric pattern (Fig. 11B, S12).

In order to further explore these differences I look at maximal distances () between sequences that are part of the same neutral set, that is, sequences that fold onto the same phenotype. Figure S13 shows such distributions per type of potential. As expected, potentials type I show short maximal distances, with hardly larger than 7 point mutations. In contrast, all other potentials show phenotypes at varying distances and sequences at opposite sides of genotype space ( = 18). In particular, potentials type II, IV and VI show 40 to 60% of phenotypes with  = 18. Consistent with the patterns observed in Fig. 11 (and S12), potentials type III and V show on average, 70 and 97% of phenotypes with  = 18, respectively (Fig. S13).

The existence of sequences at can be explained by the degree of symmetry between attractive and repulsive interactions in the potential. A sequence folds onto its native conformation by stabilizing a set of contacts (2 to 10 in the case of the L18 model). In the case of a completely symmetric potential (as type V), sequences in opposite sides of genotype space, those with every position mutated by the opposite monomer, would preserve the same fraction and type of interactions, and therefore stabilize the same phenotype. In contrast, an asymmetric potential, as potentials of type I, with a single homomonomeric attractive interaction, will populate phenotypes at biased compositional classes. As these observations predict, potentials type III, a fully symmetric potential with no competing interactions, stabilizes sequences at a varying range of distances (Fig. S13).

In summary, potentials induce maps with variable degrees of phenotypic diversity and divergence between neighborhoods. At short mutational distances, there is a large fraction of phenotypic diversity and these values are consistent across types of potentials. At moderate and long distances, however, potentials differ extensively in the distribution of unique phenotypes and those differences are due to the symmetric distribution of the potential's attractive and repulsive forces in homo versus heteromonomeric energy terms.

Foldability

Not all non-degenerate sequences are guaranteed to fold readily onto their native conformations. The propensity of a polypeptide to fold fast is an important determinant of how protein-like is a random sequence [67]. Next, I look at the impact of the potential on foldability (), a measure of a sequence's propensity to fold (see Models).

Foldability is very sensitive to parameters in the potential. As shown in Figure 4, varies extensively across sequence-structure maps, even among those induced by potentials of the same type (see Fig. S14). Min and max median values are −8.2 and −2.3, respectively (the lowest the foldability, the faster the folder - see Eq. 2). Similar values of foldability are also observed to correlate very well with the accessible set of genotypes (Figure S1). The canonical potential HP has a notorious long-tailed distribution biased towards fast folders. This is however not a peculiarity of the HP model, and similar protein-like sequence-structure maps are observed in the case of potentials type I, II and other potentials type VI (Fig. 4 and S1). In addition, variation on the foldability of maps induced by the same potential type, suggests that foldability is highly sensitive to changes on the potential (confront for instance, potentials type I or II in Fig. 4 and S14).

Evidence from the theory of protein folding relates foldability to cooperativity or the non-additivity of interactions [15]. In the context of binary potentials, I measure additivity () as deviations of excess from the ideal part of the potential (see Models). Figure 12 presents the median across all non-degenerate sequences of each sequence-structure map, as a function of . In the case of a completely additive potential: (dashed lined at ).

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Figure 12. Foldability as a function of a potential's additivity.

Foldability was calculated using Eq. 2. Additivity, as described in Models. Values refer to the median foldability across non-degenerate sequences for a given potential. Shaded circles correspond to a single potential colored as defined in the legend (see Fig. 3 and Table 1). Black dots represent potentials type VI. Dashed lines illustrate additive potentials (; ).

https://doi.org/10.1371/journal.pcbi.1003946.g012

The association between and for potentials type I-V is delineated by the foldabilities of potentials type VI (black dots in Fig. 12). This is due to the fact that transitions between types of potentials occur whenever 0.0 (grey planes in Fig. 3). Sequence-structure maps that favor foldability are induced by HP-like energy functions, which include potentials type I, II and VI.

Not every potential that deviates significantly from additivity ensures a foldable map. Figure 12 shows that the extent to which additivity dictates the overall of a map, is a function of the type of interactions present in the potential. For instance, potentials type II and III reach better as ; whereas in the case of potentials type V, when .

In summary, our observations confirm the impact of a potential's non-additive interactions on favoring protein-like sequences. I observe that the role of non-additivity is highly dependent on the form of the potential and that different potentials can induce maps as protein-like as the canonical HP model. HP-like sequence-structure maps are particularly induced by potentials type I and II. Most notably, this analysis suggests that by controlling for the form of the potential, it is possible to design a map with a desired fraction of protein-like sequences.

The binary potential energy functions of natural amino acids

How random are the pairwise interactions observed in the natural amino acid alphabet? I assess this question by comparing the pairwise interactions of amino acids in the Miyazawa-Jerningan (MJ) potential (Table VI in [29]), to the unbiased random sample of potentials studied in previous sections.

I start by counting all pairs of natural amino acids in the MJ potential (i.e. 190), and classify them according to the definition in Fig.3. The MJ potential presents all 7 types of potentials analyzed in this work. Because of its continuous energy values, there are only six binary potentials with neutral interactions (i.e. type VI), and for convenience, I neglect them in this analysis.

According to Fig. 3, an homogeneous sample from the space of binary potentials produces potentials type I:II:III:IV:V:VII in the ratio 2∶1∶1∶2∶1∶1. The histogram in Fig. 13, shows a comparison between expected versus observed types of binary potentials in the MJ energy function.

Download:

• PPT
  PowerPoint slide
• PNG
  larger image
• TIFF
  original image

Figure 13. Hierarchical clustering of phenotype spaces generated by binary sequence-structure maps of a statistical potential derived from natural proteins.

Values of the pairwise potentials for natural amino acids were obtained from the Miyazawa-Jernigan potential, Table VI [29]. (See legend of Figure 4 and main text).

https://doi.org/10.1371/journal.pcbi.1003946.g013

This analysis shows that natural amino acids tend to avoid purely repulsive potentials (type VII) as much as they promote HP-like potentials (type I and II). Strikingly, there is a strong overrepresentation of potentials type III, approximately equivalent to the overall underrepresentation of potentials type IV and V.

In order to gain further insights on the properties of binary combinations of natural amino acids, I perform a similar analysis as the one reported in Figure 4 (see Figure S15).

In contrast to Fig. 4, the clustering of sequence-structure maps of binary potentials of natural amino acids seems more homogeneous. Similar to our previous observations, non-degeneracy ranges from 2 to 34% and encodability, from 1 to 21%. Several sequence structure maps reflect good foldabilities. These maps usually involve strong interactions such as Cys. Sequence-structure maps with different degrees of protein-likeness are observed in the case of potentials type I, II, IV and VI.

The purpose of this analysis is not to argue that these binary potentials reflect the architecture of the sequence-structure map of natural proteins; but to suggest that, if the combination of potentials can be approximately considered additive, then combinations of these binary interactions may indeed reflect some of the properties of sequence-structure maps induced by larger alphabets. Indeed, random libraries composed primarily of 3 amino acids, such as AEK [68] and QLR [57], can be decomposed into potentials type I, II, IV; and I, I, V; respectively.

In summary, these results show that the types of binary potentials observed in an unbiased sample of the space of energy functions, are represented in the interactions of natural amino acids, as described by the MJ potential. The types of potentials overrepresented in proteinaceous amino acids are potentials characterized as HP-like. Furthermore, these analysis suggest that random libraries enriched in HP-like potentials, are likely to favor protein-like sequence-structure maps.