Reducing the computational complexity of protein folding via fragment folding and assembly

Abstract

Understanding, and ultimately predicting, how a 1-D protein chain reaches its native 3-D fold has been one of the most challenging problems during the last few decades. Data increasingly indicate that protein folding is a hierarchical process. Hence, the question arises as to whether we can use the hierarchical concept to reduce the practically intractable computational times. For such a scheme to work, the first step is to cut the protein sequence into fragments that form local minima on the polypeptide chain. The conformations of such fragments in solution are likely to be similar to those when the fragments are embedded in the native fold, although alternate conformations may be favored during the mutual stabilization in the combinatorial assembly process. Two elements are needed for such cutting: (1) a library of (clustered) fragments derived from known protein structures and (2) an assignment algorithm that selects optimal combinations to "cover" the protein sequence. The next two steps in hierarchical folding schemes, not addressed here, are the combinatorial assembly of the fragments and finally, optimization of the obtained conformations. Here, we address the first step in a hierarchical protein-folding scheme. The input is a target protein sequence and a library of fragments created by clustering building blocks that were generated by cutting all protein structures. The output is a set of cutout fragments. We briefly outline a graph theoretic algorithm that automatically assigns building blocks to the target sequence, and we describe a sample of the results we have obtained.

Figure 1.

Folding by parts and part assembly: A hierarchy-based protein folding scheme. The overall folding scheme, composed of three steps: The first step involves cutting the target sequence into building blocks and assigning their conformations (this stage is described in this work). In the second step, the building blocks are assembled combinatorially. In the third step, the structure is refined to yield the predicted conformation.

Figure 2.

Two examples of clusters. The figures show multiple structural alignments using MUSTA (Leibowitz et al. 2001a,b) of the cluster members. The inserts give the file names and the range of residues. (A) (1bdc) Immunoglobulin-binding protein A modules from Staphylococcus aureus (domain B); (1grl) GroEL from Escherichia coli; (2pas) parvalbumin from pike; (1edi) immunoglobulin-binding protein A modules from S. aureus (domain E). (B) (1coy) Cholesterol oxidase from Brevibacterium sterolicum; (1gal) glucose oxidase from Aspergillus niger; (1gnd) guanine nucleotide dissociation inhibitor, GDI, from cow; (1ldm) lactate dehydrogenase from dogfish.

Figure 3.

A flowchart of the building block assignment algorithm.

Figure 4.

An illustration of the building block assignment algorithm. (A) The protein sequence is aligned against a building block sequence database using BLAST. (B) A weighted directed acyclic graph is built from the aligned building blocks, plus start and target vertices. (C) The "shortest" path is the "best" building block assignment to the target sequence.

Figure 5.

Examples of the building block assignment algorithm. (A) The target protein is chain A of glutathione S-transferase from human, class pi (PDB code 13gs). (B) The target protein is pseudoazurin from Alcaligenes faecalis (PDB code 1paz). (C) The target protein is immunoglobulin from human (PDB code 2imm). (D) The target protein is chain D of barstar (barnase inhibitor) from Bacillus amyloliquefaciens (PDB code 1brs). (E) The target protein is chain A of anti-sigma factor antagonist SpoIIaa from Bacillus sphaericus (PDB code 1h4x). (F) The target protein is Clp protease, ClpP subunit from Escherichia coli (PDB code 1tyf). The inserts shows the matched building block sequences. (See also Table 2.)

Figure 5.

Examples of the building block assignment algorithm. (A) The target protein is chain A of glutathione S-transferase from human, class pi (PDB code 13gs). (B) The target protein is pseudoazurin from Alcaligenes faecalis (PDB code 1paz). (C) The target protein is immunoglobulin from human (PDB code 2imm). (D) The target protein is chain D of barstar (barnase inhibitor) from Bacillus amyloliquefaciens (PDB code 1brs). (E) The target protein is chain A of anti-sigma factor antagonist SpoIIaa from Bacillus sphaericus (PDB code 1h4x). (F) The target protein is Clp protease, ClpP subunit from Escherichia coli (PDB code 1tyf). The inserts shows the matched building block sequences. (See also Table 2.)

Figure 5.

Examples of the building block assignment algorithm. (A) The target protein is chain A of glutathione S-transferase from human, class pi (PDB code 13gs). (B) The target protein is pseudoazurin from Alcaligenes faecalis (PDB code 1paz). (C) The target protein is immunoglobulin from human (PDB code 2imm). (D) The target protein is chain D of barstar (barnase inhibitor) from Bacillus amyloliquefaciens (PDB code 1brs). (E) The target protein is chain A of anti-sigma factor antagonist SpoIIaa from Bacillus sphaericus (PDB code 1h4x). (F) The target protein is Clp protease, ClpP subunit from Escherichia coli (PDB code 1tyf). The inserts shows the matched building block sequences. (See also Table 2.)

Figure 5.

Examples of the building block assignment algorithm. (A) The target protein is chain A of glutathione S-transferase from human, class pi (PDB code 13gs). (B) The target protein is pseudoazurin from Alcaligenes faecalis (PDB code 1paz). (C) The target protein is immunoglobulin from human (PDB code 2imm). (D) The target protein is chain D of barstar (barnase inhibitor) from Bacillus amyloliquefaciens (PDB code 1brs). (E) The target protein is chain A of anti-sigma factor antagonist SpoIIaa from Bacillus sphaericus (PDB code 1h4x). (F) The target protein is Clp protease, ClpP subunit from Escherichia coli (PDB code 1tyf). The inserts shows the matched building block sequences. (See also Table 2.)

Figure 5.

Examples of the building block assignment algorithm. (A) The target protein is chain A of glutathione S-transferase from human, class pi (PDB code 13gs). (B) The target protein is pseudoazurin from Alcaligenes faecalis (PDB code 1paz). (C) The target protein is immunoglobulin from human (PDB code 2imm). (D) The target protein is chain D of barstar (barnase inhibitor) from Bacillus amyloliquefaciens (PDB code 1brs). (E) The target protein is chain A of anti-sigma factor antagonist SpoIIaa from Bacillus sphaericus (PDB code 1h4x). (F) The target protein is Clp protease, ClpP subunit from Escherichia coli (PDB code 1tyf). The inserts shows the matched building block sequences. (See also Table 2.)

Figure 5.

Examples of the building block assignment algorithm. (A) The target protein is chain A of glutathione S-transferase from human, class pi (PDB code 13gs). (B) The target protein is pseudoazurin from Alcaligenes faecalis (PDB code 1paz). (C) The target protein is immunoglobulin from human (PDB code 2imm). (D) The target protein is chain D of barstar (barnase inhibitor) from Bacillus amyloliquefaciens (PDB code 1brs). (E) The target protein is chain A of anti-sigma factor antagonist SpoIIaa from Bacillus sphaericus (PDB code 1h4x). (F) The target protein is Clp protease, ClpP subunit from Escherichia coli (PDB code 1tyf). The inserts shows the matched building block sequences. (See also Table 2.)