Enlightened by the law of interactions among objects in the physical world, we propose a heuristic algorithm for solving the three-dimensional (3D) off-lattice protein folding problem. Based on a physical model, the p...Enlightened by the law of interactions among objects in the physical world, we propose a heuristic algorithm for solving the three-dimensional (3D) off-lattice protein folding problem. Based on a physical model, the problem is converted from a nonlinear constraint-satisfied problem to an unconstrained optimization problem which can be solved by the well-known gra- dient method. To improve the efficiency of our algorithm, a strategy was introduced to generate initial configuration. Computa- tional results showed that this algorithm could find states with lower energy than previously proposed ground states obtained by nPERM algorithm for all chains with length ranging from 13 to 55.展开更多
Using a triangular lattice model to study the designability of proteinfolding, we overcame the parity problem of previous cubic lattice model and enumerated all thesequences and compact structures on a simple two-dime...Using a triangular lattice model to study the designability of proteinfolding, we overcame the parity problem of previous cubic lattice model and enumerated all thesequences and compact structures on a simple two-dimensional triangular lattice model of size4+5+6+5+4. We used two types of amino acids, hydrophobic and polar, to make up the sequences, andachieved 2^(23)+2^(12) different sequences excluding the reverse symmetry sequences. The totalstring number of distinct compact structures was 219,093, excluding reflection symmetry in theself-avoiding path of length 24 triangular lattice model. Based on this model, we applied a fastsearch algorithm by constructing a cluster tree. The algorithm decreased the computation bycomputing the objective energy of non-leaf nodes. The parallel experiments proved that the fast treesearch algorithm yielded an exponential speed-up in the model of size 4+5+6+5+4. Designabilityanalysis was performed to understand the search result.展开更多
A branch and bound algorithm is proposed for the two-dimensional protein folding problem in the HP lattice model. In this algorithm, the benefit of each possible location of hydrophobic monomers is evaluated and only ...A branch and bound algorithm is proposed for the two-dimensional protein folding problem in the HP lattice model. In this algorithm, the benefit of each possible location of hydrophobic monomers is evaluated and only promising nodes are kept for further branching at each level. The proposed algorithm is compared with other well-known methods for 10 benchmark sequences with lengths ranging from 20 to 100 monomers. The results indicate that our method is a very efficient and promising tool for the protein folding problem.展开更多
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 ...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.展开更多
A heuristic algorithm is presented for a three-dimensional off-lattice AB model consisting of hydrophobic （A） and hydrophilic （B） residues in Fibonacci sequences. By incorporating extra energy contributions into t...A heuristic algorithm is presented for a three-dimensional off-lattice AB model consisting of hydrophobic （A） and hydrophilic （B） residues in Fibonacci sequences. By incorporating extra energy contributions into the original potential function, we convert the constrained optimization problem of AB model into an unconstrained optimization problem which can be solved by the gradient method. After the gradient minimization leads to the basins of the local energy minima, the heuristic off-trap strategy and subsequent neighborhood search mechanism axe then proposed to get out of local minima and search for the lower-energy configurations. Furthermore, in order to improve the efficiency of the proposed algorithm, we apply the improved version called the new PERM with importance sampling （nPERMis） of the chain-growth algorithm, pruned-enriched-Rosenbluth method （PERM）, to face-centered-cubic （FCC）-lattice to produce the initial configurations. The numerical results show that the proposed methods are very promising for finding the ground states of proteins. In several cases, we found the ground state energies are lower than the best values reported in the present literature.展开更多
PERM is the most efficient approach for solv- ing protein folding problem based on simple lattice model. In this article a personification explanation of PERM is pro- posed. A new version of PERM, population control a...PERM is the most efficient approach for solv- ing protein folding problem based on simple lattice model. In this article a personification explanation of PERM is pro- posed. A new version of PERM, population control algorithm with two main improvements is presented: one is that it is able to redefine the weight and its predicted value in PERM, and the other is that it is able to unify the calculation of weight when choosing possible branches. The improved PERM is more efficient than the previous version; specifi- cally it can find the known lowest energy states for the four well-known difficult instances and is generally several to hundreds times faster than PERM. It is noteworthy that with the improved PERM we found new lowest energy configura- tions of three of the four difficult problems missed in previ- ous papers.展开更多
In this paper, we study an off-lattice protein AB model with two species of monomers, hydrophobic and hydrophilic, and present a heuristic quasi-physical algorithm. First, by elaborately simulating the movement of the...In this paper, we study an off-lattice protein AB model with two species of monomers, hydrophobic and hydrophilic, and present a heuristic quasi-physical algorithm. First, by elaborately simulating the movement of the smooth solids in the physical world, we find low-energy conformations for a given monomer chain. A subsequent off-trap strategy is then proposed to trigger a jump for a stuck situation in order to get out of the local minima. The algorithm has been tested in the three-dimensional AB model for all sequences with lengths of 13-55 monomers. In several cases, we renew the putative ground state energy values. The numerical results show that the proposed methods are very promising for finding the ground states of proteins.展开更多
基金Project supported by the National Basic Research Program (973) of China (No. 2004CB318000) and the National Natural Science Foun-dation of China (No. 10471051)
文摘Enlightened by the law of interactions among objects in the physical world, we propose a heuristic algorithm for solving the three-dimensional (3D) off-lattice protein folding problem. Based on a physical model, the problem is converted from a nonlinear constraint-satisfied problem to an unconstrained optimization problem which can be solved by the well-known gra- dient method. To improve the efficiency of our algorithm, a strategy was introduced to generate initial configuration. Computa- tional results showed that this algorithm could find states with lower energy than previously proposed ground states obtained by nPERM algorithm for all chains with length ranging from 13 to 55.
文摘Using a triangular lattice model to study the designability of proteinfolding, we overcame the parity problem of previous cubic lattice model and enumerated all thesequences and compact structures on a simple two-dimensional triangular lattice model of size4+5+6+5+4. We used two types of amino acids, hydrophobic and polar, to make up the sequences, andachieved 2^(23)+2^(12) different sequences excluding the reverse symmetry sequences. The totalstring number of distinct compact structures was 219,093, excluding reflection symmetry in theself-avoiding path of length 24 triangular lattice model. Based on this model, we applied a fastsearch algorithm by constructing a cluster tree. The algorithm decreased the computation bycomputing the objective energy of non-leaf nodes. The parallel experiments proved that the fast treesearch algorithm yielded an exponential speed-up in the model of size 4+5+6+5+4. Designabilityanalysis was performed to understand the search result.
基金supported by the National Natural Science Foundation of China(No.10471051)the National Basic Research Program(973 Program)of China(No.2004CB318000)
文摘A branch and bound algorithm is proposed for the two-dimensional protein folding problem in the HP lattice model. In this algorithm, the benefit of each possible location of hydrophobic monomers is evaluated and only promising nodes are kept for further branching at each level. The proposed algorithm is compared with other well-known methods for 10 benchmark sequences with lengths ranging from 20 to 100 monomers. The results indicate that our method is a very efficient and promising tool for the protein folding problem.
基金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.
基金Project supported by the Foundation of Nanjing University of Information Science and Technologythe Excellent Youth Foundation of Education Office of Hunan Province,China (Grant No 07B009)
文摘A heuristic algorithm is presented for a three-dimensional off-lattice AB model consisting of hydrophobic （A） and hydrophilic （B） residues in Fibonacci sequences. By incorporating extra energy contributions into the original potential function, we convert the constrained optimization problem of AB model into an unconstrained optimization problem which can be solved by the gradient method. After the gradient minimization leads to the basins of the local energy minima, the heuristic off-trap strategy and subsequent neighborhood search mechanism axe then proposed to get out of local minima and search for the lower-energy configurations. Furthermore, in order to improve the efficiency of the proposed algorithm, we apply the improved version called the new PERM with importance sampling （nPERMis） of the chain-growth algorithm, pruned-enriched-Rosenbluth method （PERM）, to face-centered-cubic （FCC）-lattice to produce the initial configurations. The numerical results show that the proposed methods are very promising for finding the ground states of proteins. In several cases, we found the ground state energies are lower than the best values reported in the present literature.
文摘PERM is the most efficient approach for solv- ing protein folding problem based on simple lattice model. In this article a personification explanation of PERM is pro- posed. A new version of PERM, population control algorithm with two main improvements is presented: one is that it is able to redefine the weight and its predicted value in PERM, and the other is that it is able to unify the calculation of weight when choosing possible branches. The improved PERM is more efficient than the previous version; specifi- cally it can find the known lowest energy states for the four well-known difficult instances and is generally several to hundreds times faster than PERM. It is noteworthy that with the improved PERM we found new lowest energy configura- tions of three of the four difficult problems missed in previ- ous papers.
文摘In this paper, we study an off-lattice protein AB model with two species of monomers, hydrophobic and hydrophilic, and present a heuristic quasi-physical algorithm. First, by elaborately simulating the movement of the smooth solids in the physical world, we find low-energy conformations for a given monomer chain. A subsequent off-trap strategy is then proposed to trigger a jump for a stuck situation in order to get out of the local minima. The algorithm has been tested in the three-dimensional AB model for all sequences with lengths of 13-55 monomers. In several cases, we renew the putative ground state energy values. The numerical results show that the proposed methods are very promising for finding the ground states of proteins.
基金国家自然科学基金( the National Natural Science Foundation of China under Grant No.30170214)国家高技术研究发展计划( 863)( the National High-Tech Research and Development Plan of China under Grant No.2006AA10Z1E6) 。
