Overview of the algorithm

The list of 'non-polar groups' in proteins and nucleic acids.

An 'indivisible unit' of the hydrophobic interaction is an atomic group that includes one carbon or sulfur atom and covalently bound hydrogen atoms. In proteins and nucleic acids those groups are -CH3, -CH2-, -CH=, -SH, and -S- groups.

The program uses two variants of the list of non-polar groups. The extended list includes all such groups in protein and nucleic acids, the strict list includes those groups of extended one, whose main atom is covalently bound only with another carbon or sulfur atoms (and, thus, is not covalently bound with any polar atom).

The center of a non-polar group is the center of the carbon or sulfur atom. Hydrogen atoms are not considered in calculations.

The graph of interactions of non-polar groups in a 3D structure.

Each non-polar group corresponds to one vertex of the graph. Two vertices are connected by an edge (and are suppose to be in interaction) in the case if (a) the distance between the centers of the groups does not exceed the threshold value d; (b) the interaction of these groups is not prevented by any other (polar or non-polar) group. We say that a group C prevents the interaction between non-polar groups A and B, if the ball with the center C and the radius R_C includes the intersection of the balls with the centers A and B and the radii R_A and R_B, respectively. In the program all radii are equal to 2.7 Å, which corresponds to the minimal possible distance from a carbon-generated non-polar group to the oxygen atom of a water molecule. The value of d is a user parameter. Maximal vreasonable value of d is 5.4 Å, which corresponds to the sum of R_A and R_B radii in the case of carbon non-polar groups (roughly speaking, the hydrophobic interaction occurs if a water molecule cannot be placed between two non-polar groups).

Edges of the graph reflect two sufficiently different types of relations between atomic groups: (i) 'fixed' groups (including covalently bound ones); (ii) groups that are nearby located due to the hydrophobic interactions. Two non-polar groups A and B are 'fixed', if the distance between them is fixed due to chemical bonds, or any other interaction with energy exceeding sufficiently the free energy of the hydrophobic interaction between the groups. The examples of fixed non-polar groups are two groups, the central atoms of which are covalently bound with some third atom, or any two groups of aromatic ring. In the described algorithm and program these two different types of edges are not distinguished.

The graph of interactions of non-polar groups is denoted by Γ.

The definition of a (K,L)-cut of the graph Γ

Fig. 1. Connected 2-edges subgraphs (thick lines) representing (a) (2, 1)-cut; (b) non-(2, 1)-cut. Vertices of 1-neighbourhood of the subgraphs are in dark grey. In (a), after the removal of thick edges from 1-neighbourhood the obtained subgraph is decomposed into 2 connected components. In (b), the analogous procedure gives a connected subgraph.

The algorithm of exhaustion of connected subgraphs of ≤ K edges

The algorithm starts with the exhaustion of all subgraphs of one edge. Then for each subgraph Δ all 1-extensions of Δ are considered. The procedure iterates K–1 times. It can be proved that each connected subgraph of ≤K edges is considered by the algorithm exactly ones.

The algorithm for the hydrophobic clusters detection

Fig. 2. The planar illustration of (K,L)-cut algorithm. (a) The initial distribution of non-polar groups. (b) The graph of interactions of non-polar groups. (c) All (1,1)-cuts in the graph. The edges of (1,1)-cuts are thick ones. (d) The graph after removal of all (1,1)-cuts. An example of one (2,1)-cut is presented (thick edges). The clusters, found after the removal of (1,1)-cuts and one (2,1)-cut, are subscribed.

The algorithm works as follows. At the first step the graph Γ of interactions of the non-polar groups is constructed (see Fig. 2b). At the second step all (K, L)-cuts in the graph Γ are found (Fig. 2c). If a subgraph with t<K edges is a (K, L)-cut, then larger subgraphs including this (K, L)-cut are not considered: the process of connected subgraphs exhaustion (see above) stops extending a subgraph if it is proved to be a (K, L)-cut. At the third step all edges of found (K, L)-cuts are removed from the graph (Fig. 2d). At the fourth step the connected components of the obtained graph are found. The vertices of each connected component that contains not less than m non-polar groups form a hydrophobic cluster. For every hydrophobic cluster the additional parameters (see further) are calculated. The found hydrophobic clusters, ordered in accordance to the number of non-polar groups, form the output of the algorithm.

For graphs of interacting non-polar groups the algorithm is linear in the number N of atoms in a given structure, because the number of interactions of a non-polar group with other groups is obviously restricted. The constant in this linear function is rather big and depends on K exponentially. Fortunately, only small K=1, 2, 3 are expected to be sufficient for reasonable hydrophobic cluster detection.

In the program realization the values K=1, L=1, m=3 are fixed.

Parameters of hydrophobic clusters