BACKGROUND
the process of protein folding whereby a linear polypeptide chain reaches its native structure has been one of the most intensely studied biomolecular problems over the past  <dig> years .
folding of a protein is usually pictured as a search for the native conformation within the conformational space of all possible conformational states, each characterized by a set of parameters.
even though most of the conformational states are not accessible to experiment, graphic representations of the potential energy surface have played pivotal roles in explaining how the conformational space is gradually restricted during the process folding  <cit> .
key concepts such as folding pathways  <cit>  are also best explained by graphic representations.
the particular kind of folding that this article is concerned with is oxidative folding, which is the fusion of native disulfide bond formation with conformational folding  <cit> .
this complex process is guided by two types of interactions: first, non-covalent interactions giving rise to secondary and tertiary structure, and second, covalent interactions between cysteine residues, which ultimately transform into native disulfide bridges.
the process of disulfide formation is a simple chemical reaction in which two sh groups join to form a disulfide link .
if the sh groups are on a polypeptide chain, the in vitro reaction can be promoted by an external redox system such as a mixture of oxidized and reduced glutathione, or cysteine and cystine, respectively.
in vivo, the oxidative power comes from specific agents such as the molecular chaperones protein disulfide isomerases <cit> .
the underlying chemical mechanism is disulfide interchange .
in this scheme there are two kinds of reactions: i) in a redox reaction a protein disulfide bond is created , i.e.
the oxidative state of the polypeptide is changed.
this is the case when one of the participants of the reaction  is not part of the protein.
ii) in a shuffling reaction both participants of the reaction are protein-bound, so the oxidative state of the polypeptide does not change.
in view of these possibilities it becomes obvious that there are a great many ways in which disulfide bridges can form and rearrange during the folding process.
today it is generally accepted that non-covalent interactions guide the process of folding and formation of disulfide bridges will lock the protein into the right conformation.
the advantage of oxidative folding as opposed to general protein folding is that disulfide intermediates can be chemically isolated and studied using such techniques as acid trapping of the intermediates and analysis of the disulfide bridges using a combination of enzymatic cleavage and mass spectrometry.
there is a body of literature in describing the pathways of oxidative folding in terms of disulfide intermediates  <cit> , and our goal is show how graph theory can be used to visualize them.
graph theory has been applied to many aspects of protein research .
the applications followed two broad avenues:
i) first, protein structure itself can be considered as a graph consisting of various interactions  as edges, the nodes being atoms or residues of the protein.
for instance, one of the classical definitions of protein secondary structures is based on main/chain h-bond contacts between residues  <cit> .
structural neworks have been used in folding research as well.
it was found, among others, that the so-called contact order, i.e.
the average sequence distance between residues in atomic contact, seems to be a key determinant of folding speed  <cit> .
another line of research concentrates on characteristic networks of inter-atomic contacts that may form stabilization centres in protein structures and can be the reason of the differential stability of various proteins  <cit> .
it was found that populated conformations seen in molecular dynamics simulations contain characteristic networks of residues  <cit> .
ii) in the network descriptions of the folding space, on the other hand, the folding states are the nodes, and transitions are the edges between them.
this approach was fostered by the finding that the robustness and stability of networks may be the result of simple topological properties that are invariant throughout various technical as well as biological systems  <cit> .
in the following years the network topology of a large number of systems have been described, and it was found that some topology classes, such as those characterized by a scale-free distribution of the number of links at each node, or the so called "small world models" that are characterized by densely connected subnetworks loosely linked between each other, are indeed found in various systems within and without biology .
the various network types were described in terms of simple measures borrowed from graph theory, such as the clustering coefficient, the diameter of the graph etc  <cit> .
scala and associates described the folding states of short peptides using monte carlo simulation on lattice models  <cit> .
they found that that the geometric properties of this network are similar to those of small-world networks, i.e.
the diameter of the conformation space increases for large networks as the logarithm of the number of conformations, while locally the network appears to have low dimensionality.
shakhnovich and co-workers analysed the folding states of proteins during molecular dynamics simulations.
it was found that the folding space is reminiscent of scale-free network, characterized by a majority of less populated states as well as some highly populated states reminiscent of "hubs" seen in other systems  <cit> .
our purpose is to describe the folding space of the oxidative folding process using graph representations.
this is an intriguing task since, in contrast to "ordinary" protein folding, the number of states defined in terms of disulfide links is not exceedingly high, moreover the actual disulfide intermediates can be isolated and studied.
we will approach the problem in two steps as: i) we will use graph theory to describe the disulfide intermediates, and to enumerate the states of the folding space.
ii) then we will represent the folding space as a network  of all possible intermediates.
we show with few examples that experimentally observed intermediates mapped onto this network appear as contiguous folding pathways.
RESULTS
graph representation of oxidative folding intermediates
the disulfide topology of a protein is unequivocally defined by describing which cysteines are connected to each other.
for example, a topology "1– <dig>  2–4" means that a protein with four cysteines has two disulfide bridges that connect cysteines  and cysteines  respectively.
cysteines can be labelled by their sequence position, or – as in the previous example – in a serial order from the n-terminus .
the number of fully oxidised  isomers in a protein chain with n disulfide bonds  can be deduced from simple combinatorial considerations as !/.
according to this formula proteins with two disulfide bridges have  <dig> fully oxidized isomers, 3-disulfide proteins have  <dig> and 4-disulfide proteins have  <dig>  in other words, the number of intermediates increases very fast as a function of the number of constituent cysteines.
for a complete description of the folding process we have to consider both fully oxidized intermediates as well as the ones with free cysteine residues.
for this purpose we will use a formal description of the intermediates as undirected graphs, with cysteines as nodes and disulfide bridges as edges .
for the majority of naturally occurring protein structures the resulting graphs will be extremely simple.
if the protein has n cysteines, the n × n adjacency matrix of the graph is symmetrical; it will contain a value of  <dig> if two cysteines form a disulfide bond and zero otherwise.
as one cysteine can form only one disufide bridge, each column and each row will have at most one value of  <dig>  examples are shown in figure  <dig>
description of the oxidative folding space as graphs
the transitions between folding intermediates can be conveniently described by comparing the adjacency matrices of the two states.
for the enumeration of the transition reactions we introduce a few simple variables.
nb is the number of disulfide bonds, calculated as the sum of the elements of the adjacency matrix.
the sum of elements in the i-th column plus the i-th row,
is  <dig> if the i-th cysteine is part of a disulfide bridge and zero otherwise.
the sum of the differences calculated between the si measures of two adjacency matrices,
shows how many cysteines gain or loose a bond as the molecule passes from one state to the other.
here we are interested only in the two kinds of elementary reactions depicted in figure 1b.
in shuffling reactions, the number of disulfide bridges nb remains the same by definition, and it is easy to show that sd will differ exactly by  <dig>  in redox steps in which one disulfide bridge is established or lost, nb and sd will increase or decrease by one and two, respectively.
on the above basis one can easily draw a network of all possible oxidative folding pathways.
for a protein of n cysteines, we first generate the graphs  of all possible intermediates, i.e.
those with  <dig> ... disulfide bridges.
then we compare all pairs of intermediates in terms of the above parameters.
a shuffling edge will be drawn between two intermediate states if |sd| =  <dig> and Δnb = 0; redox edges will be drawn if |sd| =  <dig> and Δnb =  <dig>  if the values of |sd| and Δnb are different from these two combinations, no edge will be drawn.
the graph characteristics of a few systems are summarized in table  <dig>  the results show that as the number of cysteines increases, the clustering coefficient of the system decreases.
while the average path length increases.
both findings are consistent with the intuitive view that the folding space of peptides with many cysteines may be too complex and thus the systems may be unable to fold fast enough.
the pathways can also be graphically represented, and in order to simplify the resulting picture, we chose a 3d representation wherein the states  are grouped according to the number of disulfide bridges .
species with the same number of disulfide bridges are placed on the same plane, so shuffling reactions, which do not change the number of disulfide bridges are represented as edges within the same plane.
it is noted that on each of the separate planes we find a regular graph.
this is not surprising: exhaustive enumeration of theoretical states, such as eigen's quasi-species  <cit> , can produce highly connected regular graphs.
on the contrary, reactions in which a disulfide bridge is gained or lost, are represented as edges between two neighbouring planes.
the fully reduced state  is on top, the fully oxidized species, one of which is the native state, is on the bottom.
panel b shows a peptide with an odd number cysteines, such as granulocyte-colony stimulating-factor  <cit>  in which the native state contains one free cysteine residue.
in this case there are shuffling edges even in the lowest plane in the figure, so the native state  can be subject to shuffling transitions.
on the contrary, if the number of cysteines is an even number , the fully oxidized diss can not interconvert into each other in one step.
in some cases however an additional cysteine is in fact used to facilitate the process of oxidative folding: the propeptide of bpti contains an additional free cysteine that seems to significantly speed up the in vitro folding of the molecule  <cit> .
in vivo, the propeptide is subsequently cleaved, and in this way the structure is locked into the native disulfide configuration.
in principle, the oxidative folding pathways can be pictured as routes within the full network, starting at the fully reduced species and ending at the native state.
in the literature there are a few well-studied examples in which folding intermediates have been determined.
the experimentally observed disulfide intermediates of three examples, bovine pancreatic trypsin inhibitor, insulin-like growth factor and epidermal growth factor, are shown in table  <dig> and figure  <dig>  respectively.
it is noted that experimental methods do not necessarily reveal all possible intermediates; some of the intermediates may be too short-lived or not abundant enough so as to be noticed an isolated.
in spite of these limitations, the folding pathways appear as connected subgraphs within the network of all possible intermediates, showing that the experimental techniques actually identified states that can interconvert into one another.
only in egf do we see an "isolated" intermediate, which suggests that some intermediates of the pathway were not observed experimentally.
CONCLUSIONS
the oxidative folding space of polypeptides can be represented as networks in which the nodes are the disulfide intermediates while the edges are transitions between them.
a simple visualization tool written was developed to draw 3d pictures of such networks in which the states having the same number of disulfide bridges are placed on separate planes.
these pictures provide a simple method for the visualization of oxidative folding pathways as studied by experimental methods.
in the case of bovine pancreatic trypsin inhibitor, insulin-like growth factor and epidermal growth factor, the folding pathways appear as a small network of contiguous routes that connect the fully reduced state to the native state.
a further plausible extension of this method would include colouring of the folding states by quantitative properties and look for correlations between the coloured areas of the network and the experimentally determined folding pathways.
even though the topology of the theoretically complete folding space appears to be highly regular, data currently available are insufficient to draw general conclusions on the topology of the experimentally observed folding pathways.
experimentalists find folding intermediates as a series of chromatographic peaks, and usually the disulfide bridges of more abundant species are analysed first.
the question whether or not all the relevant intermediates have been analyzed is difficult to answer, and mapping the intermediates onto the graphs presented here may help one to decide whether or not the pathways found are contiguous.
authors' contributions
v.a.
designed and implemented the algorithms and carried out the calculations.
m.c.
helped to compile the experimental data and to draft the manuscript.
l.k.
designed the representation of folding intermediates.
the project was coordinated by s.p.

 the process of protein folding whereby a linear polypeptide chain reaches its native structure has been one of the most intensely studied biomolecular problems over the past years. folding of a protein is usually pictured as a search for the native conformation within the conformational space of all possible conformational states, each characterized by a set of parameters. even though most of the conformational states are not accessible to experiment, graphic representations of the potential energy surface have played pivotal roles in explaining how the conformational space is gradually restricted during the process folding. key concepts such as folding pathways are also best explained by graphic representations. the particular kind of folding that this article is concerned with is oxidative folding, which is the fusion of native disulfide bond formation with conformational folding. this complex process is guided by two types of interactions: first, non-covalent interactions giving rise to secondary and tertiary structure, and second, covalent interactions between cysteine residues, which ultimately transform into native disulfide bridges. the process of disulfide formation is a simple chemical reaction in which two sh groups join to form a disulfide link. if the sh groups are on a polypeptide chain, the in vitro reaction can be promoted by an external redox system such as a mixture of oxidized and reduced glutathione, or cysteine and cystine, respectively. in vivo, the oxidative power comes from specific agents such as the molecular chaperones protein disulfide isomerases. the underlying chemical mechanism is disulfide interchange. in this scheme there are two kinds of reactions: i) in a redox reaction a protein disulfide bond is created, i.e. the oxidative state of the polypeptide is changed. this is the case when one of the participants of the reaction is not part of the protein. ii) in a shuffling reaction both participants of the reaction are protein-bound, so the oxidative state of the polypeptide does not change. in view of these possibilities it becomes obvious that there are a great many ways in which disulfide bridges can form and rearrange during the folding process. today it is generally accepted that non-covalent interactions guide the process of folding and formation of disulfide bridges will lock the protein into the right conformation. the advantage of oxidative folding as opposed to general protein folding is that disulfide intermediates can be chemically isolated and studied using such techniques as acid trapping of the intermediates and analysis of the disulfide bridges using a combination of enzymatic cleavage and mass spectrometry. there is a body of literature in describing the pathways of oxidative folding in terms of disulfide intermediates, and our goal is show how graph theory can be used to visualize them. graph theory has been applied to many aspects of protein research. the applications followed two broad avenues: i) first, protein structure itself can be considered as a graph consisting of various interactions as edges, the nodes being atoms or residues of the protein. for instance, one of the classical definitions of protein secondary structures is based on main/chain h-bond contacts between residues. structural neworks have been used in folding research as well. it was found, among others, that the so-called contact order, i.e. the average sequence distance between residues in atomic contact, seems to be a key determinant of folding speed. another line of research concentrates on characteristic networks of inter-atomic contacts that may form stabilization centres in protein structures and can be the reason of the differential stability of various proteins. it was found that populated conformations seen in molecular dynamics simulations contain characteristic networks of residues. ii) in the network descriptions of the folding space, on the other hand, the folding states are the nodes, and transitions are the edges between them. this approach was fostered by the finding that the robustness and stability of networks may be the result of simple topological properties that are invariant throughout various technical as well as biological systems. in the following years the network topology of a large number of systems have been described, and it was found that some topology classes, such as those characterized by a scale-free distribution of the number of links at each node, or the so called "small world models" that are characterized by densely connected subnetworks loosely linked between each other, are indeed found in various systems within and without biology. the various network types were described in terms of simple measures borrowed from graph theory, such as the clustering coefficient, the diameter of the graph etc. scala and associates described the folding states of short peptides using monte carlo simulation on lattice models. they found that that the geometric properties of this network are similar to those of small-world networks, i.e. the diameter of the conformation space increases for large networks as the logarithm of the number of conformations, while locally the network appears to have low dimensionality. shakhnovich and co-workers analysed the folding states of proteins during molecular dynamics simulations. it was found that the folding space is reminiscent of scale-free network, characterized by a majority of less populated states as well as some highly populated states reminiscent of "hubs" seen in other systems. our purpose is to describe the folding space of the oxidative folding process using graph representations. this is an intriguing task since, in contrast to "ordinary" protein folding, the number of states defined in terms of disulfide links is not exceedingly high, moreover the actual disulfide intermediates can be isolated and studied. we will approach the problem in two steps as: i) we will use graph theory to describe the disulfide intermediates, and to enumerate the states of the folding space. ii) then we will represent the folding space as a network of all possible intermediates. we show with few examples that experimentally observed intermediates mapped onto this network appear as contiguous folding pathways.  graph representation of oxidative folding intermediates the disulfide topology of a protein is unequivocally defined by describing which cysteines are connected to each other. for example, a topology "1– 2–4" means that a protein with four cysteines has two disulfide bridges that connect cysteines and cysteines respectively. cysteines can be labelled by their sequence position, or – as in the previous example – in a serial order from the n-terminus. the number of fully oxidised isomers in a protein chain with n disulfide bonds can be deduced from simple combinatorial considerations as!/. according to this formula proteins with two disulfide bridges have fully oxidized isomers, 3-disulfide proteins have and 4-disulfide proteins have in other words, the number of intermediates increases very fast as a function of the number of constituent cysteines. for a complete description of the folding process we have to consider both fully oxidized intermediates as well as the ones with free cysteine residues. for this purpose we will use a formal description of the intermediates as undirected graphs, with cysteines as nodes and disulfide bridges as edges. for the majority of naturally occurring protein structures the resulting graphs will be extremely simple. if the protein has n cysteines, the n × n adjacency matrix of the graph is symmetrical; it will contain a value of if two cysteines form a disulfide bond and zero otherwise. as one cysteine can form only one disufide bridge, each column and each row will have at most one value of examples are shown in figure description of the oxidative folding space as graphs the transitions between folding intermediates can be conveniently described by comparing the adjacency matrices of the two states. for the enumeration of the transition reactions we introduce a few simple variables. nb is the number of disulfide bonds, calculated as the sum of the elements of the adjacency matrix. the sum of elements in the i-th column plus the i-th row, is if the i-th cysteine is part of a disulfide bridge and zero otherwise. the sum of the differences calculated between the si measures of two adjacency matrices, shows how many cysteines gain or loose a bond as the molecule passes from one state to the other. here we are interested only in the two kinds of elementary reactions depicted in figure 1b. in shuffling reactions, the number of disulfide bridges nb remains the same by definition, and it is easy to show that sd will differ exactly by in redox steps in which one disulfide bridge is established or lost, nb and sd will increase or decrease by one and two, respectively. on the above basis one can easily draw a network of all possible oxidative folding pathways. for a protein of n cysteines, we first generate the graphs of all possible intermediates, i.e. those with... disulfide bridges. then we compare all pairs of intermediates in terms of the above parameters. a shuffling edge will be drawn between two intermediate states if |sd| = and Δnb = 0; redox edges will be drawn if |sd| = and Δnb = if the values of |sd| and Δnb are different from these two combinations, no edge will be drawn. the graph characteristics of a few systems are summarized in table the results show that as the number of cysteines increases, the clustering coefficient of the system decreases. while the average path length increases. both findings are consistent with the intuitive view that the folding space of peptides with many cysteines may be too complex and thus the systems may be unable to fold fast enough. the pathways can also be graphically represented, and in order to simplify the resulting picture, we chose a 3d representation wherein the states are grouped according to the number of disulfide bridges. species with the same number of disulfide bridges are placed on the same plane, so shuffling reactions, which do not change the number of disulfide bridges are represented as edges within the same plane. it is noted that on each of the separate planes we find a regular graph. this is not surprising: exhaustive enumeration of theoretical states, such as eigen's quasi-species, can produce highly connected regular graphs. on the contrary, reactions in which a disulfide bridge is gained or lost, are represented as edges between two neighbouring planes. the fully reduced state is on top, the fully oxidized species, one of which is the native state, is on the bottom. panel b shows a peptide with an odd number cysteines, such as granulocyte-colony stimulating-factor in which the native state contains one free cysteine residue. in this case there are shuffling edges even in the lowest plane in the figure, so the native state can be subject to shuffling transitions. on the contrary, if the number of cysteines is an even number, the fully oxidized diss can not interconvert into each other in one step. in some cases however an additional cysteine is in fact used to facilitate the process of oxidative folding: the propeptide of bpti contains an additional free cysteine that seems to significantly speed up the in vitro folding of the molecule. in vivo, the propeptide is subsequently cleaved, and in this way the structure is locked into the native disulfide configuration. in principle, the oxidative folding pathways can be pictured as routes within the full network, starting at the fully reduced species and ending at the native state. in the literature there are a few well-studied examples in which folding intermediates have been determined. the experimentally observed disulfide intermediates of three examples, bovine pancreatic trypsin inhibitor, insulin-like growth factor and epidermal growth factor, are shown in table and figure respectively. it is noted that experimental methods do not necessarily reveal all possible intermediates; some of the intermediates may be too short-lived or not abundant enough so as to be noticed an isolated. in spite of these limitations, the folding pathways appear as connected subgraphs within the network of all possible intermediates, showing that the experimental techniques actually identified states that can interconvert into one another. only in egf do we see an "isolated" intermediate, which suggests that some intermediates of the pathway were not observed experimentally.  the oxidative folding space of polypeptides can be represented as networks in which the nodes are the disulfide intermediates while the edges are transitions between them. a simple visualization tool written was developed to draw 3d pictures of such networks in which the states having the same number of disulfide bridges are placed on separate planes. these pictures provide a simple method for the visualization of oxidative folding pathways as studied by experimental methods. in the case of bovine pancreatic trypsin inhibitor, insulin-like growth factor and epidermal growth factor, the folding pathways appear as a small network of contiguous routes that connect the fully reduced state to the native state. a further plausible extension of this method would include colouring of the folding states by quantitative properties and look for correlations between the coloured areas of the network and the experimentally determined folding pathways. even though the topology of the theoretically complete folding space appears to be highly regular, data currently available are insufficient to draw general conclusions on the topology of the experimentally observed folding pathways. experimentalists find folding intermediates as a series of chromatographic peaks, and usually the disulfide bridges of more abundant species are analysed first. the question whether or not all the relevant intermediates have been analyzed is difficult to answer, and mapping the intermediates onto the graphs presented here may help one to decide whether or not the pathways found are contiguous. authors' contributions v.a. designed and implemented the algorithms and carried out the calculations. m.c. helped to compile the experimental data and to draft the manuscript. l.k. designed the representation of folding intermediates. the project was coordinated by s.p. 
such networks can be used to visualize folding pathways in terms of the experimentally observed intermediates. in this representation, the shuffling transitions are within the planes, and the redox edges connect adjacent planes. the oxidative folding space can be represented as a network of dis states interconnected by disulfide interchange reactions that can either create/abolish or rearrange disulfide bridges. we propose a simple 3d representation wherein the states having the same number of disulfide bridges are placed on separate planes.
 the process of oxidative folding combines the formation of native disulfide bond with conformational folding resulting in the native three-dimensional fold. oxidative folding pathways can be described in terms of disulfide intermediate species which can also be isolated and characterized. each dis corresponds to a family of folding states that the given dis can adopt in three dimensions.  the oxidative folding space can be represented as a network of dis states interconnected by disulfide interchange reactions that can either create/abolish or rearrange disulfide bridges. we propose a simple 3d representation wherein the states having the same number of disulfide bridges are placed on separate planes. in this representation, the shuffling transitions are within the planes, and the redox edges connect adjacent planes. in a number of experimentally studied cases, the observed intermediates appear as part of contiguous oxidative folding pathways.  such networks can be used to visualize folding pathways in terms of the experimentally observed intermediates. a simple visualization template written for the tulip package can be obtained from v.a. 