# The Origin of the Designability of Protein Structures

## Introduction

Natural proteins fold into unique compact structures in spite of the huge number of possible conformations. For most single domain proteins, each of these native structures corresponds to the global minimum of the free energy.

It has been proposed phenomenologically that the number of possible structures of natural proteins is only about one thousand, which suggests that many sequences can fold into one preferred structure. There have been theoretical studies for the existence of such preferred structures .

In many of theoretical studies for the protein folding, a simplified model called HP model  is adopted. HP model is one of 2-letter codes lattice models where a protein is represented by a self-avoiding chain of beads placed on a lattice, with two types of beads, hydrophobic(H) and polar(P). In the HP model, the energy of a structure is given by the nearest-neighbor topological contact interactions as

$$H=\underset{i<j}{}E_{\sigma _i\sigma _j}\mathrm{\Delta }(r_ir_j)$$
(1)   
where $`i`$ and $`j`$ are monomer indexes, $`\{\sigma _i\}`$ are monomer types ($`\sigma =`$ H or P); $`\mathrm{\Delta }(r_ir_j)=1`$ if $`r_i`$ and $`r_j`$ are topological nearest neighbors not along the sequence, and $`\mathrm{\Delta }(r_ir_j)=0`$ otherwise.

Based on the HP model, a concept of designability has recently been introduced; the number of sequences that have a given structure as their non-degenerate ground state (native state) is called the designability of this structure. When many sequences have a common native structure, one say that the structure is highly designable. Adding to the importance in the protein design problem, the designability also have evolutional significance because highly designable structures are found to be relatively stable against mutations.

In the original study of H. Li et al., HP models on the square and cubic lattices are employed, with the energy parameters in eq.(1) being $`E_{HH}=2.3,`$ $`E_{HP}=1.0,`$ $`E_{PP}=0.0`$. For each sequence, they calculated the energy over all maximally compact structures and picked up the native structure. The results indicated that highly designable structures actually exist on both lattices.

A. Irbäck and E. Sandelin studied the HP models on the square and triangular lattices. They adopted different energy parameters from H. Li et al. , namely, $`E_{HH}=1,`$ $`E_{HP}=E_{PP}=0`$. In the calculation of the designability, they considered all the possible structures, not restricting to the maximally compact ones. For the square lattice, they confirmed the existence of the highly designable structures as in Ref.. For the triangular lattice, however, no such structures were found. In addition to the nearest-neighbor topological contact interactions, they considered local interactions represented by the bend angle and calculated the designability. Indeed the local interactions reduced degeneracy (i.e., the number of sequences which have non-degenerate ground state increased) and made the designability higher. But they found that the designability on the square lattice was still much higher than that on the triangular lattice. They concluded that the difference in the designability for these two lattices are related to the even-odd problem, that is, whether the lattice structure is bipartite or not.

Quite recently, H. Li et al. proposed a new model based on the HP model on the square lattice . In the model, the hydrophobic interaction is treated in such a way that the energy decreases if the hydrophobic residue is buried in the core. They justify this treatment in two reasons: (1) the hydrophobic force which is dominant in folding  originates from aversion of hydrophobic residues from water. (2) the Miyazawa-Jernigan matrix  contains a dominant hydrophobic interaction of the linear form $`E_{\alpha \beta }=h_\alpha +h_\beta `$ . They took

$$H=\underset{i=1}{\overset{N}{}}s_ih_i$$
(2)   
where $`\{h_i\}`$ represent a sequence : $`h_i=1`$ if the i-th amino acid is H-type and $`h_i=0`$ if it is P-type. And $`\{s_i\}`$ represent a structure : $`s_i=0`$ if the i-th amino acid is on the surface and $`s_i=1`$ if it is in the core. They calculated the designability over all maximally compact structures, whose result is consistent with their former study \[See Table. I \].

In our view, there are many points to be explored further for the designability problem. First, since the structures of natural proteins are compact but not necessarily “maximally compact” in general, how can we justify the discussion where only the maximally compact structures are taken into account? Second, is it adequate to consider only nearest-neighbor interactions? Properties of a system with only nearest-neighbor interactions are directly affected by the lattice structure, in particular, whether the lattice is bipartite or not. Is it good, only from these facts, to conclude immediately that the absence of the highly designable structures on the triangular lattice should be ascribed to the even-odd problem associated with the triangular lattice? One should discuss the problem on the triangular lattice by using a model like the one in Ref. where the interactions do not depend on the contact between monomers, hence, do not directly reflect the non-bipartiteness.

Our aim of this paper is to examine the above points and clarify what determines the designability of protein structures. We use a new model with a 2-letter codes (H and P) on the square and triangular lattices and calculate the designability over all possible structures. In our model, based on Ref., the energy increases if the hydrophobic residue is exposed to the solvent. We will call this model “solvation model”. In brief, the solvation model is a 2-letter codes lattice model where the hydrophobic force to form a core is dominant and the interactions do not directly reflect the bipartiteness. Using the solvation model and the HP model, we investigate model-independent properties of designability.

