Su et al. Proteome Science 2011, 9(Suppl 1):S19
http://www.proteomesci.com/content/9/S1/S19

PROCEEDINGSOpen Access

An effective hybrid of hill climbing and genetic
algorithm for 2D triangular protein structure
prediction
Shih-Chieh Su1†, Cheng-Jian Lin2*†, Chuan-Kang Ting1*†
From International Workshop on Computational Proteomics
Hong Kong, China. 18-21 December 2010

Abstract
Background: Proteins play fundamental and crucial roles in nearly all biological processes, such as, enzymatic
catalysis, signaling transduction, DNA and RNA synthesis, and embryonic development. It has been a long-standing
goal in molecular biology to predict the tertiary structure of a protein from its primary amino acid sequence. Fromvisual comparison, it was found that a 2D triangular lattice model can give a better structure modeling andprediction for proteins with short primary amino acid sequences.
Methods: This paper proposes a hybrid of hill-climbing and genetic algorithm (HHGA) based on elite-based
reproduction strategy for protein structure prediction on the 2D triangular lattice.
Results: The simulation results show that the proposed HHGA can successfully deal with the protein structure
prediction problems. Specifically, HHGA significantly outperforms conventional genetic algorithms and iscomparable to the state-of-the-art method in terms of free energy.
Conclusions: Thanks to the enhancement of local search on the global search, the proposed HHGA achieves
promising results on the 2D triangular protein structure prediction problem. The satisfactory simulation results
demonstrate the effectiveness of the proposed HHGA and the utility of the 2D triangular lattice model for protein
structure prediction.

Introduction
Since the presence of HP lattice model [1], heuristic
search algorithms for a variety of lattice models havebeen proposed and proven useful to explore the relationship between the primary amino acid sequence andits native folding structure, particularly in the protein
folding problem (PFP) and the protein structure prediction (PSP). The main purpose of the HP lattice model isto understand the physicochemical principle of protein
folding during the modeling process of searching for thelowest free-energy conformation of a protein.
* Correspondence: cjlin@ncut.edu.tw; ckting@cs.ccu.edu.tw† Contributed equally1
Department of Computer Science and Information Engineering, National
Chung Cheng University, Chiayi 62102, Taiwan, R.O.C
2
Department of Computer Science and Information Engineering, National
Chin-Yi University of Technology, Taichung 41101, Taiwan, R.O.C
Full list of author information is available at the end of the article

