BACKGROUND
as early studies revealed that an unfolded protein can fold spontaneously to a three-dimensional structure under suitable environmental conditions  <cit> , traditional approaches to understanding protein folding have focused on the prediction of the native structure.
as more studies showed the existence of intermediates and interaction among residues during the protein folding process  <cit> , there is substantial interest to understand the time order of events during the formation of the tertiary structure.
from the free energy point of view, each conformation of a protein is associated with a free energy and the protein folds from the high-energy denatured conformation to its folded structure along a funnel-like energy landscape  <cit> .
although advances in experimental techniques allow the investigation of protein folding pathways at the microsecond timescale  <cit> , experimental determination of protein folding pathways remains difficult.
most studies are only able to identify general characteristics of the folding pathway without much details and are limited to analyzing small proteins.
computational techniques are often used to simulate protein folding and the problem is transformed to energetic optimization problems, that is, computational search for global energy minimum over all possible conformations.
the most accurate computational techniques utilize molecular dynamics to determine the order of events that lead to the tertiary structure through atomic-level simulations  <cit> .
due to the extremely large conformation space, these approaches suffer from well-known problems accompanying high dimensionality, including computational expensiveness and ease of trapping in local minima, and are applicable only to small proteins in a short time course.
by omitting some details, proteins can be represented at the level of amino acids.
kolinski and skolnick  <cit>  performed monte carlo simulations of protein folding on a reduced lattice representation of the protein α-carbon backbone.
yue and dill  <cit>  limited the conformation space to a discrete subset of possibilities and used a branch-and-bound procedure to search for near-optimal conformations.
alm and baker  <cit>  and muñoz and eaton  <cit>  further observed that the availability of the known native structure can dramatically reduce the search space.
alm and baker  <cit>  took into account only native interactions among residues and used a sequential binary collision model to predict protein folding mechanisms from the perspectives of free energy landscapes, while muñoz and eaton  <cit>  used a slightly different approach of employing distinct free energy costs for different secondary structures.
amato and song  <cit>  represented a protein by the torsional angles of its residues and used the probabilistic roadmap technique with a biased sampling strategy around the native structure to predict folding pathways and secondary structure formation order.
liwo et al  <cit>  and kmiecik and kolinski  <cit>  showed that the use of reduced models of proteins is highly successful in characterizing folding pathways for small proteins at the mesoscopic level.
although these techniques are able to predict folding pathways very accurately for proteins with up to about  <dig> residues, the majority of proteins in the protein data bank   <cit>  are much larger .
the problem with representing a protein at the amino acid level is that even with the assumption that each residue has only two states , a protein with n residues still has 2n possible conformations  <cit> .
to overcome this problem, several recent approaches represent a protein at the level of secondary structure elements , in which each element corresponds to one helix or one β-strand.
by adopting the framework model in which secondary structures are thought to fold relatively independently of the tertiary structure  <cit> , each sse is treated as an indivisible unit that interacts with other sses as a whole.
since the number of sses in a protein is small , this model is much more tractable to simulate.
eyrich et al  <cit>  assumed that the sses are fixed and used a branch-and-bound algorithm to search for near-optimal tertiary structures.
apaydin et al  <cit>  assumed that each sse of a protein is already in native conformation and moves as a unit, and used the probabilistic roadmap approach to predict folding pathways.
zaki et al  <cit>  proposed an algorithm to predict unfolding pathways based on applying a minimum cut procedure to a weighted graph that represents a protein's contact map or interaction strength between sses.
although the underlying assumption that intermediate secondary structures are fully folded before the formation of tertiary structures is not satisfied for most proteins, these studies show that such a strategy is sufficient to study protein folding pathways at the mesoscopic level.
in this paper, our goal is to further reduce the conformation space without sacrificing prediction accuracy.
this is achieved by assuming that sses that do not yet interact with each other are independent and can be treated separately.
a conformation is represented by a collection of fully folded structures in which each of them contains a set of interacting sses.
by using a steepest descent strategy, we show that it is possible to predict the most energetically favorable folding pathway of large proteins with hundreds of residues at the mesoscopic level and this model is detailed enough to distinguish between different folding pathways of structurally very similar proteins.
in difference from the technique in  <cit> , we do not consider the spatially moving process before the sses form native contacts, and thus we are able to achieve much better computational efficiency.
methods
assume that the native structure of a protein is known.
the protein folding pathway prediction problem is to find an ordered sequence of intermediate conformations to fill the gap between the unfolded state and the native tertiary structure.
at the secondary structure level, a protein can be viewed as an ordered sequence of secondary structure elements  interspersed with irregular turns or loops, where each sse is either a helix or a β-strand, and each β-sheet consists of a variable number of β-strands that are not necessarily consecutive on the primary sequence.
we represent each protein by t0s1t1⋯sktk, where k is the number of sses, si denotes the ith sse, tj denotes the jth turn, and these elements are in the same order as they appear on the primary sequence.
given the three-dimensional structure of a protein, the assignment of sses can be obtained directly from the protein data bank   <cit>  or using programs such as dssp  <cit> .
following  <cit>  and  <cit> , we consider each sse as an indivisible unit that folds independently of the others according to the contacts present in the native structure.
this is based on the framework model that assumes that extensive intermediate secondary structures exist before they are assembled into the tertiary structure  <cit> , and our goal is to predict the interaction order of sses during folding.
based on the observation in  <cit>  and  <cit>  that a model using only native interactions can explain most experimental results, we assume that the interactions between sses or turns are the same as the ones present in the native structure.
although these assumptions are often not satisfied as there are many proteins in which there are no clear secondary structures before the formation of tertiary structures or there are no clear preservations of secondary structures throughout folding, such a strategy is sufficient for studying folding pathways at the mesoscopic level and is often the only feasible choice for large proteins.
we represent a conformation of a protein on the folding pathway by c = {s <dig>  ..., sk}, where each si represents a structure consisting of a set of fully folded sses and there are no interactions between two different sets sj and sj' .
since our focus is on the sses, turns are not included in the conformation but will be utilized when computing energies .
the protein folding problem is transformed to identifying a sequence of conformational changes that start from an initial state with fully folded sses but no interactions between sses through some intermediate conformations and ending in the native structure .
each conformational change corresponds to finding a new pair of interactions that merges two smaller structures of sses into a bigger one.
figure  <dig> illustrates the folding pathway prediction on the b <dig> domain of the streptococcal protein g .
in the prediction, β <dig> and β <dig> interact first, then α <dig> is added, followed by β <dig> and β <dig>
folding pathway predictions are obtained through the computation of free energies of intermediate conformations.
for an intermediate conformation c = {s <dig>  ..., sk}, the free energy e of c is defined as:
e=∑i=1ke,
where each si is viewed as an isolated entity and each e is obtained separately by extracting the three-dimensional coordinates of its residues from the protein data bank   <cit>  and using the rosetta software  <cit>  to compute its free energy.
the original rosetta energy function is used, which is obtained by representing each side chain by a centroid that is located at the center of mass, and computing a weighted sum of the binned probability descriptions of multiple effects, including the solvation and electrostatic effects based on observed distributions in known protein structures, the secondary structure packing effects that include strand pairing, strand arrangement into sheets and helix-strand packing, and the effects of steric repulsion and van der waals interactions .
to take the backbone into consideration, a turn tj is included in the computation of e if both of its adjacent sses sj  and sj+ <dig>  are included in si.
since the interactions that favor folding usually decrease the free energy while the interactions that destabilize the native structure increase the free energy, our goal is to find the most energetically favorable folding pathway by identifying the conformational change that decreases the free energy the most in each step so that the protein can get to lower energy states as quickly as possible.
figure  <dig> illustrates our ssfold algorithm that uses a steepest descent strategy to choose a new pair of interactions that leads to a conformation with the lowest free energy in each iteration.
this procedure is very efficient since only k -  <dig> iterations are needed.
within each iteration, o comparisons are needed to find the best pair of interactions that results in the lowest free energy.
this leads to an overall time complexity of o, where k is the number of sses in a protein and t is the time to compute the free energy of a potentially partial protein that contains only some of the sses and turns.
RESULTS
we test our strategy on proteins from the protein data bank   <cit>  that have known intermediate folding states from experimental data.
we illustrate that our model is detailed enough to distinguish between subtle differences in the folding pathways of the streptococcal protein g, the peptostreptococcal protein l, and variants nug <dig> and nug <dig> of protein g, which are all structurally very similar proteins.
we demonstrate that our approach is applicable to large proteins with hundreds of residues by testing it on the  <dig> residue pig muscle phosphoglycerate kinase .
we further test it on proteins studied in  <cit>  and  <cit>  to validate that our model has very good accuracy.
proteins gb <dig>  lb <dig>  nug <dig> and nug2
the  <dig> residue b <dig> immunoglobulin binding domain of streptococcal protein g  and the  <dig> residue b <dig> immunoglobulin binding domain of peptostreptococcal protein l  have been used extensively as model systems for studying protein folding mechanisms  <cit> .
both gb <dig>  and lb <dig> consist of one β-sheet with four strands and one α-helix.
strands  <dig> and  <dig> form an n-terminal β-hairpin, while strands  <dig> and  <dig> form a c-terminal β-hairpin.
although gb <dig> and lb <dig> have very similar tertiary structures, they have different folding pathways.
as suggested by  <cit> , a detailed model is needed to distinguish between them.
experimental results showed that the c-terminal β-hairpin in gb <dig> is formed in the transition state of the folding pathway and serves as the starting point on which the rest of the protein can fold  <cit> .
similar results were obtained using the diffusion-collision model  <cit> .
our prediction is consistent with these results.
in contrast, experimental results showed that only the n-terminal β-hairpin in lb <dig> is mainly formed in the transition state and non-random structures can be detected in the region  <cit> .
our algorithm also predicts that the n-terminal β-hairpin forms earlier than the c-terminal β-hairpin in lb <dig>
two protein g variants, nug <dig>  and nug <dig> , were designed to have a different folding mechanism from protein g by replacing some residues of protein g  <cit> .
in nug <dig> and nug <dig>  the stability of the n-terminal β-hairpin is enhanced while the stability of the c-terminal β-hairpin is reduced, with the n-terminal β-hairpin forming contacts earlier than the c-terminal β-hairpin in both cases  <cit> .
thomas et al  <cit>  showed that it is more difficult to distinguish between the folding pathways of protein g and its variants nug <dig> and nug <dig> than to distinguish between the folding pathways of protein g and protein l. in our predictions in figure  <dig>  nug <dig> and nug <dig> have the same folding pathway, with the n-terminal β-hairpin folded first.
this is consistent with the experimental results in  <cit>  and the predictions in  <cit> .
pig muscle pgk: a large protein
phosphoglycerate kinase  from various organisms has been used as a model system for studying domain-domain interactions of multiple-domain proteins  <cit> .
the pig muscle pgk   <cit>  is a large two-domain protein with  <dig> residues, with the n-terminal domain consisting of residues  <dig> to  <dig> and the c-terminal domain consisting of residues  <dig> to  <dig>  there are  <dig> α-helices and  <dig> β-strands, which belong to four different β-sheets a, b, c and d, arranged as follows on the primary sequence: α <dig> βa <dig> α <dig> α <dig> βa <dig> α <dig> βa <dig> α <dig> βa <dig> α <dig> βb <dig> βb <dig> α <dig> βa <dig> α <dig> α <dig> βa <dig> α <dig> βc <dig> α <dig> α <dig> βc <dig> α <dig> α <dig> α <dig> βc <dig> βd <dig> βd <dig> βd <dig> α <dig> βc <dig> α <dig> α <dig> βc <dig> α <dig> βc <dig> α <dig> α <dig>
szilágyi and vas  <cit>  suggested a sequential domain refolding mechanism for the pig muscle pgk, in which folding of the c-terminal domain is independent of the n-terminal domain and takes place first, and folding of the n-terminal domain starts after most of the c-terminal domain folds.
the authors also suggested that an intermediate consists of a folded c-terminal domain and a still unfolded n-terminal domain.
our prediction is consistent with these experimental results.
other proteins
the b domain of staphylococcus aureus protein a  consists of three α-helices.
in our prediction, α <dig> and α <dig> interact first, then α <dig> is added.
this is consistent with the result of the out-exchange experiment in  <cit>  and experimental results under high temperature  <cit> .
although two members of the globin protein family, leghemoglobin a  and myoglobin , have very low sequence similarity, they both consist of eight α-helices and have very similar tertiary structures.
nishimura et al  <cit>  compared their folding pathways experimentally.
for leghemoglobin a, αg, αh, and part of αe form stable structures first, while αa and αb form in the later stages of the folding pathway.
for myoglobin, αa, αg and αh form stable contacts first.
the main difference between the two folding pathways is that αa and αb form earlier in the folding pathway of myoglobin than in the folding pathway of leghemoglobin a  <cit> .
our predictions are able to distinguish between these subtle differences.
for leghemoglobin a, αg and αh are predicted to interact first, then αe is added, with αb and αa added later.
for myoglobin, αg and αh are also predicted to interact first, then αa is added, followed by αe and αb.
there are two crystal structures for chymotrypsin inhibitor  <dig> .
while 2ci <dig> consists of  <dig> residues, 1coa is a fragment of 2ci <dig> from residues  <dig> to  <dig>  they both consist of one α-helix and four β-strands, which are arranged as β1α1β2β3β <dig> in 1coa and β1α1β4β3β <dig> in 2ci <dig>  in our predictions, 1coa and 2ci <dig> have the same folding pathway, with the middle two β-strands interacting first, then the α-helix is added, followed by the c-terminal β-strand, and the n-terminal β-strand is added last.
for 1coa, simulation by  <cit>  demonstrated that β <dig> and β <dig> form contacts first, then α <dig> is added to form a folding nucleus.
the coalescence of β <dig> is the rate-limiting step and is completed at the end of the folding process.
this is consistent with the result of the out-exchange experiment in  <cit>  that showed that β <dig>  β <dig> and α <dig> form contacts first.
our prediction is consistent with these results.
the all β-sheet protein cardiotoxin iii  consists of five strands.
while β <dig> and β <dig> form a double-stranded domain, β <dig>  β <dig> and β <dig> form a triple-stranded domain.
by the amide proton pulse exchange experiment, sivaraman et al  <cit>  showed that the triple-stranded domain forms earlier than the double-stranded domain during the refolding process.
the carbonyl groups in β <dig> and the amide groups in β <dig> form hydrogen bonding partners, which are important for the formation of a hydrophobic cluster  <cit> .
our prediction is consistent with these results, with β <dig> and β <dig> interacting first, then β <dig> is added to form the triple-stranded domain, followed by β <dig> and β <dig> in the double-stranded domain.
bovine pancreatic trypsin inhibitor bpti  is a globular protein with two α-helices and three β-strands, which are arranged as α1β2β1β3α <dig>  three disulfide bonds between residues  <dig> and  <dig>   <dig> and  <dig>  and  <dig> and  <dig> play an important role in stabilizing the native structure  <cit> , and their formation order was studied in  <cit> .
in our prediction, β <dig> and β <dig> interact first, then α <dig> is added.
this brings residues  <dig> and  <dig> close together and helps to form the disulfide bond between them.
then α <dig> is added and this helps to form the disulfide bond between residues  <dig> and  <dig>  and  <dig> and  <dig>  our prediction that β <dig> and β <dig> interact earlier than the two α-helices is consistent with the result in  <cit> .
discussion
while our strategy corresponds most closely to the diffusion-collision model that allows folding to proceed independently in different parts of a protein  <cit> , it is possible to use a modified strategy for other models.
for example, to simulate the nucleation-propagation model  <cit>  or the nucleation-condensation model  <cit> , in which the existence of a nucleus facilitates further folding, one can iteratively add a sse that results in the lowest free energy to the nucleus.
since energy computations can still be slow and can take hours, which account for significant amount of computation time in our algorithm, it is also possible to use lower resolution methods to compute energy.
while our strategy finds the most energetically favorable protein folding pathway, there are evidences that multiple folding pathways exist  <cit> .
the ability to analyze multiple folding pathways will also allow the study of protein misfolding  <cit> .
our approach can be generalized to study the entire free energy landscape  <cit>  as follows: construct a graph in which each vertex represents a biologically plausible conformation and each edge represents a feasible conformation change, which is similar to the roadmap graph in  <cit>  and  <cit>  and the protein folding network in  <cit>  except that we consider each sse as an indivisible unit.
various graph-theoretic algorithms can then be used to generate predictions of alternative folding pathways.
CONCLUSIONS
we have shown that our procedure has sufficient accuracy to distinguish between subtle differences and our strategy can be applied to large proteins due to its speed.
an important future direction is to consider cooperative folding of secondary structures without too much sacrifice in speed, that is, when folding in one secondary structure affects folding in others.
authors' contributions
qy performed the research and implemented the algorithm.
s–hs supervised the research.
all authors read and approved the final manuscript.

 as early studies revealed that an unfolded protein can fold spontaneously to a three-dimensional structure under suitable environmental conditions, traditional approaches to understanding protein folding have focused on the prediction of the native structure. as more studies showed the existence of intermediates and interaction among residues during the protein folding process, there is substantial interest to understand the time order of events during the formation of the tertiary structure. from the free energy point of view, each conformation of a protein is associated with a free energy and the protein folds from the high-energy denatured conformation to its folded structure along a funnel-like energy landscape. although advances in experimental techniques allow the investigation of protein folding pathways at the microsecond timescale, experimental determination of protein folding pathways remains difficult. most studies are only able to identify general characteristics of the folding pathway without much details and are limited to analyzing small proteins. computational techniques are often used to simulate protein folding and the problem is transformed to energetic optimization problems, that is, computational search for global energy minimum over all possible conformations. the most accurate computational techniques utilize molecular dynamics to determine the order of events that lead to the tertiary structure through atomic-level simulations. due to the extremely large conformation space, these approaches suffer from well-known problems accompanying high dimensionality, including computational expensiveness and ease of trapping in local minima, and are applicable only to small proteins in a short time course. by omitting some details, proteins can be represented at the level of amino acids. kolinski and skolnick performed monte carlo simulations of protein folding on a reduced lattice representation of the protein α-carbon backbone. yue and dill limited the conformation space to a discrete subset of possibilities and used a branch-and-bound procedure to search for near-optimal conformations. alm and baker and muñoz and eaton further observed that the availability of the known native structure can dramatically reduce the search space. alm and baker took into account only native interactions among residues and used a sequential binary collision model to predict protein folding mechanisms from the perspectives of free energy landscapes, while muñoz and eaton used a slightly different approach of employing distinct free energy costs for different secondary structures. amato and song represented a protein by the torsional angles of its residues and used the probabilistic roadmap technique with a biased sampling strategy around the native structure to predict folding pathways and secondary structure formation order. liwo et al and kmiecik and kolinski showed that the use of reduced models of proteins is highly successful in characterizing folding pathways for small proteins at the mesoscopic level. although these techniques are able to predict folding pathways very accurately for proteins with up to about residues, the majority of proteins in the protein data bank are much larger. the problem with representing a protein at the amino acid level is that even with the assumption that each residue has only two states, a protein with n residues still has 2n possible conformations. to overcome this problem, several recent approaches represent a protein at the level of secondary structure elements, in which each element corresponds to one helix or one β-strand. by adopting the framework model in which secondary structures are thought to fold relatively independently of the tertiary structure, each sse is treated as an indivisible unit that interacts with other sses as a whole. since the number of sses in a protein is small, this model is much more tractable to simulate. eyrich et al assumed that the sses are fixed and used a branch-and-bound algorithm to search for near-optimal tertiary structures. apaydin et al assumed that each sse of a protein is already in native conformation and moves as a unit, and used the probabilistic roadmap approach to predict folding pathways. zaki et al proposed an algorithm to predict unfolding pathways based on applying a minimum cut procedure to a weighted graph that represents a protein's contact map or interaction strength between sses. although the underlying assumption that intermediate secondary structures are fully folded before the formation of tertiary structures is not satisfied for most proteins, these studies show that such a strategy is sufficient to study protein folding pathways at the mesoscopic level. in this paper, our goal is to further reduce the conformation space without sacrificing prediction accuracy. this is achieved by assuming that sses that do not yet interact with each other are independent and can be treated separately. a conformation is represented by a collection of fully folded structures in which each of them contains a set of interacting sses. by using a steepest descent strategy, we show that it is possible to predict the most energetically favorable folding pathway of large proteins with hundreds of residues at the mesoscopic level and this model is detailed enough to distinguish between different folding pathways of structurally very similar proteins. in difference from the technique in, we do not consider the spatially moving process before the sses form native contacts, and thus we are able to achieve much better computational efficiency. methods assume that the native structure of a protein is known. the protein folding pathway prediction problem is to find an ordered sequence of intermediate conformations to fill the gap between the unfolded state and the native tertiary structure. at the secondary structure level, a protein can be viewed as an ordered sequence of secondary structure elements interspersed with irregular turns or loops, where each sse is either a helix or a β-strand, and each β-sheet consists of a variable number of β-strands that are not necessarily consecutive on the primary sequence. we represent each protein by t0s1t1⋯sktk, where k is the number of sses, si denotes the ith sse, tj denotes the jth turn, and these elements are in the same order as they appear on the primary sequence. given the three-dimensional structure of a protein, the assignment of sses can be obtained directly from the protein data bank or using programs such as dssp. following and, we consider each sse as an indivisible unit that folds independently of the others according to the contacts present in the native structure. this is based on the framework model that assumes that extensive intermediate secondary structures exist before they are assembled into the tertiary structure, and our goal is to predict the interaction order of sses during folding. based on the observation in and that a model using only native interactions can explain most experimental results, we assume that the interactions between sses or turns are the same as the ones present in the native structure. although these assumptions are often not satisfied as there are many proteins in which there are no clear secondary structures before the formation of tertiary structures or there are no clear preservations of secondary structures throughout folding, such a strategy is sufficient for studying folding pathways at the mesoscopic level and is often the only feasible choice for large proteins. we represent a conformation of a protein on the folding pathway by c = {s..., sk}, where each si represents a structure consisting of a set of fully folded sses and there are no interactions between two different sets sj and sj'. since our focus is on the sses, turns are not included in the conformation but will be utilized when computing energies. the protein folding problem is transformed to identifying a sequence of conformational changes that start from an initial state with fully folded sses but no interactions between sses through some intermediate conformations and ending in the native structure. each conformational change corresponds to finding a new pair of interactions that merges two smaller structures of sses into a bigger one. figure illustrates the folding pathway prediction on the b domain of the streptococcal protein g. in the prediction, β and β interact first, then α is added, followed by β and β folding pathway predictions are obtained through the computation of free energies of intermediate conformations. for an intermediate conformation c = {s..., sk}, the free energy e of c is defined as: e=∑i=1ke, where each si is viewed as an isolated entity and each e is obtained separately by extracting the three-dimensional coordinates of its residues from the protein data bank and using the rosetta software to compute its free energy. the original rosetta energy function is used, which is obtained by representing each side chain by a centroid that is located at the center of mass, and computing a weighted sum of the binned probability descriptions of multiple effects, including the solvation and electrostatic effects based on observed distributions in known protein structures, the secondary structure packing effects that include strand pairing, strand arrangement into sheets and helix-strand packing, and the effects of steric repulsion and van der waals interactions. to take the backbone into consideration, a turn tj is included in the computation of e if both of its adjacent sses sj and sj+ are included in si. since the interactions that favor folding usually decrease the free energy while the interactions that destabilize the native structure increase the free energy, our goal is to find the most energetically favorable folding pathway by identifying the conformational change that decreases the free energy the most in each step so that the protein can get to lower energy states as quickly as possible. figure illustrates our ssfold algorithm that uses a steepest descent strategy to choose a new pair of interactions that leads to a conformation with the lowest free energy in each iteration. this procedure is very efficient since only k - iterations are needed. within each iteration, o comparisons are needed to find the best pair of interactions that results in the lowest free energy. this leads to an overall time complexity of o, where k is the number of sses in a protein and t is the time to compute the free energy of a potentially partial protein that contains only some of the sses and turns.  we test our strategy on proteins from the protein data bank that have known intermediate folding states from experimental data. we illustrate that our model is detailed enough to distinguish between subtle differences in the folding pathways of the streptococcal protein g, the peptostreptococcal protein l, and variants nug and nug of protein g, which are all structurally very similar proteins. we demonstrate that our approach is applicable to large proteins with hundreds of residues by testing it on the residue pig muscle phosphoglycerate kinase. we further test it on proteins studied in and to validate that our model has very good accuracy. proteins gb lb nug and nug2 the residue b immunoglobulin binding domain of streptococcal protein g and the residue b immunoglobulin binding domain of peptostreptococcal protein l have been used extensively as model systems for studying protein folding mechanisms. both gb and lb consist of one β-sheet with four strands and one α-helix. strands and form an n-terminal β-hairpin, while strands and form a c-terminal β-hairpin. although gb and lb have very similar tertiary structures, they have different folding pathways. as suggested by, a detailed model is needed to distinguish between them. experimental results showed that the c-terminal β-hairpin in gb is formed in the transition state of the folding pathway and serves as the starting point on which the rest of the protein can fold. similar results were obtained using the diffusion-collision model. our prediction is consistent with these results. in contrast, experimental results showed that only the n-terminal β-hairpin in lb is mainly formed in the transition state and non-random structures can be detected in the region. our algorithm also predicts that the n-terminal β-hairpin forms earlier than the c-terminal β-hairpin in lb two protein g variants, nug and nug, were designed to have a different folding mechanism from protein g by replacing some residues of protein g. in nug and nug the stability of the n-terminal β-hairpin is enhanced while the stability of the c-terminal β-hairpin is reduced, with the n-terminal β-hairpin forming contacts earlier than the c-terminal β-hairpin in both cases. thomas et al showed that it is more difficult to distinguish between the folding pathways of protein g and its variants nug and nug than to distinguish between the folding pathways of protein g and protein l. in our predictions in figure nug and nug have the same folding pathway, with the n-terminal β-hairpin folded first. this is consistent with the experimental results in and the predictions in. pig muscle pgk: a large protein phosphoglycerate kinase from various organisms has been used as a model system for studying domain-domain interactions of multiple-domain proteins. the pig muscle pgk is a large two-domain protein with residues, with the n-terminal domain consisting of residues to and the c-terminal domain consisting of residues to there are α-helices and β-strands, which belong to four different β-sheets a, b, c and d, arranged as follows on the primary sequence: α βa α α βa α βa α βa α βb βb α βa α α βa α βc α α βc α α α βc βd βd βd α βc α α βc α βc α α szilágyi and vas suggested a sequential domain refolding mechanism for the pig muscle pgk, in which folding of the c-terminal domain is independent of the n-terminal domain and takes place first, and folding of the n-terminal domain starts after most of the c-terminal domain folds. the authors also suggested that an intermediate consists of a folded c-terminal domain and a still unfolded n-terminal domain. our prediction is consistent with these experimental results. other proteins the b domain of staphylococcus aureus protein a consists of three α-helices. in our prediction, α and α interact first, then α is added. this is consistent with the result of the out-exchange experiment in and experimental results under high temperature. although two members of the globin protein family, leghemoglobin a and myoglobin, have very low sequence similarity, they both consist of eight α-helices and have very similar tertiary structures. nishimura et al compared their folding pathways experimentally. for leghemoglobin a, αg, αh, and part of αe form stable structures first, while αa and αb form in the later stages of the folding pathway. for myoglobin, αa, αg and αh form stable contacts first. the main difference between the two folding pathways is that αa and αb form earlier in the folding pathway of myoglobin than in the folding pathway of leghemoglobin a. our predictions are able to distinguish between these subtle differences. for leghemoglobin a, αg and αh are predicted to interact first, then αe is added, with αb and αa added later. for myoglobin, αg and αh are also predicted to interact first, then αa is added, followed by αe and αb. there are two crystal structures for chymotrypsin inhibitor. while 2ci consists of residues, 1coa is a fragment of 2ci from residues to they both consist of one α-helix and four β-strands, which are arranged as β1α1β2β3β in 1coa and β1α1β4β3β in 2ci in our predictions, 1coa and 2ci have the same folding pathway, with the middle two β-strands interacting first, then the α-helix is added, followed by the c-terminal β-strand, and the n-terminal β-strand is added last. for 1coa, simulation by demonstrated that β and β form contacts first, then α is added to form a folding nucleus. the coalescence of β is the rate-limiting step and is completed at the end of the folding process. this is consistent with the result of the out-exchange experiment in that showed that β β and α form contacts first. our prediction is consistent with these results. the all β-sheet protein cardiotoxin iii consists of five strands. while β and β form a double-stranded domain, β β and β form a triple-stranded domain. by the amide proton pulse exchange experiment, sivaraman et al showed that the triple-stranded domain forms earlier than the double-stranded domain during the refolding process. the carbonyl groups in β and the amide groups in β form hydrogen bonding partners, which are important for the formation of a hydrophobic cluster. our prediction is consistent with these results, with β and β interacting first, then β is added to form the triple-stranded domain, followed by β and β in the double-stranded domain. bovine pancreatic trypsin inhibitor bpti is a globular protein with two α-helices and three β-strands, which are arranged as α1β2β1β3α three disulfide bonds between residues and and and and play an important role in stabilizing the native structure, and their formation order was studied in. in our prediction, β and β interact first, then α is added. this brings residues and close together and helps to form the disulfide bond between them. then α is added and this helps to form the disulfide bond between residues and and and our prediction that β and β interact earlier than the two α-helices is consistent with the result in. discussion while our strategy corresponds most closely to the diffusion-collision model that allows folding to proceed independently in different parts of a protein, it is possible to use a modified strategy for other models. for example, to simulate the nucleation-propagation model or the nucleation-condensation model, in which the existence of a nucleus facilitates further folding, one can iteratively add a sse that results in the lowest free energy to the nucleus. since energy computations can still be slow and can take hours, which account for significant amount of computation time in our algorithm, it is also possible to use lower resolution methods to compute energy. while our strategy finds the most energetically favorable protein folding pathway, there are evidences that multiple folding pathways exist. the ability to analyze multiple folding pathways will also allow the study of protein misfolding. our approach can be generalized to study the entire free energy landscape as follows: construct a graph in which each vertex represents a biologically plausible conformation and each edge represents a feasible conformation change, which is similar to the roadmap graph in and and the protein folding network in except that we consider each sse as an indivisible unit. various graph-theoretic algorithms can then be used to generate predictions of alternative folding pathways.  we have shown that our procedure has sufficient accuracy to distinguish between subtle differences and our strategy can be applied to large proteins due to its speed. an important future direction is to consider cooperative folding of secondary structures without too much sacrifice in speed, that is, when folding in one secondary structure affects folding in others. authors' contributions qy performed the research and implemented the algorithm. s–hs supervised the research. all authors read and approved the final manuscript. 
