• Articles • Previous Articles     Next Articles

Quasi-Physical Algorithm of an Off-Lattice Model for Protein Folding Problem

Jing-Fa Liu1,2 and Wen-Qi Huang2   

  1. 1Computer and Software Institute, Nanjing University of Information Science and Technology, Nanjing 210044, China 2School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China
  • Received:2005-11-01 Revised:2006-02-27 Online:2007-07-10 Published:2007-07-10

Protein folding problem is one of the most prominent problems of bioinformatics. In this paper, we study a three-dimensional off-lattice protein AB model with two species of monomers, hydrophobic and hydrophilic, and present a heuristic quasi-physical algorithm. By elaborately simulating the movement of the smooth elastic balls in the physical world, the algorithm finds low-energy configurations for a given monomer chain. A subsequent ``off-trap'' strategy is proposed to trigger a jump for a stuck situation in order to get out of local minima. The methods have been tested in the off-lattice AB model. The computational results show promising performance. For all sequences with 13 to 55 monomers, the algorithm finds states with lower energy than previously proposed putative ground states. Furthermore, for the sequences with 21, 34 and 55 monomers, new putative ground states are found, which are different from those given in present literature.

Key words: software DSM; system overhead; scalability; communication; speedup;

[1] Irb\"ack A, Peterson C, Potthast F \it et al. \rm Local interactions and protein folding: A three-dimensional off-lattice approach. -\it J. Chem. Phys.}, 1997, 107(1): 273$\sim$282.

[2] Dill K A. Theory for the folding and stability of globular proteins. -\it Biochemistry}, 1985, 24(6): 1501$\sim$1509.

[3] Lau K F, Dill K A. A lattice statistical mechanics model of the conformational and sequence spaces of proteins. -\it Macromolecules}, 1989, 22(10): 3986$\sim$3997. \end-multicols} \begin-multicols}-2} \footnotesize

[4] Camacho C J, Thirumalai D. Kinetics and thermodynamics of folding in model proteins. -\it Proc. Natl. Acad. Sci. USA}, 1993, 90(13): 6369$\sim$6372.

[5] Shakhnovich E I. Proteins with selected sequences fold into unique native configuration. -\it Phys. Rev. Lett.}, 1994, 72(24): 3907$\sim$3911.

[6] Dill K A, Bromberg S, Yue K \it et al. \rm Principles of protein folding: A perspective from simple exact models. -\it Protein Sci.}, 1995, 4(4): 561$\sim$602.

[7] Honeycutt J D, Thirumalai D. The nature of folded states of globular proteins. -\it Biopolymers}, 1992, 32(6): 695$\sim$709.

[8] Fukugita M, Lancaster D, Mitchard M G. Kinematics and thermodynamics of a folding heteropolymer. -\it Proc. Natl. Acad. Sci. USA}, 1993, 90(13): 6365$\sim$6368.

[9] Zhang J L, Liu J S. A new sequential importance sampling method and its application to the two-dimensional hydrophobic-hydrophilic model. -\it J. Chem. Phys.}, 2002, 117(7): 3492$\sim$3498.

[10] Chikenji G, Kikuchi M, Iba Y. Multi-self-overlap ensemble for protein folding: Ground state search and thermodynamics. -\it Phys. Rev. Lett.}, 1999, 83(9): 1886$\sim$1889.

[11] Hsu H P, Mehra V, Nadler W \it et al. \rm Growth algorithms for lattice heteropolymers at low temperatures. -\it J. Chem. Phys.}, 2003, 118(1): 444$\sim$452.

[12] Huang W Q, L\"u Z P. Personification algorithm for protein folding problem: Improvements in PERM. -\it Chinese Science Bulletin}, 2004, 49(17): 2092$\sim$2096.

[13] Huang W Q, Kang Y. A heuristic quasi-physical strategy for solving disks packing problem. -\it Simulation Modeling Practice and Theory}, 2002, 10(4): 195$\sim$207.

[14] Wang H Q, Huang W Q, Zhang Q \it et al. \rm An improved algorithm for the packing of unequal circles within a larger containing circle. -\it European Journal of Operational Research}, 2002, 141(2): 440$\sim$453.

[15] Huang W Q, Jin R C. Quasiphysical and quasisociological algorithm Solar for solving SAT problem. -\it Science in China} (-\it Ser. E}), 1999, 42(5): 485$\sim$493.

[16] Stillinger F H, Head-Gordon T, Hirshfeld C L. Toy model for protein folding. -\it Phys. Rev. E.}, 1993, 48(2): 1469$\sim$1477.

[17] Stillinger F H, Head-Gordon T. Collective aspects of protein folding illustrated by a toy model. -\it Phys. Rev. E.}, 1995, 52(3): 2872$\sim$2877.

[18] Liang F M. Annealing contour Monte Carlo algorithm for structure optimization in an off-lattice protein model. -\it J. Chem. Phys.}, 2004, 120(14): 6756$\sim$6763.

[19] Gorse D. Application of a chaperone-based refolding method to twoand three-dimensional off-lattice protein models. -\it Biopolymers}, 2002, 64(3): 146$\sim$160.