Despite the difference in modeling accuracy, both
high-resolution and low-resolution models can contribute to an understanding of the protein structure
obtained from experiments, such as NMR and crystallography. Moreover, they have various applications in protein modification, protein-ligand and protein-protein
interactions [2]. Table 1 summarizes the relationshipbetween modeling accuracy and the related applications.
To improve the modeling accuracy, several latticemodels have been developed and proposed. The present
study compares four popular lattice models in terms ofvisual comparison, including 2D square and triangularlattice models, 3D cubic lattice model and face-centeredcubic (FCC). The protein structures obtained from thefour modeling types were compared with reported ‘real’
biological protein structures. As Figure 1 shows, the 2D
triangular lattice model can give a better structure© 2011 Su et al; licensee BioMed Central Ltd. This is an open access article distributed under the terms of the Creative Commons
Attribution License (http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction inany medium, provided the original work is properly cited.

Su et al. Proteome Science 2011, 9(Suppl 1):S19
http://www.proteomesci.com/content/9/S1/S19

Table 1 The relationship between modeling accuracy andthe related application.
Accuracy

Application<30%

Refining NMR structures
Finding binding/active sites by 3D motif searching
Annotating function by fold assignment

30%60%

Molecular replacement in crystallography
Supporting site-directed mutagenesis>60%

Comparable to medium-resolution NMR, low-resolution
crystallography
Docking of small ligands, proteins

This table illustrates the accuracy of protein modeling and its related
application [2].

modeling and prediction for proteins with short primaryamino acid sequences.
In solving this prediction problem, Hart and Istrail [4]first gave a 1/4 (25%) approximation for the problem of
the 2D square lattice and a 3/8 (38%) approximation forthe problem of the 3D cubic lattice. Agarwala et al. [5]Page 2 of 8

gave a 6/11 (54%) approximation for the problem, whichis consistent with our experimental results.
Many researchers have favored and focused researchon the square lattice model because it has many associated benchmarks, large amount of data accumulated
over the years, and the availability of comparison withdifferent strategies and modeling methods. By contrast,
little work has been done on the 2D triangular latticemodel. In this paper, we proposed a genetic algorithmwith elite-based reproduction strategy (ERS-GA). Basedon ERS-GA, this study further develops a hybrid of hillclimbing and genetic algorithm (HHGA) for protein
structure prediction on the 2D triangular lattice. Experimental results were conducted to validate the effectiveness of this method.
The remainder of this paper is structured as follows:
Section II gives the preliminaries and the definition of
the protein structure prediction problem in the HP 2D
triangular lattice model. Section III describes the

Figure 1 Four different types of lattice model for visual comparison taking the protein with the PDB id: 1A0Ma as the example. Visualcomparison for PDB id: 1A0Ma. (a) Real protein structure; (b) and (c) are 2D square and triangular lattice model simulation results. Black-filled
dots indicate Hydrophobic amino acids and white dots denote hydrophilic amino acid. (d) and (e) are 3D square and face-centered cubic (FCC)
lattice model simulation results from CPSP-tools [3]. In (d) and (e), green balls indicate hydrophobic amino acids while the gray balls indicate thehydrophilic amino acids.

Su et al. Proteome Science 2011, 9(Suppl 1):S19
http://www.proteomesci.com/content/9/S1/S19

Page 3 of 8

methodology used in the study. The comparison of
results is presented and discussed in Section IV followedby the conclusion in Section V.

Preliminaries
Proteins play fundamental and crucial roles in nearly all
biological processes, such as, enzymatic catalysis, signaling transduction, DNA and RNA synthesis, and embryonic development. It has been a long-standing goal ofmolecular biology to predict the tertiary structure of aprotein from its primary amino acid sequence [6,7].
This paper emphasizes research on ab initio modeling,
among which the 2D HP triangular lattice model isthought to be the best two-dimensional model in protein structure prediction at present.
HP lattice model

The HP lattice model [1] is the most frequently usedmodel, which is based on the observation that thehydrophobic interaction between amino acid residues isthe driving force for protein folding and for development of native state in proteins [8]. In this model, eachamino acid is classified based on its hydrophobicity asan H (hydrophobic or non-polar) or a P (hydrophilic or
polar). The HP lattice model allows HP protein
sequences to be configured as self-avoiding walks(SAW) on the lattice path favoring an energy free stateaccording to HH interaction. The energy of a given conformation is defined as the number of topological neighboring (TN) contacts between H’s that are not adjacentin the sequence. Figure 2 shows an example for the 2D
triangular lattice model.
Calculation of free energy

The free energy of a protein can be calculated by thefollowing formulae [9]:⎧ −1.0 the pair of H and H residues∈ij = ⎨
⎩ 0.0 othersE=∑ Δr ∈ ,
ij

ij

(1)

(2)

i, j

where the parameter⎧ 1 S i and S j are adjacent but not connected amino acids
Δrij = ⎨⎩ 0 others(3)

Protein folding can then be transformed into an optimization problem for the conformation with minimal
free energy. Formally, given an HP sequence s = s1s2…
sn, find a conformation of s with minimum energy. Thatis, the problem is to find c* Î C(s) such that E(c*) =Figure 2 An optimal conformation in a 2D triangular latticemodel. An optimal conformation for the sequence (HP)2PH(HP)2(PH)2
HP(PH)2 in a 2D triangular lattice model. The black filled dots
denote the hydrophobic amino acid and the red open circles
denote the hydrophilic amino acids. The H-H contacts (free energy)
in the conformation are assigned the energy value of -1. The freeenergy is defined as a minimum value; the maximum number of HH contact is given in the case of two-dimensional models, Figure 2
illustrates a protein structure with 15 H-H contacts (energy= -15).

min{E(c)|c Î C(s)}, where C(s) is the set of all valid conformations for s [10].
Triangular lattice model

A significant drawback of the cubic lattice [5] is that, if
two residues are at any even distance in the primary
sequence, they cannot be in topological contact with
one another when the protein is embedded in this lattice. In other words, on the square lattice, two aminoacids in contact in any folding must be at odd distanceaway in the protein sequence [5]. To address this issue,
Joel et al. [11] introduced the 2D triangular latticemodel. As Figure 3 shows, each lattice point has sixneighbors in the two-dimensional triangular lattice.
Since each residue has two covalent neighbors, except
the first and the last residues, a residue at a lattice point
can be in topological contact with at most four otherresidues. Thus, each residue is involved in up to four HH contacts [11].
With the unit vectors obtained from the triangular lattice, it is much easier to model protein conformation ona two-dimensional triangular lattice without exhibiting
the parity problem [5]. However, the lattice model ofprotein conformation as a self-avoiding walk is NP-complete [12]. To solve this problem, some heuristic searchalgorithms [13-18] have been developed for various lattice models. Backofen and Will [21] utilized advanced
techniques such as constraint programming to calculateSu et al. Proteome Science 2011, 9(Suppl 1):S19
http://www.proteomesci.com/content/9/S1/S19

Page 4 of 8

all optimal side-chain structures of a given sequence,and proved their optimality [3]. Further, Böckenhauer et
al. [15] extended the library by implementing the 2D triangular lattice and the pull move set for triangular lattice models.
In this paper, we developed an effective hybrid of local
search and genetic algorithm (GA) to resolve this problem. The performance is examined and compared to
the results in [15]. More details about the proposed
algorithm are presented in the next section.

Figure 3 The 2D triangular lattice model neighbors of vertex(x, y).

Figure 4 Flowchart of the elite-based reproduction strategy (ERS).

Methods
This paper introduces the elite-based reproduction strategy to GA as the ERS-GA. Further, we propose a hybridof hill-climbing and ERS-GA, called the HHGA, for protein structure prediction on the 2D triangular lattice.

Su et al. Proteome Science 2011, 9(Suppl 1):S19
http://www.proteomesci.com/content/9/S1/S19

The proposed HHGA, in essence, is a combination of
global search algorithm with local search operator.
Restated, HHGA works within the framework of ERSGA and adopts hill-climbing to enhance its exploitation
capability. Figures 4 and 5 show the flow charts of the
proposed ERS-GA and HHGA. The following subsections describe the operators of ERS-GA and HHGA.
Initialization

For an input amino acid sequence of length n, a candidate conformation in the 2D triangular lattice [11,14] is
encoded as a chromosome in the form of a string oflength (n – 1) over symbols {L, R, LU, LD, RU, RD},
denoting the fold directions left, right, left-up, left-down,right-up and right-down, respectively. An initial population is generated randomly in the (n – 1) dimensional
space within a predetermined range. In this paper,
population size was set at 200 empirically.
Each chromosome in the population needs to be evaluated for its fitness. Here we directly use equation (2) offree energy as the fitness function. The goal for an optimization algorithm like HHGA is to minimize the fitness value, namely, free energy. The evaluatedchromosomes are sorted according to their fitness

Page 5 of 8

values. This sorted population serves as the basis of subsequent reproduction process.
Elite-Based Reproduction Strategy (ERS)

Reproduction is a process in which the information ofcandidate solutions are modified and copied, depending
upon their fitness values. The reproduction in GA consists of selection, crossover, and mutation. For the ERSGA and HHGA, this study adopts the elite-based reproduction strategy, which keeps the top half of the population to the next generation and generates offspring byperforming crossover and mutation on the second halfof the population [19]. In the experiments, this study
uses two-point crossover with crossover ate 0.8 and uniform mutation with mutation rate 0.4.
Local search

Two local search operators are proposed for the protein
structure prediction problem. First, given the current
solution, local search I chooses its neighbor residues,
which are generated in a way similar to mutation operation: i.e., randomly changing its direction. Consequently,
if the fitness value of a neighbor is better than the current solution, this neighbor residue will be accepted toreplace the current one.
In local search II, the neighbor residues are generated
in a way similar to crossover operation. That is, fiveneighbors are created by changing the direction of thesecond segment after the crossover point, where rotation angles are 60°, 120°, 180°, 240° and 300°, respectively. If any of the five folding directions leads to asuperior fitness to the original direction, this neighborwill replace the current solution.
Termination condition

Genetic algorithm requires a termination condition tostop the evolutionary process and return the final result.
In this study, the experiments ran ERS-GA and HHGA
for a maximum of 200 generations. The best chromosome of the population is then returned as the final
result.

Figure 5 Flowchart of the hybrid of hill-climbing and genetic
algorithms (HHGA)

Numerical Results
Table 2 lists the eight benchmark sequences in our
experiments. These sequences have been used for the2D square HP model [20]; however, in the 2D triangularHP model the minimum energy of these benchmarks
was still unknown. The comparison with previous studies provided a means of demonstrating the effectiveness of the method described here.
The experiments were conducted in two steps. First,
ERS-GA was used to predict the protein structure toevaluate the efficacy of this method. Tables 3 and 4
summarize the results and compare them with priorSu et al. Proteome Science 2011, 9(Suppl 1):S19
http://www.proteomesci.com/content/9/S1/S19

Page 6 of 8

Table 2 The benchmarks for the 2D triangular lattice HP
model.

Table 4 Comparison of a hybrid of hill-climbing and GA(HHGA) with the tabu search (TS).

Seq.

LengthProtein Sequence

Seq.

LengthTS [15]

HHGA

1

20

(HP)2PH(HP)2(PH)2HP(PH)2

1

20

-15

-15

Fig. 6(a)224

H2P2(HP2)6H2

2

24

-17

-17

Fig. 6(b)

3

25

3

25

-12

-12

Fig. 6(c)P2HP2(H2P4)3H2
2 22 5 5

2 22 2

22

Conformation

4

36

P(P H ) P H (H P ) P H(HP )

4

36

-24

-23

Fig. 6(d)548

P2H(P2H2)2P5H10P6(H2P2)2HP2H5

5

48

-40

-41

Fig. 6(e)650

H2(PH)3PH4PH(P3H)2P4(HP3)2HPH4(PH)3PH2

6

50

-

-38

Fig. 6(f)3 2 5 3 10

3 12 4 62

760

P(PH ) H P H PHP H P H PH PHP

7

60

-70

-66

Fig. 6(g)864

H12(PH)2((P2H2)2P2H)3(PH)2H11

8

64

-50

-63

Fig. 6(h)Figures in bold indicate the lowest energy.

work. According to the results in Table 3, the proposed
ERS-GA significantly outperforms simple genetic algorithm (SGA) and hybrid genetic algorithm (HGA).
Next, the HHGA integrates the hill-climbing local
search into the ERS-GA approach for performance
improvement. Table 5 shows that this hybrid algorithm, i.
e., HHGA, can effectively enhance the performance andperforms comparably with the tabu search proposed by[15]. This comparative outcome demonstrates that HHGA
is a similarly good approach as the state-of-the-art method
in protein structure prediction. Figure 6 plots the structures obtained from HHGA for eight protein sequences.
Table 5 further presents the comparison of the ERSGA with the HHGA, where each algorithm was run for
30 times. The average running time was measured onIntel i7-920 machines. The experimental results showthat HHGA achieves better solution quality, i.e. lower
energy, than ERS-GA does on all the benchmarks. Thisvalidates the effectiveness of the local search in HHGA.
On the other hand, HHGA gains this advantage at thecost of running time.

Conclusions
In the ab initio technique, the lattice model is one of
the most frequently used methods in protein structure
Table 3 Comparison of the proposed approach with thesimple genetic algorithm (SGA) and hybrid genetic
algorithm (HGA).
Seq.

Length

SGA [14]

HGA [14]

ERS-GA

1

20

-11

-15

-15

2

24

-10

-13

-13

3

25

-10

-10

-12

4

36

-16

-19

-20

5

48

-26

-32

-32

6

50

-21

-23

-30

7

60

-40

-46

-55

8

64

-33

-46

-47

Figures in bold indicate the lowest energy.

prediction. From visual comparison, however, it was
found that the 2D triangular lattice model can yield better structure modeling sequences and prediction forproteins with short primary amino acid sequences.
Meanwhile, it was realized that the 2D triangular latticemodel has rarely been used in protein structure
prediction.
This paper has highlighted this interesting issue andprovides a short introduction to the working method for
2D triangular lattice models. Furthermore, the paper
proposes the genetic algorithm with elite-based reproduction strategy (ERS-GA) and a hybrid of hill-climbing
and genetic algorithms (HHGA) for protein structure
prediction on the 2D triangular lattice. The simulation
results show that ERS-GA and HHGA can successfully
be applied to the problem of protein structure prediction. The satisfactory simulation results validate theTable 5 Comparison of ERS-GA with HHGA in free energy
obtained (Mean/Best) and average running time.
Seq.

Len.

Label

ERS-GA

HHGA

Conformation

1

20

Mean/Best-12.5/-15-14.73/-15

Fig. 6(a)Avg. Run Time

24.24

273.23

2

24

3

25

4

36

5
6
7
8

48
50
60
64

Mean/Best-10.2/-13-14.93/-17

Avg. Run Time

65.78

378.99Mean/Best-8.47/-12-11.57/-12

Avg. Run Time

70.52

403.84Mean/Best-16.17/-20-21.27/-23

Avg. Run Time

135.68713.55

Mean/Best-28.13/-32-37.3/-41

Avg. Run Time

246.711173.2

Mean/Best-25.3/-30

34.1/-38

Avg. Run Time

254.671246.1

Mean/Best-49.43/-55-61.83/-66

Avg. Run Time

366.38

1878.3

Mean/Best-42.37/-47-56.53/-63

Avg. Run Time

423.131944.7

Figures in bold indicate the lowest energy.

Fig. 6(b)Fig. 6(c)Fig. 6(d)Fig. 6(e)Fig. 6(f)Fig. 6(g)Fig. 6(h)Su et al. Proteome Science 2011, 9(Suppl 1):S19
http://www.proteomesci.com/content/9/S1/S19

Page 7 of 8

Figure 6 (a) to (h) Results of the structure of eight protein sequences.

effectiveness of the proposed algorithms; in addition,
they demonstrate that the 2D triangular lattice model ispromising for protein structure prediction.

This article has been published as part of Proteome Science Volume 9
Supplement 1, 2011: Proceedings of the International Workshop on
Computational Proteomics. The full contents of the supplement are available
online at http://www.proteomesci.com/supplements/9/S1.

Acknowledgements
We would like thank Dr. Roy Preece at Oxford Brookes University for the
proofreading of the manuscript and Dr. Lihui Wang at Imperial College
London for advice on writing of the manuscript.

Author details
1
Department of Computer Science and Information Engineering, National
Chung Cheng University, Chiayi 62102, Taiwan, R.O.C. 2Department ofComputer Science and Information Engineering, National Chin-Yi Universityof Technology, Taichung 41101, Taiwan, R.O.C.

Su et al. Proteome Science 2011, 9(Suppl 1):S19
http://www.proteomesci.com/content/9/S1/S19

Authors’ contributions
SSC carried out studies on the protein folding prediction models,participated in the design and experiments of the genetic algorithm, anddrafted the manuscript. LCJ conceived of the study and participated in thedesign of genetic algorithm. TCK conceived of the study, participated in thedesign and experiments of the genetic algorithm, and drafted themanuscript.
All authors read and approved the final manuscript.
Competing interests
The authors declare that they have no competing interests.

Page 8 of 8

20. Jiang T, Cui Q, Shi G, Ma S: Protein folding simulations for thehydrophobic-hydrophilic model by combining tabu search with genetic
algorithms. Journal of Chemical Physics 2003, 119:4592-4596.
21. Backofen R, Will S: A constraint-based approach to fast and exact
structure prediction in three-dimensional protein models. Constraints
2006, 11:5-30.
doi:10.1186/1477-5956-9-S1-S19
Cite this article as: Su et al.: An effective hybrid of hill climbing andgenetic algorithm for 2D triangular protein structure prediction.
Proteome Science 2011 9(Suppl 1):S19.

Published: 14 October 2011
References
1. Lau KF, Dill KA: Lattice statistical mechanics model of the conformationand sequence space of proteins. Macromolecules 1989, 22:3986-3997.
2. Sali A, Kuriyan J: Challenges at the frontiers of structural biology. Trends
in Genetics 1999, 15:M20-M24.
3. Mann M, Smith C, Rabbath M, Edwards M, Will S, Backofen R: CPSP-webtools: a server for 3D lattice protein studies. Bioinformatics 2009,25:676-677.
4. Hart WE, Istrail S: Fast protein folding in the Hydrophobic-Hydrophilicmodel within three-eighths of optimal (extended abstract). Proceedings of
27th Annual ACM Symposium on Theory of Computation (STOC95) 1995,
157-168.
5. Decatur S, Batzoglou S: Protein folding in the Hydrophobic-Polar modelon the 3D triangular lattice. 6th Annual MIT Laboratory for Computer
Science Student Workshop on Computing Technologies 1996.
6. Mirsky AE, Pauling L: On the structure of native, denatured andcoagulated proteins. Proc. Natl. Acad. Sci. USA 1936, 22:439-447.
7. Orengo CA, Todd AE: From protein structure to function. Curr. Opin. Struct.
Biol 1999, 9:374-382.
8. Guoa YZ, Fenga EM, Wangb Y: Optimal HP configurations of proteins by
combining local search with elastic net algorithm. Journal of Biochemical
and Biophysical Methods 2007, 70:335-340.
9. Huang C, Yang X, He Z: Protein folding simulations of 2D HP model by
the genetic algorithm based on optimal secondary structures.
Computational Biology and Chemistry 2010, 34:137-142.
10. Shmygelska A, Hoos HH: An ant colony optimisation algorithm for the 2D
and 3D hydrophobic polar protein folding problem. BMC Bioinformatics
2005, 6:30.
11. Joel G, Martin M, Minghui J: RNA folding on the 3D triangular lattice. BMC
Bioinformatics 2009, 10:369.
12. Crescenzi P, Goldman D, Papadimitriou C, Piccolboni A, Yannakakis M: On
the complexity of protein folding. Journal of Computational Biology 1998,
5:423-465.
13. Unger R, Moult J: Genetic algorithms for protein folding simulations.
Journal of Molecular Biology 1993, 231:75-81.
14. Hoque MT, Chetty M, Dooley LS: A hybrid genetic algorithm for 2D FCChydrophobic–hydrophilic lattice model to predict protein folding.
Advances in Artificial Intelligence, Lecture Notes in Computer Science 2006,
4304:867-876.
15. Böckenhauer HJ, Ullah AD, Kapsokalivas L, Steinhöfel K: A Local Move Set
for Protein Folding in Triangular Lattice Models. Algorithms in
Bioinformatics, LNCS 2008, 5251:369-381.
16. Albrechta AA, Skaliotisb A, Steinhöfelb K: Stochastic protein folding
simulation in the three-dimensional HP-model. Computational Biology andChemistry 2008, 32:248-255.
17. Ullah AD, Kapsokalivas L, Mann M, Steinhöfel K: Protein Folding Simulation
by Two-Stage Optimization. Computational Intelligence and Intelligent
Systems, Communications in Computer and Information Science 2009,
51:138-145.
18. Zhao X: Advances on protein folding simulations based on the lattice HP
models with natural computing. Applied Soft Computing 2008,
8:1029-1040.
19. Lin CJ, Hsu YC: Reinforcement hybrid evolutionary learning for recurrent
wavelet-based neuro-fuzzy systems. IEEE Transactions on Fuzzy Systems
2007, 15:729-745.

Submit your next manuscript to BioMed Central
and take full advantage of:• Convenient online submission• Thorough peer review• No space constraints or color figure charges• Immediate publication on acceptance• Inclusion in PubMed, CAS, Scopus and Google Scholar• Research which is freely available for redistribution
Submit your manuscript at
www.biomedcentral.com/submit