by assuming that the native structure of a protein is known and representing each intermediate conformation as a collection of fully folded structures in which each of them contains a set of interacting secondary structure elements, we show that it is possible to significantly reduce the conformation space while still being able to predict the most energetically favorable folding pathway of large proteins with hundreds of residues at the mesoscopic level, including the pig muscle phosphoglycerate kinase with residues. since experimental determination of protein folding pathways remains difficult, computational techniques are often used to simulate protein folding. such a strategy is often the only feasible choice for large proteins. the model is detailed enough to distinguish between different folding pathways of structurally very similar proteins, including the streptococcal protein g and the peptostreptococcal protein l. the model is also able to recognize the differences between the folding pathways of protein g and its two structurally similar variants nug and nug which are even harder to distinguish. our technique is efficient enough to predict folding pathways for both large and small proteins at the mesoscopic level. most current techniques to predict protein folding pathways are computationally intensive and are suitable only for small proteins.
 since experimental determination of protein folding pathways remains difficult, computational techniques are often used to simulate protein folding. most current techniques to predict protein folding pathways are computationally intensive and are suitable only for small proteins.  by assuming that the native structure of a protein is known and representing each intermediate conformation as a collection of fully folded structures in which each of them contains a set of interacting secondary structure elements, we show that it is possible to significantly reduce the conformation space while still being able to predict the most energetically favorable folding pathway of large proteins with hundreds of residues at the mesoscopic level, including the pig muscle phosphoglycerate kinase with residues. the model is detailed enough to distinguish between different folding pathways of structurally very similar proteins, including the streptococcal protein g and the peptostreptococcal protein l. the model is also able to recognize the differences between the folding pathways of protein g and its two structurally similar variants nug and nug which are even harder to distinguish. we show that this strategy can produce accurate predictions on many other proteins with experimentally determined intermediate folding states.  our technique is efficient enough to predict folding pathways for both large and small proteins at the mesoscopic level. such a strategy is often the only feasible choice for large proteins. a software program implementing this strategy is available at. 