Approximation Algorithms for Three Dimensional Protein Folding

• Autorzy: Shaw D. L. , Karmaker S. , Islam A. S. M. S , Rahman M. S.

Identyfikatory

DOI

10.3233/FI-2018-1750

• Języki publikacji: EN

Abstrakty

EN

Predicting the secondary structure of a protein using a lattice model is one of the most studied computational problems in bioinformatics. Here the secondary structure or three dimensional structure of a protein is predicted from its amino acid sequence. The secondary structure refers to the local sub-structures of a protein. Simplified energy models have been proposed in the literature on the basis of interaction of amino acid residues in proteins. We focus on a well researched model known as the Hydrophobic-Polar (HP) energy model. In this paper, we propose the hexagonal prism lattice with diagonals that can overcome the problems of other lattice structures, e.g., parity problem. We give two approximation algorithms for protein folding on this lattice using HP model. Our first algorithm leads us to a similar structure of helix structure that is commonly found in a protein structure. This motivates us to propose the next algorithm with a better approximation ratio. Finally, we analyze the algorithms on the basis of intensity of the chemical forces along the different types of edges of hexagonal prism lattice with diagonals.

Słowa kluczowe

EN

algorithms; protein folding; lattice theory; bioinformatics; hydrophobic compounds

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2018
• Tom: Vol. 163, nr 4
• Strony: 375--393
• Opis fizyczny: Bibliogr. 26 poz., rys., tab.

Twórcy

autor

Shaw D. L.

• Department of CSE, University of California, Riverside, CA 92521, United States

autor

Karmaker S.

• Department of CSE, BUET, Dhaka-1205, Bangladesh

autor

Islam A. S. M. S

• Department of Computational Engineering and Science, McMaster University, Hamilton, Ontario, Canada

autor

Rahman M. S.

• AℓEDA Group, Department of CSE, BUET, ECE Building, West Palasi, Dhaka-1205, Bangladesh

Bibliografia