## The Models

In the solvation model, based on Ref. , a protein is represented by a self-avoiding chain of beads with two types H and P, placed on a lattice. A sequence is specified by a choice of monomer types at each position on the chain.

We used two-dimensional lattice models because a computable length by numerical enumeration of the full conformational space is limited (square lattice : 18, triangular and cubic lattices : 13). Even with this chain-length limitation, we can make a “hydrophobic core” in two dimensions, in contrast with the three-dimensional case.

A structure is specified by a set of coordinates for all the monomers and is mapped into the number of contacts with the solvent. In our model, the total energy is given in terms of the monomer-solvent interactions, and depends only on the number of contacts with the solvent:

$$H=\underset{i=1}{\overset{N}{}}E_{s_i}h_i$$
(3)   
where $`\{h_i\}`$ represent a sequence : $`h_i=1`$ if the i-th monomer is the H-type and $`h_i=0`$ if it is P-type. The variable $`s_i`$ denotes the number of contacts with the solvent, for example, $`s_i=\{0,1,2,3\}`$ on the square lattice and $`s_i=\{0,1,2,3,4,5\}`$ on the triangular lattice. In other words, $`s_i=0`$ means that the $`i`$-th monomer is buried away from the solvent. We take $`E_0=0,`$ $`E_1=\sqrt{2},`$ $`E_2=\sqrt{7},`$ $`E_3=\sqrt{13},`$ $`E_4=\sqrt{19},`$ $`E_5=\sqrt{23}`$. That is, the possible minimum energy is zero. And these parameters are selected so that the larger the number of contacts with the solvent is, the more the degree of energy increase is; the hydrophobic residue is energetically unfavorable to be at the corner. Although the choice of these values is somewhat arbitrary, we have considered the following points: (1) these values should not increase too much rapidly with the increase in the number of contacts with the solvent, and (2) the way of choosing these values must not bring about nonessential accidental degeneracies (due to simple rational ratios between the parameters) .

Using the model on the square and triangular lattices, we calculate the designability for all the $`2^N`$ sequences, where $`N`$ is the number of monomers, by exact computer-enumeration method over the full conformational space. To get correct data, we exclude overcounting coming from redundant structures which are mutually related by rotation, reflection and reverse-labeling.

On the basis of data obtained by the solvation model and the HP model, we examine what determines the designability from three points of view: (1) the effect of the search-space restriction, namely, the search within maximally compact structures (in this paper, we just used maximally compact structures as a simplest example of the search-space restriction, and we may consider other one, e.g., structures with the biggest core), (2) the effect of the lattice structure, namely, whether the lattice is bipartite or not (or, equivalently, the even-odd problem), (3) the effect of the number of monomers (or, the length of the chain).

## Results and Discussion

Let us now give results of calculations.

(1) The effect of the search within maximally compact structures

In Fig. 1, we show the designability calculated on the square lattice for $`N=16`$, using maximally compact structures. For comparison, in Fig. 2, we show the designability of the same system without the search-space restriction (i.e., search over all possible structures). In both cases, there are some highly designable structures. However, these structures are not common to both cases. In Fig. 2, the number of sequences that have native structures is 8277, but the number of sequences that have maximally compact structures as native is only 1087 out of 8277. That is, most sequences that have native structures have non-maximally compact structures as native. The importance of non-maximally compact structures has also been pointed out for the HP model . These facts imply that it is not good to calculate the designability over only maximally compact structures. Such calculation picking up a “native” structure out of maximally compact structures, is not correct if the true native structure is non-maximally compact. Further, when the lowest-energy non-maximally compact structure and the lowest-energy maximally compact structure are degenerate, there is no native structure (native structure must be non-degenerate), but the restricted-search-space calculation gives a false result that there is a native (and maximally compact) structure. We should say that the designability calculated over only maximally compact structures may be erroneous.

(2) The effect of the lattice structure: bipartite or non-bipartite

In two previous studies using the HP model , interactions of the system directly reflected whether the lattice is bipartite or not. Moreover the designability on the triangular lattice was calculated with the energy parameters in eq.(1) being $`E_{HH}=1,E_{HP}=E_{PP}=0`$, which would cause accidental degeneracies. In their results, highly designable structures were not found for the triangular lattice. Also, it seemed that native structures are likely to contain the hydrophobic core where a group of hydrophobic monomers contact with each other; such contact can be made only if the distance between the monomers along the sequence is odd. Therefore, the bipartiteness has been thought to be a main source of the designability.. If so, highly designable structures do not actually exist, i.e., the concept of designability itself could be meaningless. On the other hand, if such preferred structures should exist on the basis of the proposal by C. Chothia , the use of the lattice model would be inadequate. Then, we used the solvation model, which does not directly reflect the bipartiteness, and calculated the designability on the square and triangular lattices. Besides, we also calculated the designability on the triangular lattice using the HP model, with the energy parameters being $`E_{HH}=2.3,E_{HP}=1.0,E_{PP}=0.0`$.

