Algorithm for Protein Folding Problem in 3D Lattice HP Model

AUTHOR(S):

Metodi Traykov, Nicola Yanev, Radoslav Mavrevski, Borislav Yurukov

TITLE

Algorithm for Protein Folding Problem in 3D Lattice HP Model

ABSTRACT

The prediction of a protein’s tertiary structure from the amino acid sequence of a protein is known as the protein folding problem. The protein folding problem in 3D lattice Hydrophobic-Polar model is problem of finding the lowest energy conformation. This is the NP-complete problem. In this article we propose extension of the heuristic algorithm described by some of authors to solve the protein folding problem in 3D cubic lattice in HP model. For computational experiments we use 8 HP sequences that are known in the literature benchmarks for 3D lattice in HP model. We compare the obtained results with results obtained by algorithms for solving the problem in 3D lattice HP model as genetic algorithms, ant-colony optimization algorithm, and Monte Carlo algorithm.

KEYWORDS

Bioinformatics, Protein Folding Problem, 3D Cubic Lattice, HP Model, Heuristics, HP folding, 3D structure

REFERENCES

[1] K. Dill, Theory for the folding and stability of lobular proteins, Biochemistry-US, Vol. 24, 1985, pp. 1501-1509.

[2] K. Dill, K. Lau, A Lattice Statistical Mechanics Model of the Conformational Sequence Spaces of Proteins, Macromolecules, Vol. 22, 1989, pp. 3986-3997.

[3] C. Lin, M. Hsieh, An efficient hybrid Taguchi-genetic algorithm for protein folding simulation, Expert Systems with Applications, Vol. 36, 2009, pp. 12446-12453.

[4] J. Blazewick, K. Dill, P. Lukasiak, et al., A Tabu Search Strategy For Finding Low Energy Structures Of Proteins In Hp-Model, CMST, Vol. 10, 2004, pp. 7-19.

[5] S. Istrail, A. Hurd, R. Lippert, et al., Prediction of self-assembly of energetic tiles and dominoes: Experiments, mathematics, and software, Technical Report SAND2002, 2000, Sandia National Laboratories.

[6] S. Istrail, F. Lam, Combinatorial algorithms for protein folding in lattice models: A survey of mathematical results, Commun. Inf. Syst., Vol. 9, 2009, pp. 303-346.

[7] M. Chen, W. Huang, A branch and bound algorithm for the protein folding problem in the HP Lattice Model, Genomics Proteomics Bioinformatics, Vol. 3, 2005, pp. 225-230.

[8] L. Toma, S. Toma, Contact interactions method: A new algorithm for protein folding simulations, Protein Sci., Vol. 5, 1996, pp. 147-153.

[9] Y. Zhang, J. Skolnick, Tertiary structure predictions on a comprehensive benchmark of medium to large size proteins, Biophys J., Vol. 87, 2004, pp. 2647-2655.

[10] N. Krasnogor, D. Pelta, P. Lopez, et al., Genetic Algorithms for the Protein Folding Problem: A Critical View, Proc. Engineering of intelligent systems, 1998, pp. 353-360.

[11] F. Liang, W. Wong, Evolutionary Monte Carlo for Protein Folding Simulations, J. Chem. Phys., Vol. 115, 2001, pp. 444-451.

[12] A. Shmygelska, H. Hoos, An ant colony optimisation algorithm for the 2D and 3D hydrophobic polar protein folding problem, BMC Bioinformatics, Vol. 6, 2005, Article No.30.

[13] N. Yanev, M. Traykov, P. Milanov, B. Yurukov, Protein folding prediction in a cubic lattice in hydrophobic-polar model, Journal of Computational Biology, Vol. 24, 2017, pp. 412-421.

[14] N. Yanev, P. Milanov, I. Mirchev, Integer programming approaches to HP folding, Serdica J. Computing, Vol. 5, 2011, pp. 359-366.

[15] M. Traykov, S. Angelov, N. Yanev, A New Heuristic Algorithm for Protein Folding in the HP Model, J Comput. Biol., Vol. 23, 2016, pp. 662-668.

Cite this paper

Metodi Traykov, Nicola Yanev, Radoslav Mavrevski, Borislav Yurukov. (2018) Algorithm for Protein Folding Problem in 3D Lattice HP Model. International Journal of Biology and Biomedicine, 3, 16-21