^{1}, S. C. Kou

^{1}and Jun S. Liu

^{1,a)}

### Abstract

An efficient exploration of the configuration space of a biopolymer is essential for its structure modeling and prediction. In this study, the authors propose a new Monte Carlo method, fragment regrowth via energy-guided sequential sampling (FRESS), which incorporates the idea of multigrid Monte Carlo into the framework of configurational-bias Monte Carlo and is suitable for chain polymer simulations. As a by-product, the authors also found a novel extension of the Metropolis Monte Carlo framework applicable to all Monte Carlo computations. They tested FRESS on hydrophobic-hydrophilicprotein folding models in both two and three dimensions. For the benchmark sequences, FRESS not only found all the minimum energies obtained by previous studies with substantially less computation time but also found new lower energies for all the three-dimensional models with sequence length longer than 80 residues.

One of the authors (S.C.K.) was supported in part by a NSF CAREER Award No. DMS-0449204. Two of the authors (J.S.L. and J.Z.) were supported in part by the NSF Grant No. DMS-0244638 and NIH Grant Nos. R01-GM078990 and R01-HG02518-02.

I. INTRODUCTION

II. RESULTS

A. Folding sequences

B. Generalized Metropolis-Hastings framework

III. DISCUSSION

IV. METHOD

A. FRESS algorithm for chain polymer simulation

B. Justification and modification

### Key Topics

- Sequence analysis
- 14.0
- Monte Carlo methods
- 9.0
- Polymers
- 6.0
- Proteins
- 6.0
- Biopolymers
- 3.0

## Figures

An example of fragment growth on the 2D square lattice. (a) One step of FRESS move, with dashed border in (1) indicating the regrown segment. (b) Under FRESS the global minimum energy conformation B can be reached from a compact conformation A in just four steps when the maximum allowed fragment length is set to six. Residues enclosed in the dashed lines are the fragments to be regrown. The sequence and its ground state were taken from Ref. 32.

An example of fragment growth on the 2D square lattice. (a) One step of FRESS move, with dashed border in (1) indicating the regrown segment. (b) Under FRESS the global minimum energy conformation B can be reached from a compact conformation A in just four steps when the maximum allowed fragment length is set to six. Residues enclosed in the dashed lines are the fragments to be regrown. The sequence and its ground state were taken from Ref. 32.

Sample conformations with the minimum energies newly discovered by FRESS. (a) A conformation of sequence 3D88 with . (b) A conformation of sequence 3D103 with . (c) A conformation of sequence 3D124 with . (d) A conformation of sequence 3D136 with .

Sample conformations with the minimum energies newly discovered by FRESS. (a) A conformation of sequence 3D88 with . (b) A conformation of sequence 3D103 with . (c) A conformation of sequence 3D124 with . (d) A conformation of sequence 3D136 with .

## Tables

Comparison of performances of different methods on ten benchmark 3D sequences (Ref. 10). The setting for FRESS: starting temperature , minimum temperature , and temperature decreasing by 0.98 geometrically; fragment lengths between 2 and 12; and 50 000 moves at each temperature. ST: standard local moves with 2 000 000 moves at each temperature; other settings are the same as FRESS. Rows 2–11: the minimum energy (time spent on each run in minutes) found by the corresponding method. Row 12: the number of sequences for which the minimum energy conformations were found (the average time spent on the searches). The CPUs of the computers used to obtain the results are: FRESS and ST, PC; nPERMis, PC; nPERMh, PC; ACO, PC; CG, SPARC I workstation.

Comparison of performances of different methods on ten benchmark 3D sequences (Ref. 10). The setting for FRESS: starting temperature , minimum temperature , and temperature decreasing by 0.98 geometrically; fragment lengths between 2 and 12; and 50 000 moves at each temperature. ST: standard local moves with 2 000 000 moves at each temperature; other settings are the same as FRESS. Rows 2–11: the minimum energy (time spent on each run in minutes) found by the corresponding method. Row 12: the number of sequences for which the minimum energy conformations were found (the average time spent on the searches). The CPUs of the computers used to obtain the results are: FRESS and ST, PC; nPERMis, PC; nPERMh, PC; ACO, PC; CG, SPARC I workstation.

Benchmark sequences longer than 50 residues.

Benchmark sequences longer than 50 residues.

Comparison of performances of different methods on 2D HP sequences. NA means data not available. The number in each cell is the minimum energy obtained by the corresponding method for the respective HP sequence.

Comparison of performances of different methods on 2D HP sequences. NA means data not available. The number in each cell is the minimum energy obtained by the corresponding method for the respective HP sequence.

Comparison of performances of different methods on 3D sequences longer than 50 residues. The numbers are the minimum energies found by a particular method; and the numbers in parentheses are times in hours for the searches. “NA” means data not available. The parameter setting of FRESS for 3D88 and 3D103 are starting temperature , lowest temperature , and temperature decreasing by 0.995 geometrically; moves at each temperature; and fragment lengths from 2 to 16. The setting for 3D124 and 3D136 is the same as above except the number of moves at each temperature is and , respectively. The CPUs of the computers used to obtain the results: FRESS, PC; nPERMh, PC; nPERMis, PC. The reported lowest energies for sequences 3D124 and 3D136 were found in less than two weeks.

Comparison of performances of different methods on 3D sequences longer than 50 residues. The numbers are the minimum energies found by a particular method; and the numbers in parentheses are times in hours for the searches. “NA” means data not available. The parameter setting of FRESS for 3D88 and 3D103 are starting temperature , lowest temperature , and temperature decreasing by 0.995 geometrically; moves at each temperature; and fragment lengths from 2 to 16. The setting for 3D124 and 3D136 is the same as above except the number of moves at each temperature is and , respectively. The CPUs of the computers used to obtain the results: FRESS, PC; nPERMh, PC; nPERMis, PC. The reported lowest energies for sequences 3D124 and 3D136 were found in less than two weeks.

Performances of FRESS on ten benchmark 3D sequences under five parameter settings. Last row: the number of sequences for which the minimum energy conformations were found (the average time spent on the searches) in the end. Each cell contains the minimum energy (and the time spent in minutes on each run) reached under the respective condition for the respective sequence. For all the sequences, starting temperature , minimum temperature , and temperature decreasing by 0.98 geometrically. FRESS (best): fragment lengths are chosen between 2 and 12, with moves at each temperature; : fragment lengths are chosen from 2 to 4, moves at each temperature; : fragment length is fixed to 12, moves at each temperature; NIS: no importance sampling used, moves at each temperature; NR: without DFS for fragment regrowth, moves at each temperature.

Performances of FRESS on ten benchmark 3D sequences under five parameter settings. Last row: the number of sequences for which the minimum energy conformations were found (the average time spent on the searches) in the end. Each cell contains the minimum energy (and the time spent in minutes on each run) reached under the respective condition for the respective sequence. For all the sequences, starting temperature , minimum temperature , and temperature decreasing by 0.98 geometrically. FRESS (best): fragment lengths are chosen between 2 and 12, with moves at each temperature; : fragment lengths are chosen from 2 to 4, moves at each temperature; : fragment length is fixed to 12, moves at each temperature; NIS: no importance sampling used, moves at each temperature; NR: without DFS for fragment regrowth, moves at each temperature.

Article metrics loading...

Full text loading...

Commenting has been disabled for this content