In Table. II, we show the total number of sequences that have non-degenerate ground state ($`S_n`$) and the highest designabilities ($`D_h`$) on the triangular lattice for $`N=13`$, obtained by using different interactions. This result shows that, even if we take different values of energy parameters, or even if we use the solvation model, the triangular lattice is still unfavorable for the designability although $`S_n`$ varies largely. On the other hand, for the square lattice, highly designable structures are found in the solvation model as well as in the HP model (Fig. 2). These results imply that the absence of the highly designable structures for the triangular lattice should not be ascribed to the even-odd problem (or, the non-bipartiteness), but to other reasons. The properties that highly designable structures are found on the square lattice and no such structures are found on the triangular lattice might be general in 2-letter codes lattice models where the hydrophobic force is dominant.

(3) The effect of the number of monomers

Then, why are the highly designable structures absent for the triangular lattice? Smallness of number of monomers (in other words, the length of a chain is too short), may be a possible reason. Important object in the protein structure is the hydrophobic core which consists of buried monomers in no contact with the solvent. Recall that the limit of a computable length by exact enumeration of the full conformational space on the triangular lattice is 13. The biggest core which we can make by using this limited length is the one which consists of only three monomers; the length is too short for the hydrophobic force to form a core. This monomer-number effect is also found on the square lattice. Consider the following conditions: at least ten sequences have a given structure as their native state, and at the same time, there are at least five such structures. Only if these conditions are satisfied, let us say that “there are highly designable structures.” Then, at $`N=10`$ or less, there are no highly designable structures even for the square lattice \[Table. III, Table. IV\]. This result implies that, when we discuss whether there are highly designable structures or not, we need a long chain enough to make a core of enough size. This further implies that, in three-dimensional case, we will need a chain of longer length than that in two-dimensional case to make a core.

Let us see Table. III, Table. IV and Table. V. In Table. V, we show the designability calculated on the triangular lattice for $`N=13`$. On the square lattice for $`N=10`$, the biggest core consists of two monomers. Both on the triangular lattice for $`N=13`$ and on the square lattice for $`N=11`$, the biggest core consists of three monomers. We see that the triangular lattice is unfavorable for designability compared with square lattice, even when the biggest possible core size is same or a little larger. A possible reason would be the number of all possible structures, particularly the number of structures with the biggest core. As the length of a chain becomes long, the number of all possible structures increases almost exponentially as $`\mu ^N`$ ( $`2<\mu <3`$ for the square lattice, and $`4<\mu <5`$ for the triangular lattice). On the triangular lattice for $`N=13`$, the number of all possible structures is 6,279,601 and the number of structures with the biggest core is 4,110 out of them. On the other hand, on the square lattice for $`N=10,11`$, the number of all possible structures is 2,034, 5,513 and the number of structures with the biggest core is 23, 5, respectively. Thus the number of all possible structures and the number of structures with the biggest core on the triangular lattice are much larger than those on the square lattice . In consequence, the degeneracy tends to grow, which is unfavorable for designability. In this view, designable structures on the triangular lattice would be more difficult to appear than on the square lattice.

## Summary

We have calculated the designability of the protein structure using the solvation model and the HP model, to deduce model-independent properties of designability. The solvation model introduced in this paper satisfies two conditions: (1)the hydrophobic force is dominant, (2) the model does not directly reflect the bipartiteness. We have examined what determines the designability from three points of view: effect of restricted search within maximally compact structures, the bipartite/non-bipartite effect, the length of the chain.

In result, we have found that it is inadequate to calculate the designability within maximally compact structures. Our results imply that the reason why no highly designable structures on the triangular lattice have been found is not the non-bipartiteness. We suppose that the main factor which affects the designability is the chain length, because for sufficiently large hydrophobic core to form, long enough chains are required. Triangular lattice is more unfavorable for the designability than square lattice irrespective of models or energy parameters, probably because the number of all possible structures is large. However, if we can deal with longer chain than in the present study, it is possible that we find highly designable structures even on the triangular lattice. The calculations of the designability for longer chains on the triangular lattice are highly desirable. These conclusions would apply to a wide variety of 2-letter codes lattice models, where the hydrophobic force is dominant, regardless of energy parameters and further details of the model.

Though a concept of designability is currently defined for a 2-letter codes lattice model, our final goal is to examine whether natural proteins have highly designable structures. Therefore it is an interesting problem to extend the study of the designability for a 20-letter codes model (e.g., MJ model, KGS model) and an off-lattice model. Substituting 20-letter codes for 2-letter codes certainly reduces degeneracy, and most of all sequences come to have a structure as non-degenerate ground state (i.e., native structure).

## Acknowledgements

We would like to thank Y. Akutsu and M. Kikuchi for useful discussions and careful reading of the manuscript.