Open Access Open Access  Restricted Access Subscription or Fee Access

An Improved Ant Colony Algorithm Based on the Immune Strategy for the 2D HP Protein Structure Prediction Problem

Marghny H. Mohammed, Abdel-Rahman Hedar, Sara Salah


The prediction of a protein’s structure from its amino acid sequence is one of the most important problems in computational biology. In this work we present an improved version of Ant Colony Optimization (ACO) algorithm with diversified solutions based on the Immune Strategy (IS) called (ACIS). It is shown experimentally that the algorithm achieves on nearly all test sequences comparable results to other state of the art algorithms.


Ant Colony Optimization, Immune System, Genetic Algorithm, Protein Structure Prediction

Full Text:



C. B. Anfinsen, E. Haber, M. Sela, "The kinetics of formation of native ribonuclease during oxidation of the reduced polypeptide chain," Proc Natl Acad Sci USA 47:1309–1314(1961).

C. B. Anfinsen, "Principles that govern the folding of proteins chains," Science 181:223–230(1973).

R. Unger, J. Moult, " Finding the lowest free energy conformation of a protein is an NP-hard problem: proof and implications," Bulletin of Mathematical Biology 55:1183–1198(1993).

F. Liang, W. H. Wong, "Evolutionary Monte Carlo for protein folding simulations," J Chem Phys 115(7):3374–3380(2001).

F. L. Cust′odio, H. Dardenne, "Investigation of the three dimensional lattice HP protein folding model using a genetic algorithm," Genetics and Molecular Biology 27(4):611–615(2004).

N. Krasnogor, W. Hart and J. Smith," Protein structure prediction with evolutionary algorithms," Proceedings of the Genetic and Evolutionary Computation Conference 1596– 1601(1999).

A. Shmygelska, H. H. Hoos, "An ant colony optimisation algorithm for the 2D and 3D hydrophobic polar protein folding problem," BMC Bioinformatics 6:30 (2005).

V. Cutello, G. Nicosia, M. Pavone, and J. Timmis," An immune algorithm for protein structure prediction on lattice models,"IEEE Trans. on Evolutionary Computation 11(1):101 117(2007).

V. Cutello, G. Nicosia and M. Pavone, "An immune algorithm with hypermacromutations for the Dill’s 2D hydrophobic-hydrophilic model," CEC 2004 1: 1074 1080(2004).

M. Dorigo, T. St¨utzle ,"Ant Colony Optimization," Cambridge MA: MIT Press(2004).

M. Dorigo, M. Gambardella," Ant Colony System," A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Trans on. J Chem Phys 115(7):3374–3380.

M. Dorigo, V. Maniezzo, and A. Colorni," Ant system: optimization by a colony of cooperating agents," IEEE Trans on Systems Man and Cybernetics–Part B 26(1):29–41(1996).

D. W. Mount," Bioinformatics: sequence and genome analysis," Cold Spring Harbor Laboratory Press(2001).

S. S. Chen, "A localized protein-folding problem," International Journal of Intelligent Systems 16:449–457 (2001).

RCSB (Research Collaboratory for Structural Bioinformatics). Protein Data Bank

F. H. Stillinger, T. Head-Gordon, "Toy model for protein folding," Phys Rev E 48(2):1469–1477 (1993).

A. A. Tantar, N. Melab and E. G. Talbi, "A parallel hybrid genetic algorithm for protein structure prediction on the computational grid," Future Generation Computer Systems 23:398– 409(2007).

X. Hu, J. Zhang and Y. Li," Flexible protein folding by ant colony optimization," In Computational Intelligence in Biomedicine and Bioinformatics: Current Trends and Applications. Springer-Verlag , New York, pp. 317-336. (2008).

B. Berger and T. Leighton," Protein folding in the hydrophobic-hydrophilic model is NP complete," J. Comp. Biol., vol. 5, pp. 27–40(1998).

D. Bradley and A. M. Tyrrell, "Hardware fault tolerance: An immunological solution," in Proc. IEEE Int. Conf. Syst., Man, Cybern., Nashville, TN, pp. 107–112(2000).

T. Zhang, Y. Ding and K.-C. Chou," Prediction of protein subcellular location using hydrophobic patterns of amino acid sequence," Computational Biology and Chemistry, Vol. 30, No. 5, pp. 367- 371(2006).

Y. Zhang, L. Wu and S. Wang, "Artificial Immune System for Protein Folding Model," Journal of Convergence Information Technology, Volume 6, Number 1(2011).

R. Unger, J. Moult, "Genetic algorithms for protein folding simulations," J Mol Biol 231(1):75–81(1993).

F. Liang, W. H. Wong, "Evolutionary Monte Carlo for protein folding simulations". J Chem Phys 115(7):3374–3380(2001).


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.