[20] Gorse D. Global minimization of an off-lattice potential energy function using a chaperone-based refolding method. -\it Biopolymers}, 2001, 59(6): 411$\sim$426.

[21] Irb\"ack A, Peterson C, Potthast F. Identification of amino acid sequences with good folding properties in an off-lattice model. -\it Phys. Rev. E.}, 1997, 55(1): 860$\sim$867.

[22] Irb\"ack A, Potthast F. Studies of an off-lattice model for protein folding: Sequence dependence and improved sampling at finite temperature. -\it J. Chem. Phys.}, 1995, 103(23): 10298$\sim$10305.

[23] Hsu H P, Mehra V, Grassberger P. Structure optimization in an off-lattice protein model. -\it Phys. Rev. E.}, 2003, 68(3): 037703.
[1] Yu-Wei Wu, Qing-Gang Wang, Long Zheng, Xiao-Fei Liao, Hai Jin, Wen-Bin Jiang, Ran Zheng, Kan Hu. FDGLib: A Communication Library for Efficient Large-Scale Graph Processing in FPGA-Accelerated Data Centers [J]. Journal of Computer Science and Technology, 2021, 36(5): 1051-1070.
[2] Zhi-Hao Liu, Han-Wu Chen. Universal and General Quantum Simultaneous Secret Distribution with Dense Coding by Using One-Dimensional High-Level Cluster States [J]. Journal of Computer Science and Technology, 2021, 36(1): 221-230.
[3] Zhi-Yuan Dong, Chu-Zhe Tang, Jia-Chen Wang, Zhao-Guo Wang, Hai-Bo Chen, Bin-Yu Zang. Optimistic Transaction Processing in Deterministic Database [J]. Journal of Computer Science and Technology, 2020, 35(2): 382-394.
[4] Hong-Mei Wei, Jian Gao, Peng Qing, Kang Yu, Yan-Fei Fang, Ming-Lu Li. MPI-RCDD: A Framework for MPI Runtime Communication Deadlock Detection [J]. Journal of Computer Science and Technology, 2020, 35(2): 395-411.
[5] Yang Hong, Yang Zheng, Fan Yang, Bin-Yu Zang, Hai-Bing Guan, Hai-Bo Chen. Scaling out NUMA-Aware Applications with RDMA-Based Distributed Shared Memory [J]. Journal of Computer Science and Technology, 2019, 34(1): 94-112.
[6] Xiao-Hu Yan, Fa-Zhi He, Yi-Lin Chen. A Novel Hardware/Software Partitioning Method Based on Position Disturbed Particle Swarm Optimization with Invasive Weed Optimization [J]. , 2017, 32(2): 340-355.
[7] Li-Li Xu, Hui-Min Lin. Complete Proof Systems for Amortised Probabilistic Bisimulations [J]. , 2016, 31(2): 300-316.
[8] Zeinab Hmedeh, Harry Kourdounakis, Vassilis Christophides, Cédric du Mouza, et al. Content-Based Publish/Subscribe System for Web Syndication [J]. , 2016, 31(2): 359-380.
[9] Erika Rosas, Nicolás Hidalgo, Veronica Gil-Costa, Carolina Bonacic, et al. Survey on Simulation for Mobile Ad-Hoc Communication for Disaster Scenarios [J]. , 2016, 31(2): 326-349.
[10] Fang Zheng, Hong-Liang Li, Hui Lv, Feng Guo, Xiao-Hong Xu, Xiang-Hui Xie. Cooperative Computing Techniques for a Deeply Fused and Heterogeneous Many-Core Processor Architecture [J]. , 2015, 30(1): 145-162.
[11] Lengdong Wu, Liyan Yuan, Jiahuai You. Survey of Large-Scale Data Management Systems for Big Data Applications [J]. , 2015, 30(1): 163-183.
[12] Chen-Da Hou, Dong Li, Jie-Fan Qiu, Hai-Long Shi, Li Cui. SeaHttp:A Resource-Oriented Protocol to Extend REST Style for Web of Things [J]. , 2014, 29(2): 205-215.
[13] Kun Xie, Jian-Nong Cao, and Ji-Gang Wen. Optimal Relay Assignment and Power Allocation for Cooperative Communications [J]. , 2013, 28(2): 343-356.
[14] Joo Hyuk Jeon, Jihwan Song, Jeong Eun Kwon, Yoon Joon Lee, Man Ho Park and Myoung Ho Kim. An Efficient and Spam-Robust Proximity Measure Between Communication Entities [J]. , 2013, 28(2): 394-400.
[15] Yue-Hua Wang (王跃华), Student Member, IEEE, Zhong Zhou (周忠), Member, CCF, ACM, IEEE, Ling Liu, Senior Member, IEEE, and Wei Wu (吴威), Member, CCF. Fault Tolerance and Recovery for Group Communication Services in Distributed Networks [J]. , 2012, (2): 298-312.
Full text



[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
[10] Li Minghui;. CAD System of Microprogrammed Digital Systems[J]. , 1987, 2(3): 226 -235 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved