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

作　　者：刘景发 黄文奇 

机构地区：[1]Computer and Software Institute,Nanjing University of Information Science and Technology [2]School of Computer Science and Technology,Huazhong University of Science and Technology

出　　处：《Journal of Computer Science & Technology》2007年第4期569-574,共6页计算机科学技术学报（英文版）

基　　金：This work was supported by the National Grand Fundamental Research 973 Program of China(Grant No.2004CB318000);the National Natural Science Foundation of China nnder Grant No.10471051.

摘　　要：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.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.

关 键 词：protein folding off-lattice model quasi-physical algorithm off-trap strategy NP-hard problem 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]