• [1] Laganowsky A, Reading E, Allison TM, Ulmschneider MB, Degiacomi MT, Baldwin AJ, Robinson CV. Membrane proteins bind lipids selectively to modulate their structure and function. Nature, 2014.510(7503):172-175. doi:10.1038/nature13419.
• [2] Aebersold R, Mann M. Mass-spectrometric exploration of proteome structure and function. Nature, 2016.537(7620):347-355. doi:10.1038/nature19949.
• [3] Nanci A. Ten Cate’s Oral Histology-E-Book: Development, Structure, and Function. Elsevier Health Sciences, 2017. ISBN:9780323485180, 9780323485203.
• [4] Lukoyanova N, Kondos SC, Farabella I, Law RH, Reboul CF, Caradoc-Davies TT, Spicer BA, Kleifeld O, Traore DA, Ekkel SM, et al. Conformational changes during pore formation by the perforin-related protein pleurotolysin. PLoS biology, 2015.13(2):e1002049. doi:10.1371/journal.pbio.1002049.
• [5] Dill KA. Theory for the folding and stability of globular proteins. Biochemistry, 1985.24(6):1501-1509. doi:10.1021/bi00327a032.
• [6] Crescenzi P, Goldman D, Papadimitriou C, Piccolboni A, Yannakakis M. On the complexity of protein folding. Journal of computational biology, 1998.5(3):423-465. doi:10.1089/cmb.1998.5.423.
• [7] Berger B, Leighton T. Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete. Journal of Computational Biology, 1998.5(1):27-40. doi:10.1089/cmb.1998.5.27.
• [8] Hart WE, Istrail SC. Fast protein folding in the hydrophobic-hydrophilic model within three-eighths of optimal. Journal of computational biology, 1996.3(1):53-96. doi:10.1089/cmb.1996.3.53.
• [9] Newman A, Ruhl M. Combinatorial problems on strings with applications to protein folding. In: Latin American Symposium on Theoretical Informatics. vol 2976. Springer, 2004 pp. 369-378. doi:10.1007/978-3-540-24698-5_41.
• [10] Hart WE, Istrail S. Lattice and off-lattice side chain models of protein folding: linear time structure prediction better than 86% of optimal. Journal of Computational Biology, 1997.4(3):241-259. doi:10.1089/cmb.1997.4.241.
• [11] Heun V. Approximate protein folding in the HP side chain model on extended cubic lattices. Discrete Applied Mathematics, 2003.127(1):163-177. URL https://doi.org/10.1016/S0166-218X(02)00382-7.
• [12] Böckenhauer HJ, Ullah AZMD, Kapsokalivas L, Steinhöfel K. A local move set for protein folding in triangular lattice models. In: International Workshop on Algorithms in Bioinformatics. vol 5251. Springer, 2008 pp. 369-381. doi:10.1007/978-3-540-87361-7_31.
• [13] Unger R, Moult J. Genetic algorithms for protein folding simulations. Journal of molecular biology, 1993.231(1):75-81.
• [14] Hoque MT, Chetty M, Dooley LS. A hybrid genetic algorithm for 2D FCC hydrophobic-hydrophilic lattice model to predict protein folding. In: Australasian Joint Conference on Artificial Intelligence. vol 4304. Springer, 2006 pp. 867-876. doi:10.1007/11941439_91.
• [15] Hoque MT, Chetty M, Sattar A. Protein folding prediction in 3D FCC HP lattice model using genetic algorithm. In: Evolutionary Computation, 2007. CEC 2007. IEEE Congress on. IEEE, 2007 pp. 4138-4145. doi:10.1109/CEC.2007.4425011.
• [16] Ullah A, Ahmed N, Pappu SD, Shatabda S, Ullah AD, Rahman MS. Efficient conformational space exploration in ab initio protein folding simulation. Royal Society open science, 2015.2(8):150238. doi:10.1098/rsos.150238.
• [17] Mauri G, Pavesi G, Piccolboni A. Approximation Algorithms for Protein Folding Prediction. In: SODA. Citeseer, 1999 pp. 945-946.
• [18] Newman A. A new algorithm for protein folding in the HP model. In: Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2002 pp. 876-884. ISBN:0-89871-513-X.
• [19] Agarwala R, Batzoglou S, Dančik V, Decatur SE, Hannenhalli S, Farach M, Muthukrishnan S, Skiena S. Local rules for protein folding on a triangular lattice and generalized hydrophobicity in the HP model. Journal of Computational Biology, 1997.4(3):275-296. doi:10.1089/cmb.1997.4.275.
• [20] Böckenhauer HJ, Bongartz D. Protein folding in the HP model on grid lattices with diagonals. Discrete Applied Mathematics, 2007.155(2):230-256. URL https://doi.org/10.1016/j.dam.2006.04.031.
• [21] Jiang M, Zhu B. Protein folding on the hexagonal lattice in the HP model. Journal of bioinformatics and computational biology, 2005.3(01):19-34. URL https://doi.org/10.1142/S0219720005000850.
• [22] Shaw DL, Islam AS, Rahman MS, Hasan M. Protein folding in HP model on hexagonal lattices with diagonals. In: BMC bioinformatics, volume 15. BioMed Central, 2014 p. S7. doi:10.1186/1471-2105-15-S2-S7.
• [23] Shaw DL, Islam ASMS, Karmaker S, Rahman MS. Approximation Algorithms for Three Dimensional Protein Folding. In: Kaykobad M, Petreschi R (eds.), WALCOM: Algorithms and Computation - 10th International Workshop, WALCOM 2016, Kathmandu, Nepal, March 29-31, 2016, Proceedings, volume 9627 of Lecture Notes in Computer Science. Springer. ISBN 978-3-319-30138-9, 2016 pp. 274-285. doi:10.1007/978-3-319-30139-6_22.
• [24] Islam ASMS, Rahman MS. On the protein folding problem in 2D-triangular lattices. Algorithms for Molecular Biology, 2013.8(1):30. doi:10.1186/1748-7188-8-30.
• [25] Islam AS, Rahman MS. Protein folding in 2d-triangular lattice revisited. In: International Workshop on Combinatorial Algorithms. vol 8288. Springer, 2013 pp. 244-257. doi:10.1007/978-3-642-45278-9_21.
• [26] Kessler I, Livingston M. The expected number of parts in a partition of n. Monatshefte für Mathematik, 1976.81(3):203-212. doi:10.1007/BF01303193.