蛋白质结构预测的现实求解方法
|
摘要
蛋白质结构预测问题是计算生物学领域的核心问题之一,对其求解是后基因时代蛋白质工程的一项重要任务。已经证明,即使按最简化的数学模型,所导出的问题仍然是NP难度的。因此,蛋白质结构预测问题的研究在当今国际学术界是一项具有挑战性的重大课题。
求解NP难度问题的方法主要有三种—–完整算法、近似算法和启发式算法。完整算法虽然能保证给出最优解,但由于人们普遍相信P= NP,指数级的计算复杂度导致其在实际应用中很难求解较大规模的问题实例。近似算法能保证在最坏情况下所得解的精度与最优解之间的误差在一定的范围内,但其实际计算效率往往不能令人满意。
另一种方法是启发式优化算法。启发式算法的主要思想来源于生物世界和社会现象,它往往可以在算法速度和精度之间达到一种很好的平衡,有可能在较短时间内求解大规模的问题实例,并达到令人满意的精度。拟物拟人算法是一种借助物理知识和人类社会经验来求解NP难度问题的启发式方法。对于蛋白质结构预测问题,当前的研究重点是设计求解该问题的高效启发式优化算法。
研究了蛋白质结构预测问题的两个简化模型—–HP格点模型和AB非格点模型。HP格点模型中,PERM算法不够简洁,不便于理解。AB非格点模型中,没有非常贴近问题本质的高效求解算法。对于这两个模型,文献中算法的计算效率不够高。对于HP格点模型,PERM(Pruned-Enrichment Rosenbluth Method)算法是当今国际文献中最先进的求解算法。在介绍PERM算法的基础上,对其给出了一种拟人解释—–人口控制策略,使该算法变得好想,易于理解,对算法中的权重及预测值进行了改进,并对选择动作时不同情况下的权重计算公式进行了统一。综合这些策略得到了改进的PERM算法。在此基础上提出了进一步的拟人改进策略。根据拟人思想对权重预测公式进行了重新定义,拟人改进后的PERM算法在链生长过程中不仅考虑氨基酸的类型(H或P),同时考虑氨基酸在整个链中的位置。
拟人改进的PERM算法的计算结果可概括为以下三点:第一,算法的计算速度要优于目前国际文献中最先进的求解算法—–nPERMis(new PERM importancesampling),计算速度是nPERMis的几倍到几十倍。第二,对一个链长为103的标准问题实例,拟人改进的PERM算法得到的最低能量为-55,该最低能量要优于nPERMis算法所得的最低能量-54。第三,对一个链长为46的标准问题实例,拟人改进的PERM算法首次得到了最低能量-35,该最低能量要优于文献中所报道的最低能量-34。
对于AB非格点模型,找到了贴近问题本质的物理模型—–弹簧模型。在此基础上通过将原始约束优化问题转化为无约束优化问题,提出了求解基于AB非格点模型的蛋白质结构预测问题的拟物算法。拟物算法的思想基于所提出的物理模型。
拟物算法及其计算结果可概括为以下三点:第一,算法提出的拟物思想很好地贴近了问题的本质。第二,以HP格点模型为基础生成初始解,算法所得解的精度要优于一种以PERM算法生成初始解的共轭梯度法所得解的精度。第三,以ELP(EnergyLandscape Paving)算法为基础生成初始解,对于绝大多数文献中的标准算例,拟物算法所得解的精度要优于国际文献中最先进的几个求解算法所得解的精度。
以上研究成果表明:拟物拟人策略是求解蛋白质结构预测问题的一种有效途径。进一步工作将研究基于更加真实的数学模型的蛋白质结构预测问题的高效启发式求解算法,以期在不久的将来将其应用于蛋白质工程的实践中去。同时,沿着拟物拟人的途径,有望为其它NP难度问题设计出高效率的求解算法。
Protein structure prediction is one of the central problems in the field of computationalbiology and one of the most demanding tasks of protein engineering in post-genome era.Meanwhile, the protein structure prediction problem remains to be NP-Hard even for itsmost simplified model. Therefore, it is a challenging task to study the problem of proteinstructure prediction.
For NP-Hard problems, we are forced to go on one of three ways. One is accurate algo-rithms that are employed to produce an optimal solution in an enumerative way. However,under the widely believed conjecture that P=NP, the exponential complexity of accuratealgorithms have limited themselves only to theoretical analysis or small size applications.As an alternative to solving NP-Hard problems to optimality, a stream of research has con-centrated on polynomial-time approximate algorithms with performance guarantee, i.e., anupper bound on the ratio between the approximate solution quality and the optimal one.The third way is to design practically efficient heuristic or meta-heuristic algorithmsfor solving NP-Hard problems. Heuristic algorithms seek for high quality solutions at areasonable computational time, and they can also be considered as intelligent techniquesthat are based upon human intuition, which often comes out as a result of analogies withphysical world, human experience or biological phenomena. Quasi-physical and quasi-human algorithm is one of the most effective methods for solving NP-Hard problems, whichis inspired by the wisdom from physical phenomenon and human experience. For proteinstructure prediction problem, the main focus of current research is to design highly efficientheuristic and meta-heuristic optimization algorithms.
Two of the simplified models for protein structure prediction, called HP lattice modeland AB off-lattice model, respectively, are studied. For HP lattice model, PERM algorithmis not succinct and can not be naturally explained, while for AB off-lattice model, no appro-priate heuristic algorithms have been reported. Besides, for both models, the computational performance of the previously proposed algorithms in literature still needs to be improved.
For HP lattice model, PERM (Pruned-Enrichment Rosenbluth Method) is recognizedto be the most efficient algorithm in literature for solving the protein structure predictionproblem based on this model. A personification explanation of PERM is proposed basedupon introducing PERM, which makes PERM algorithm naturally explained. A new versionof PERM, population control algorithm, with two main improvements is presented: one isthat it redefines the weight and the predicted value in PERM, and the other is that it is ableto unify the calculation of weight when choosing possible branches. Further personificationimprovement strategy is proposed, that is, predicted value of weight is redefined using thepersonification ideas. The further improved PERM algorithm not only considers the typesof amino acids (H or P), but also takes into account the position of the current amino acid inthe protein chain during the chain growth procedure.
The merits of the two improved PERM algorithms can be generalized as the followingthree points: Firstly, the improved PERM is more efficient than the previous version nPER-Mis (new PERM importance sampling) and is generally several to hundreds times fasterthan nPERMis. Secondly, for a standard benchmark instance with length equal to 103, itcan find lower energy (-55) than that nPERMis can find (-54). Finally, for a standard bench-mark instance with length equal to 46, it can find lower energy (-35) than the previously bestresult (-34) in literature.
For AB off-lattice model, an appropriate physical model—–spring model—–is pro-posed to simulate the original problem, based on which the original constraint optimizationproblem can be converted into an unconstraint one. Then a corresponding quasi-physical al-gorithm is provided to solve the protein structure prediction problem based on AB off-latticemodel, whose main ideas are based on the proposed physical model.
The merits of the proposed quasi-physical algorithm and its computational results canbe concluded as the following three points: First of all, the proposed quasi-physical ideais perfectly appropriate for the original problem. Secondly, based on the initial solutionsgenerated on SC-HP lattice model, the quasi-physical algorithm can produce higher qualitysolutions than PERM+ method which utilizes PERM to generate initial solutions and sub- sequently a conjugate gradient method is employed to improve them. Finally, based on theinitial solutions generated by ELP (Energy Landscape Paving) algorithm, the quasi-physicalalgorithm is superior to a number of famous algorithms in literature for most of the standardbenchmark instances.
Above results indicate that quasi-physical and quasi-human strategy is one of the mostefficient and effective approaches for solving protein structure prediction problem. Furtherresearch work will be focused on the high-efficient heuristic algorithms for more realisticprotein structure prediction models, so as to apply them to the practical protein engineeringin the near future. Meanwhile, following the path of quasi-physical quasi-human strategies,it is promising to design high-efficient heuristic algorithms for solving other NP-Hardproblems.
求解NP难度问题的方法主要有三种—–完整算法、近似算法和启发式算法。完整算法虽然能保证给出最优解,但由于人们普遍相信P= NP,指数级的计算复杂度导致其在实际应用中很难求解较大规模的问题实例。近似算法能保证在最坏情况下所得解的精度与最优解之间的误差在一定的范围内,但其实际计算效率往往不能令人满意。
另一种方法是启发式优化算法。启发式算法的主要思想来源于生物世界和社会现象,它往往可以在算法速度和精度之间达到一种很好的平衡,有可能在较短时间内求解大规模的问题实例,并达到令人满意的精度。拟物拟人算法是一种借助物理知识和人类社会经验来求解NP难度问题的启发式方法。对于蛋白质结构预测问题,当前的研究重点是设计求解该问题的高效启发式优化算法。
研究了蛋白质结构预测问题的两个简化模型—–HP格点模型和AB非格点模型。HP格点模型中,PERM算法不够简洁,不便于理解。AB非格点模型中,没有非常贴近问题本质的高效求解算法。对于这两个模型,文献中算法的计算效率不够高。对于HP格点模型,PERM(Pruned-Enrichment Rosenbluth Method)算法是当今国际文献中最先进的求解算法。在介绍PERM算法的基础上,对其给出了一种拟人解释—–人口控制策略,使该算法变得好想,易于理解,对算法中的权重及预测值进行了改进,并对选择动作时不同情况下的权重计算公式进行了统一。综合这些策略得到了改进的PERM算法。在此基础上提出了进一步的拟人改进策略。根据拟人思想对权重预测公式进行了重新定义,拟人改进后的PERM算法在链生长过程中不仅考虑氨基酸的类型(H或P),同时考虑氨基酸在整个链中的位置。
拟人改进的PERM算法的计算结果可概括为以下三点:第一,算法的计算速度要优于目前国际文献中最先进的求解算法—–nPERMis(new PERM importancesampling),计算速度是nPERMis的几倍到几十倍。第二,对一个链长为103的标准问题实例,拟人改进的PERM算法得到的最低能量为-55,该最低能量要优于nPERMis算法所得的最低能量-54。第三,对一个链长为46的标准问题实例,拟人改进的PERM算法首次得到了最低能量-35,该最低能量要优于文献中所报道的最低能量-34。
对于AB非格点模型,找到了贴近问题本质的物理模型—–弹簧模型。在此基础上通过将原始约束优化问题转化为无约束优化问题,提出了求解基于AB非格点模型的蛋白质结构预测问题的拟物算法。拟物算法的思想基于所提出的物理模型。
拟物算法及其计算结果可概括为以下三点:第一,算法提出的拟物思想很好地贴近了问题的本质。第二,以HP格点模型为基础生成初始解,算法所得解的精度要优于一种以PERM算法生成初始解的共轭梯度法所得解的精度。第三,以ELP(EnergyLandscape Paving)算法为基础生成初始解,对于绝大多数文献中的标准算例,拟物算法所得解的精度要优于国际文献中最先进的几个求解算法所得解的精度。
以上研究成果表明:拟物拟人策略是求解蛋白质结构预测问题的一种有效途径。进一步工作将研究基于更加真实的数学模型的蛋白质结构预测问题的高效启发式求解算法,以期在不久的将来将其应用于蛋白质工程的实践中去。同时,沿着拟物拟人的途径,有望为其它NP难度问题设计出高效率的求解算法。
Protein structure prediction is one of the central problems in the field of computationalbiology and one of the most demanding tasks of protein engineering in post-genome era.Meanwhile, the protein structure prediction problem remains to be NP-Hard even for itsmost simplified model. Therefore, it is a challenging task to study the problem of proteinstructure prediction.
For NP-Hard problems, we are forced to go on one of three ways. One is accurate algo-rithms that are employed to produce an optimal solution in an enumerative way. However,under the widely believed conjecture that P=NP, the exponential complexity of accuratealgorithms have limited themselves only to theoretical analysis or small size applications.As an alternative to solving NP-Hard problems to optimality, a stream of research has con-centrated on polynomial-time approximate algorithms with performance guarantee, i.e., anupper bound on the ratio between the approximate solution quality and the optimal one.The third way is to design practically efficient heuristic or meta-heuristic algorithmsfor solving NP-Hard problems. Heuristic algorithms seek for high quality solutions at areasonable computational time, and they can also be considered as intelligent techniquesthat are based upon human intuition, which often comes out as a result of analogies withphysical world, human experience or biological phenomena. Quasi-physical and quasi-human algorithm is one of the most effective methods for solving NP-Hard problems, whichis inspired by the wisdom from physical phenomenon and human experience. For proteinstructure prediction problem, the main focus of current research is to design highly efficientheuristic and meta-heuristic optimization algorithms.
Two of the simplified models for protein structure prediction, called HP lattice modeland AB off-lattice model, respectively, are studied. For HP lattice model, PERM algorithmis not succinct and can not be naturally explained, while for AB off-lattice model, no appro-priate heuristic algorithms have been reported. Besides, for both models, the computational performance of the previously proposed algorithms in literature still needs to be improved.
For HP lattice model, PERM (Pruned-Enrichment Rosenbluth Method) is recognizedto be the most efficient algorithm in literature for solving the protein structure predictionproblem based on this model. A personification explanation of PERM is proposed basedupon introducing PERM, which makes PERM algorithm naturally explained. A new versionof PERM, population control algorithm, with two main improvements is presented: one isthat it redefines the weight and the predicted value in PERM, and the other is that it is ableto unify the calculation of weight when choosing possible branches. Further personificationimprovement strategy is proposed, that is, predicted value of weight is redefined using thepersonification ideas. The further improved PERM algorithm not only considers the typesof amino acids (H or P), but also takes into account the position of the current amino acid inthe protein chain during the chain growth procedure.
The merits of the two improved PERM algorithms can be generalized as the followingthree points: Firstly, the improved PERM is more efficient than the previous version nPER-Mis (new PERM importance sampling) and is generally several to hundreds times fasterthan nPERMis. Secondly, for a standard benchmark instance with length equal to 103, itcan find lower energy (-55) than that nPERMis can find (-54). Finally, for a standard bench-mark instance with length equal to 46, it can find lower energy (-35) than the previously bestresult (-34) in literature.
For AB off-lattice model, an appropriate physical model—–spring model—–is pro-posed to simulate the original problem, based on which the original constraint optimizationproblem can be converted into an unconstraint one. Then a corresponding quasi-physical al-gorithm is provided to solve the protein structure prediction problem based on AB off-latticemodel, whose main ideas are based on the proposed physical model.
The merits of the proposed quasi-physical algorithm and its computational results canbe concluded as the following three points: First of all, the proposed quasi-physical ideais perfectly appropriate for the original problem. Secondly, based on the initial solutionsgenerated on SC-HP lattice model, the quasi-physical algorithm can produce higher qualitysolutions than PERM+ method which utilizes PERM to generate initial solutions and sub- sequently a conjugate gradient method is employed to improve them. Finally, based on theinitial solutions generated by ELP (Energy Landscape Paving) algorithm, the quasi-physicalalgorithm is superior to a number of famous algorithms in literature for most of the standardbenchmark instances.
Above results indicate that quasi-physical and quasi-human strategy is one of the mostefficient and effective approaches for solving protein structure prediction problem. Furtherresearch work will be focused on the high-efficient heuristic algorithms for more realisticprotein structure prediction models, so as to apply them to the practical protein engineeringin the near future. Meanwhile, following the path of quasi-physical quasi-human strategies,it is promising to design high-efficient heuristic algorithms for solving other NP-Hardproblems.
引文
[1] Anfinsen C B. Principles that govern the folding of protein chains. Science, 1973,181(96):223～230
[2] Yue K, Dill K A. Forces of tertiary structural organization in globular proteins. Proceedings of theNational Academy of Sciences USA, 1995, 92(11):146～150
[3] Dill K A. Theory for the folding and stability of globular proteins. Biochemistry, 1985,24(6):1501～1509
[4] Dill K A, Bromberg S, Yue K. Principles of protein folding: A perspective from simple exactmodels. Protein Science, 1995, 4(4):561～602
[5] Shih C T, Su Z Y, Gwan J F. Mean-Field HP model, designability and Alpha-Helices in proteinstructures. Physical Review Letters, 2000, 84(2):386～389
[6] Unger R, Moult J. Finding the lowest free energy conformation of a protein is an NP-hard problem:Proof and implications. Bulletin of Mathematical Biology, 1993, 55(6):1183～1198
[7] Berger B, Leighton T. Protein folding in the hydrophobic-hydrophilic(HP) model is NP-complete.in: Istrail S, Pevzner P, Waterman M S, editors. Proceedings of the 2nd Annual International Con-ferences on Computational Molecular Biology. New York, USA. 1998. New York: ACM Press,1998. 30～39
[8] O’Toole E M, Panagiotopoulos A Z. Effect of sequence and intermolecular interactions on thenumber and nature of low-energy states for simple model proteins. Journal of Chemical Physics,1993, 98(44):3185～3190
[9] Will S. Constraint-based hydrophobic core construction for protein structure prediction in theface-centered-cubic lattice. in: Chrisman L, Langley P, Bay S, et al., editors. Proceedings of the7th Pacific Symposium on Biocomputing. Lihue, Hawaii, USA. 2002. NJ, USA: World ScientificPublishing, 2002. 661～672
[10] Stillinger F H, Head-Gordon T, Hirshfeld C L. The model for protein folding. Physical Review E,1993, 48(2):1469～1477
[11] Head-Gordon T, Stillinger F H. Optimal neural networks for protein-structure prediction. PhysicalReview E, 1993, 48(2):1502～1515
[12] Irback A, Peterson C, Potthast F, et al. Local interactions and protein folding: A three-dimensionaloff-lattice approach. Journal of Chemical Physics, 1997, 107(1):273～282
[13] Klimov D K, Thirumalai D. Factors governing the foldability of proteins. Proteins: Structure,Function, and Bioinformatics, 1996, 26(4):411～441
[14] Unger R, Moult J. Genetic algorithm for protein folding simulations. Journal of Molecular Biol-ogy, 1993, 231(1):75～81
[15] Konig R, Dandekar T. Solvent entropy-driven searching for protein modeling examined and testedin simplified models. Protein Engineering, 2001, 14(5):329～335
[16] Beutler T C, Dill K A. A fast conformational search strategy for finding low energy structures ofmodel proteins. Protein Science, 1996, 5(10):2037～2043
[17] Chikenji G, Kikuchi M, Iba Y. Multi-Self-Overlap ensemble for protein folding: ground statesearch and thermodynamics. Physical Review Letters, 1999, 83(9):1886～1889
[18] Zhang J L, Liu J S. A new sequential importance sampling method and its application tothe two-dimensional Hydrophobic-Hydrophilic model. Journal of Chemical Physics, 2002,117(7):3492～3498
[19] Grassberger P. Pruned-enriched Rosenbluth method: Simulations of theta polymers of chain lengthup to 1 000 000. Physical Review E, 1997, 56(3):3682～3693
[20] Frauenkron H, Bastolla U, Gerstner E, et al. New Monte Carlo algorithm for protein folding.Physical Review Letters, 1998, 80(14):3149～3152
[21] Bastolla U, Frauenkron H, Gerstner E, et al. Testing a new monte carlo algorithm for proteinfolding. Proteins: Structure, Function, and Bioinformatics, 1998, 32(1):52～66
[22] Hsu H P, Mehra V, Nadler W, et al. Growth algorithms for lattice heteropolymers at low tempera-tures. Journal of Chemical Physics, 2003, 118(1):444～452
[23] Hsu H P, Mehra V, Nadler W, et al. A growth-based optimization algorithm for lattice heteropoly-mers. Physical Review E, 2003, 68(2):021113
[24] Bachmann M, Janke W. Thermodynamics of lattice heteropolymers. Journal of Chemical Physics,2004, 120(14):6779～6791
[25] Chou C I, Han R S, Li S P, et al. Guided simulated annealing method for optimization problems.Physical Review E, 2003, 67(6):066704
[26] Jiang T Z, Cui Q H, Shi G H, et al. Protein folding simulations of the hydrophobic-hydrophilicmodel by combining tabu search with genetic algorithms. Journal of Chemical Physics, 2003,119(8):4592～4596
[27] Liang F, Wong W H. Evolutionary Monte Carlo for protein folding simulations. Journal of Chem-ical Physics, 2001, 115(7):3374～3380
[28] Irback A, Potthast F. Studies of an off-lattice model for protein folding: Sequence de-pendence and improved sampling at finite temperature. Journal of Chemical Physics, 1995,103(23):10298～10305
[29] Stillinger F H, Head-Gordon T. Collective aspects of protein folding illustrated by a toy model.Physical Review E, 1995, 52(3):2872～2877
[30] Irback A, Peterson C, Potthast F. Identification of amino acid sequences with good folding prop-erties in an off-lattice model. Physical Review E, 1997, 55(1):860～867
[31] Gorse D. Global minimization of an off-lattice potential energy function using a chaperone-basedrefolding method. Biopolymers, 2001, 59(6):411～426
[32] Gorse D. Application of a chaperone-based refolding method to two- and three-dimensional off-lattice protein models. Biopolymers, 2002, 64(3):146～160
[33] Torcini A, Livi R, Politi A. A dynamical approach to protein folding. Journal of MolecularBiology, 2001, 27(2-3):181～203
[34] Hsu H P, Mehra V, Grassberger P. Structure optimization in an off-lattice protein model. PhysicalReview E, 2003, 68(3):037703
[35] Liang F. Annealing contour Monte Carlo algorithm for structure optimization in an off-latticeprotein model. Journal of Chemical Physics, 2004, 120(14):6756～6763
[36] Wang F, Landau D P. Efficient, multiple-range random walk algorithm to calculate the density ofstates. Physical Review Letters, 2001, 86(10):2050～2053
[37] Wang F, Landau D P. Determining the density of states for classical statistical models: A randomwalk algorithm to produce a ?at histogram. Physical Review E, 2001, 64(5):056101
[38] Hesselbo B, Stinchcombe R B. Monte Carlo simulation and global optimization without parame-ters. Physical Review Letters, 1995, 74(12):2151～2155
[39] Bachmann M, Arkin H, Janke W. Multicanonical study of coarse-grained off-lattice models forfolding heteropolymers. Physical Review E, 2005, 71(3):031906
[40] Hansmann U H E, Wille L T. Global optimization by energy landscape paving. Physical ReviewLetters, 2002, 88(6):068105
[41] Kim S Y, Lee S B, Lee J. Structure optimization by conformational space annealing in an off-latticeprotein model. Physical Review E, 2005, 72(1):011916
[42] Lee J, Scheraga H A, Rackovsky S. New optimization method for conformational energy calcula-tions on polypeptides: Conformational space annealing. Journal of Computational Physics, 1997,18(9):1222～1232
[43] Elser V, Rankenburg I. Deconstructing the energy landscape: new algorithms for folding het-eropolymers. Physical Review E, 2006, 73(2):026702
[44]王敞,陈增强,袁著祉.基于并行遗传算法的蛋白质空间结构预测.计算机科学, 2003,30(7):147～150
[45]解伟,王翼飞.蛋白质折叠的计算机模拟.上海大学学报(自然科学版), 2000, 6(2):145～149
[46]解伟,王翼飞.蛋白质折叠的三维计算机模拟.上海大学学报(自然科学版), 2000,6(6):548～550
[47] Garey M R, Johnson D S. Computers and intractability: a guide to the theory of NP-completeness.1st ed. San Francisco, CA: W H Freeman, 1979
[48] Sipser M. Introduction to the theory of computation. 2nd ed. Boston, USA: PWS PublishingCompany, 1997
[49] Cook S A. The complexity of theorem-proving procedures. in: ACM, editor. Proceedings of the3rd ACM Symposium on Theory of Computing. Shaker Heights, Ohio, USA. 1971. New York:ACM Press, 1971. 151～158
[50] Reeves C R. Modern heuristic techniques for combinatorial problems. 1st ed. Oxford, UK: Black-well Scientific Publications, 1993
[51] Huang W, Chen D, Xu R. A new heuristic algorithm for rectangle packing. Computers andOperations Research, 2007, 34(11):3270～3280
[52] Chen D, Huang W. A novel quasi-human heuristic algorithm for two-dimensional rectanglepacking problem. International Journal of Computer Science and Network Security, 2006,6(12):115～120
[53] Huang W, Li Y, Jurkowiak B, et al. A two-level search strategy for packing unequal circles intoa circle container. in: Rossi F, editor. Proceedings of the 9th International Conference on Prin-ciples and Practice of Constraint Programming. Kinsale, County Cork, Ireland. 2003. Heidelber,Germany: Springer, 2003. 868～872
[54] Huang W, Li Y, Li C, et al. New heuristics for packing unequal circles into a circular container.Computers and Operations Research, 2006, 33(8):2125～2142
[55] Lenstra J K, Aarts E. Local search in combinatorial optimization. 1st ed. Chichester, UK: JohnWiley and Sons, 1997
[56] Glover F W, Kochenberger G A. Handbook of Metaheuristics. 1st ed. Dordrecht: Kluwer, 2003
[57] Feo T A, Resende M G C. Greedy randomized adaptive search procedures. Journal of GlobalOptimization, 1995, 6(1):109～133
[58] Ribeiro C, Hansen P. Essays and surverys in metaheuristics. 1st ed. Dordrecht: Kluwer, 2002
[59] Holland J H. Adaptation in natural and artificial systems. 1st ed. Ann Arbor, IL: University ofMichigan Press, 1975
[60] Holland J H. Genetic algorithms. Scientific American, 1992, 267(4):44～50
[61] Kirkpatrick S, Jr C D G, Vecchi M P. Optimization by simulated annealing. Science, 1983,220(4598):671～680
[62]姚新,陈国良.模拟退火算法及其应用.计算机研究与发展, 1990, 7(1):1～6
[63] Glover F. Future paths for integer programming and links to artificial intelligence. Computers andOperations Research, 1986, 13(5):533～549
[64] Hansen P. The steepest ascent mildest descent heuristic for combinatorial programming. in:Hansen P, editor. Proceedings of Congress on Numerical Methods in Combinatorial Optimization.Capri, Italy. 1986. Dordrecht: Kluwer, 1986. 533～549
[65] Glover F. Tabu search—Part 1. ORSA Journal on Computing, 1989, 1(3):190～206
[66] Glover F. Tabu search—Part 1. ORSA Journal on Computing, 1990, 2(1):4～32
[67] Glover F, Laguna M. Tabu search. 1st ed. Dordrecht: Kluwer, 1997
[68] Colorni A, Dorigo M, Maniezzo V. An investigation of some properties of an“Ant algorithm”.in: Manner R, Manderick B, editors. Proceedings of the Parallel Problem Solving From NatureConference. Brussels, Belgium. 1992. New York: Elsevier Publishing, 1992. 509～520
[69] Dorigo M, Maniezzo V, Colorni A. The ant system: Optimization by a colony of cooperatingagents. IEEE Transactions on Systems, Man, and Cybernetics-Part B, 1996, 26(1):29～41
[70] Colorni A, Dorigo M, Maniezzo V. Distributed optimization by ant colonies. in: Fullmer B,Miikkulainen R, editors. Proceedings of European Conference on Artificial Life. Paris, France.1991. New York: Elsevier Publishing, 1991. 134～142
[71] Mladenovic′N, Hansen P. Variable neighborhood search. Computers and Operations Research,1997, 24(11):1097～1100
[72] Voss S, Martello S, Osman I H, et al. Metaheuristics: advances and trends in local search proce-dures for optimization, 1st ed. Dordrecht, Boston: Kluwer, 1999
[73] Barr R S, Helgason R V, Kennington J L. Interfaces in computer science and operations research:Advances in metaheuristics, optimization, and stochastic modeling technologies, 1st ed. Dor-drecht, Boston: Kluwer, 1996
[74] Boettcher S, Percus A G. Optimization with extremal dynamics. Physical Review Letters, 2001,86(23):5211
[75] Boettcher S, Percus A G. Extremal optimization for graph partitioning. Physical Review E, 2001,64(2):026114
[76] Ferna′ndez A, Go′mez S. Portfolio selection using neural networks. Computers and OperationsResearch, 2007, 34(6):1177～1191
[77] Blum C, Roli A. Metaheuristics in combinatorial optimization: overview and conceptual compar-ison. ACM Computing Surveys, 2003, 35(3):268～308
[78] Ribeiro C, Martins S L, Rosseti I. Metaheuristics for optimization problems in computer commu-nications. Computer Communications, 2006, doi:10.1016/j.comcom.2006.08.027
[79]黄文奇,许如初,陈卫东等.解packing及CNF-SAT问题的拟物拟人方法.华中理工大学学报,1998, 26(9):5～7
[80]李未,黄文奇.一种求解合取范式可满足性问题的数学物理方法.中国科学A辑, 1994,24(11):1208～1217
[81] Huang W, Li W. A hopeful CNF～SAT algorithm–Its high efficiency, industrial application andlimitation. Journal of Computer Science and Technology, 1998, 13(1):9～12
[82]黄文奇,金人超.求解SAT问题的拟物拟人算法–Solar.中国科学(E辑), 1998, 27(2):179～186
[83] Huang W, Jin R. Quasiphysical and quasisociological algorithm Solar for solving SAT problem.Science In China(Series E), 1999, 42(5):485～493
[84]黄文奇.求解Covering问题的拟物方法–NP难度问题的一个处理途径.计算机学报, 1989,12(8):610～616
[85]黄文奇,詹叔浩.一类几何布局问题的计算机辅助设计.应用数学学报, 1983, 6(1):34～46
[86]黄文奇,詹叔浩.求解Packing问题的拟物方法.应用数学学报, 1979, 2(2):176～180
[87]黄文奇,李庆华,余向东.求解空间Packing问题的拟物方法.应用数学学报, 1986,9(4):443～453
[88]康雁,黄文奇.求解圆形packing问题的一个快速拟物算法.计算机工程与应用, 2003,39(35):30～32
[89]康雁,黄文奇.求解圆形Packing问题的一个启发式算法.计算机研究与发展, 2003,39(4):410～414
[90] Huang W, Kang Y. A heuristic quasi-physical strategy for solving disks packing problem. Simu-lation Modeling Practice and Theory, 2002, 10(4):195～207
[91] Wang H, Huang W, Zhang Q, et al. An improved algorithm for the packing of unequalcircles within a larger containing circle. European Journal of Operational Research, 2002,141(2):440～453
[92]黄文奇,陈亮.求解有关空间利用的调度问题的拟物方法.中国科学(A辑), 1991,29(4):325～331
[93]黄文奇,许如初.支持求解圆形Packing问题的两个拟人策略.中国科学(A辑), 1999,29(4):347～353
[94]黄文奇,朱虹.求解方格PACKING问题的启发式算法.计算机学报, 1993, 16(11):829～836
[95]黄文奇,何大华.求解单位等边三角形PACKING问题的最小损伤法.武钢大学学报, 2000,12(1):1～3
[96]王磊,黄文奇.求解置换Flow shop调度问题的一种启发式算法.计算机工程与应用, 2004,40(19):31～32
[97] Huang W, Wang L. A novel local search method for the traveling salesman problem.西南交通大学学报英文版, 2005, 13(1):1～4
[98]王磊,黄文奇.求解工件车间调度问题的一种新的邻域搜索算法.计算机学报, 2005,28(5):809～816
[99] Guttman A J, Ninham B W, Tompson C J. Determination of critical behavior in lattice statisticsfrom series expansions. Physical Review, 1968, 172(2):554～558
[100] Grassberger P. Recursive sampling of random walks: Self-avoiding walks in disordered media.Journal of Physics A, 1993, 26(5):1023～1036
[101] Hegger R, Grassberger P. Chain polymers near absorbing surface. Journal of Physics A, 1994,27(12):4069～4081
[102] Rosenbluth M N, Rosenbluth A W. Monte Carlo calculation of the average extension of molecularchains. Journal of Chemical Physics, 1955, 23(2):356～359
[103] Wall F T, Erpenbeck J J. New method for the statistical computation of polymer dimensions.Journal of Chemical Physics, 1959, 30(1):634～637
[104] Grassberger P. Sequential Monte Carlo methods for protein folding. in: Wolf D, Munster G,Kremer M, editors. Proceedings of NIC Symposium. Ju¨lich, Germany. 2004. John von NeumannInstitute for Computing, Ju¨lich: NIC Series, 2004. 1～10
[105] Hochbaum D S, Maass W. Approximation schemes for covering and packing problems in imageprocessing and VLSI. Journal of the Association for Computing Machinery, 1985, 1(32):130～136
[106] Zhang D, Deng A. An effective hybrid algorithm for the problem of packing circles into a largercontaining circle. Computers and Operations Research, 2005, 32(8):1941～1951
[107] Huang W, Kang Y. A short note on a simple search heuristic for the disk packing problem. Annalsof Operations Research, 2004, 131(1-4):101～108
[108]许如初,黄文奇.解不等圆packing问题拟物拟人算法初态选取.华中理工大学学报, 1998,26(4):1～3
[109]黄文奇,陈端兵.一种求解矩形块布局问题的拟物拟人算法.计算机科学, 2005,32(11):182～186
[110]陈端兵,黄文奇.一种求解矩形块装填问题的拟人算法.计算机科学, 2006, 33(5):234～237
[111]陈端兵,黄文奇.求解矩形和圆形装填问题的最大穴度算法.计算机工程与应用, 2007,43(4):1～3
[112]陈端兵,黄文奇.求解矩形packing问题的贪心算法.计算机工程, 2007, 33(4):160～162
[113] Boyd S, Vandenberghe L. Convex optimization. 1st ed. Cambridge, UK: Cambridge UniversityPress, 2004
[114] Yue K, Fiebig K M, Thomas P D, et al. A test of lattice protein folding algorithms. Proceedingsof the National Academy of Sciences USA, 1995, 92(1):325～329
[115] Dill K A, Fiebig K, Chan H S. Cooperativity in protein-folding kinetics. Proceedings of theNational Academy of Sciences USA, 1993, 90(5):1942～1946
[116] Lattman E E, Fiebig K M, Dill K A. Modeling compact denatured states of proteins. Biochemistry,1994, 33(20):6158～6166
[117] Toma L, Toma S. Contact interactions method: A new algorithm for protein folding simulations.Protein Science, 1996, 5(1):147～153
[2] Yue K, Dill K A. Forces of tertiary structural organization in globular proteins. Proceedings of theNational Academy of Sciences USA, 1995, 92(11):146～150
[3] Dill K A. Theory for the folding and stability of globular proteins. Biochemistry, 1985,24(6):1501～1509
[4] Dill K A, Bromberg S, Yue K. Principles of protein folding: A perspective from simple exactmodels. Protein Science, 1995, 4(4):561～602
[5] Shih C T, Su Z Y, Gwan J F. Mean-Field HP model, designability and Alpha-Helices in proteinstructures. Physical Review Letters, 2000, 84(2):386～389
[6] Unger R, Moult J. Finding the lowest free energy conformation of a protein is an NP-hard problem:Proof and implications. Bulletin of Mathematical Biology, 1993, 55(6):1183～1198
[7] Berger B, Leighton T. Protein folding in the hydrophobic-hydrophilic(HP) model is NP-complete.in: Istrail S, Pevzner P, Waterman M S, editors. Proceedings of the 2nd Annual International Con-ferences on Computational Molecular Biology. New York, USA. 1998. New York: ACM Press,1998. 30～39
[8] O’Toole E M, Panagiotopoulos A Z. Effect of sequence and intermolecular interactions on thenumber and nature of low-energy states for simple model proteins. Journal of Chemical Physics,1993, 98(44):3185～3190
[9] Will S. Constraint-based hydrophobic core construction for protein structure prediction in theface-centered-cubic lattice. in: Chrisman L, Langley P, Bay S, et al., editors. Proceedings of the7th Pacific Symposium on Biocomputing. Lihue, Hawaii, USA. 2002. NJ, USA: World ScientificPublishing, 2002. 661～672
[10] Stillinger F H, Head-Gordon T, Hirshfeld C L. The model for protein folding. Physical Review E,1993, 48(2):1469～1477
[11] Head-Gordon T, Stillinger F H. Optimal neural networks for protein-structure prediction. PhysicalReview E, 1993, 48(2):1502～1515
[12] Irback A, Peterson C, Potthast F, et al. Local interactions and protein folding: A three-dimensionaloff-lattice approach. Journal of Chemical Physics, 1997, 107(1):273～282
[13] Klimov D K, Thirumalai D. Factors governing the foldability of proteins. Proteins: Structure,Function, and Bioinformatics, 1996, 26(4):411～441
[14] Unger R, Moult J. Genetic algorithm for protein folding simulations. Journal of Molecular Biol-ogy, 1993, 231(1):75～81
[15] Konig R, Dandekar T. Solvent entropy-driven searching for protein modeling examined and testedin simplified models. Protein Engineering, 2001, 14(5):329～335
[16] Beutler T C, Dill K A. A fast conformational search strategy for finding low energy structures ofmodel proteins. Protein Science, 1996, 5(10):2037～2043
[17] Chikenji G, Kikuchi M, Iba Y. Multi-Self-Overlap ensemble for protein folding: ground statesearch and thermodynamics. Physical Review Letters, 1999, 83(9):1886～1889
[18] Zhang J L, Liu J S. A new sequential importance sampling method and its application tothe two-dimensional Hydrophobic-Hydrophilic model. Journal of Chemical Physics, 2002,117(7):3492～3498
[19] Grassberger P. Pruned-enriched Rosenbluth method: Simulations of theta polymers of chain lengthup to 1 000 000. Physical Review E, 1997, 56(3):3682～3693
[20] Frauenkron H, Bastolla U, Gerstner E, et al. New Monte Carlo algorithm for protein folding.Physical Review Letters, 1998, 80(14):3149～3152
[21] Bastolla U, Frauenkron H, Gerstner E, et al. Testing a new monte carlo algorithm for proteinfolding. Proteins: Structure, Function, and Bioinformatics, 1998, 32(1):52～66
[22] Hsu H P, Mehra V, Nadler W, et al. Growth algorithms for lattice heteropolymers at low tempera-tures. Journal of Chemical Physics, 2003, 118(1):444～452
[23] Hsu H P, Mehra V, Nadler W, et al. A growth-based optimization algorithm for lattice heteropoly-mers. Physical Review E, 2003, 68(2):021113
[24] Bachmann M, Janke W. Thermodynamics of lattice heteropolymers. Journal of Chemical Physics,2004, 120(14):6779～6791
[25] Chou C I, Han R S, Li S P, et al. Guided simulated annealing method for optimization problems.Physical Review E, 2003, 67(6):066704
[26] Jiang T Z, Cui Q H, Shi G H, et al. Protein folding simulations of the hydrophobic-hydrophilicmodel by combining tabu search with genetic algorithms. Journal of Chemical Physics, 2003,119(8):4592～4596
[27] Liang F, Wong W H. Evolutionary Monte Carlo for protein folding simulations. Journal of Chem-ical Physics, 2001, 115(7):3374～3380
[28] Irback A, Potthast F. Studies of an off-lattice model for protein folding: Sequence de-pendence and improved sampling at finite temperature. Journal of Chemical Physics, 1995,103(23):10298～10305
[29] Stillinger F H, Head-Gordon T. Collective aspects of protein folding illustrated by a toy model.Physical Review E, 1995, 52(3):2872～2877
[30] Irback A, Peterson C, Potthast F. Identification of amino acid sequences with good folding prop-erties in an off-lattice model. Physical Review E, 1997, 55(1):860～867
[31] Gorse D. Global minimization of an off-lattice potential energy function using a chaperone-basedrefolding method. Biopolymers, 2001, 59(6):411～426
[32] Gorse D. Application of a chaperone-based refolding method to two- and three-dimensional off-lattice protein models. Biopolymers, 2002, 64(3):146～160
[33] Torcini A, Livi R, Politi A. A dynamical approach to protein folding. Journal of MolecularBiology, 2001, 27(2-3):181～203
[34] Hsu H P, Mehra V, Grassberger P. Structure optimization in an off-lattice protein model. PhysicalReview E, 2003, 68(3):037703
[35] Liang F. Annealing contour Monte Carlo algorithm for structure optimization in an off-latticeprotein model. Journal of Chemical Physics, 2004, 120(14):6756～6763
[36] Wang F, Landau D P. Efficient, multiple-range random walk algorithm to calculate the density ofstates. Physical Review Letters, 2001, 86(10):2050～2053
[37] Wang F, Landau D P. Determining the density of states for classical statistical models: A randomwalk algorithm to produce a ?at histogram. Physical Review E, 2001, 64(5):056101
[38] Hesselbo B, Stinchcombe R B. Monte Carlo simulation and global optimization without parame-ters. Physical Review Letters, 1995, 74(12):2151～2155
[39] Bachmann M, Arkin H, Janke W. Multicanonical study of coarse-grained off-lattice models forfolding heteropolymers. Physical Review E, 2005, 71(3):031906
[40] Hansmann U H E, Wille L T. Global optimization by energy landscape paving. Physical ReviewLetters, 2002, 88(6):068105
[41] Kim S Y, Lee S B, Lee J. Structure optimization by conformational space annealing in an off-latticeprotein model. Physical Review E, 2005, 72(1):011916
[42] Lee J, Scheraga H A, Rackovsky S. New optimization method for conformational energy calcula-tions on polypeptides: Conformational space annealing. Journal of Computational Physics, 1997,18(9):1222～1232
[43] Elser V, Rankenburg I. Deconstructing the energy landscape: new algorithms for folding het-eropolymers. Physical Review E, 2006, 73(2):026702
[44]王敞,陈增强,袁著祉.基于并行遗传算法的蛋白质空间结构预测.计算机科学, 2003,30(7):147～150
[45]解伟,王翼飞.蛋白质折叠的计算机模拟.上海大学学报(自然科学版), 2000, 6(2):145～149
[46]解伟,王翼飞.蛋白质折叠的三维计算机模拟.上海大学学报(自然科学版), 2000,6(6):548～550
[47] Garey M R, Johnson D S. Computers and intractability: a guide to the theory of NP-completeness.1st ed. San Francisco, CA: W H Freeman, 1979
[48] Sipser M. Introduction to the theory of computation. 2nd ed. Boston, USA: PWS PublishingCompany, 1997
[49] Cook S A. The complexity of theorem-proving procedures. in: ACM, editor. Proceedings of the3rd ACM Symposium on Theory of Computing. Shaker Heights, Ohio, USA. 1971. New York:ACM Press, 1971. 151～158
[50] Reeves C R. Modern heuristic techniques for combinatorial problems. 1st ed. Oxford, UK: Black-well Scientific Publications, 1993
[51] Huang W, Chen D, Xu R. A new heuristic algorithm for rectangle packing. Computers andOperations Research, 2007, 34(11):3270～3280
[52] Chen D, Huang W. A novel quasi-human heuristic algorithm for two-dimensional rectanglepacking problem. International Journal of Computer Science and Network Security, 2006,6(12):115～120
[53] Huang W, Li Y, Jurkowiak B, et al. A two-level search strategy for packing unequal circles intoa circle container. in: Rossi F, editor. Proceedings of the 9th International Conference on Prin-ciples and Practice of Constraint Programming. Kinsale, County Cork, Ireland. 2003. Heidelber,Germany: Springer, 2003. 868～872
[54] Huang W, Li Y, Li C, et al. New heuristics for packing unequal circles into a circular container.Computers and Operations Research, 2006, 33(8):2125～2142
[55] Lenstra J K, Aarts E. Local search in combinatorial optimization. 1st ed. Chichester, UK: JohnWiley and Sons, 1997
[56] Glover F W, Kochenberger G A. Handbook of Metaheuristics. 1st ed. Dordrecht: Kluwer, 2003
[57] Feo T A, Resende M G C. Greedy randomized adaptive search procedures. Journal of GlobalOptimization, 1995, 6(1):109～133
[58] Ribeiro C, Hansen P. Essays and surverys in metaheuristics. 1st ed. Dordrecht: Kluwer, 2002
[59] Holland J H. Adaptation in natural and artificial systems. 1st ed. Ann Arbor, IL: University ofMichigan Press, 1975
[60] Holland J H. Genetic algorithms. Scientific American, 1992, 267(4):44～50
[61] Kirkpatrick S, Jr C D G, Vecchi M P. Optimization by simulated annealing. Science, 1983,220(4598):671～680
[62]姚新,陈国良.模拟退火算法及其应用.计算机研究与发展, 1990, 7(1):1～6
[63] Glover F. Future paths for integer programming and links to artificial intelligence. Computers andOperations Research, 1986, 13(5):533～549
[64] Hansen P. The steepest ascent mildest descent heuristic for combinatorial programming. in:Hansen P, editor. Proceedings of Congress on Numerical Methods in Combinatorial Optimization.Capri, Italy. 1986. Dordrecht: Kluwer, 1986. 533～549
[65] Glover F. Tabu search—Part 1. ORSA Journal on Computing, 1989, 1(3):190～206
[66] Glover F. Tabu search—Part 1. ORSA Journal on Computing, 1990, 2(1):4～32
[67] Glover F, Laguna M. Tabu search. 1st ed. Dordrecht: Kluwer, 1997
[68] Colorni A, Dorigo M, Maniezzo V. An investigation of some properties of an“Ant algorithm”.in: Manner R, Manderick B, editors. Proceedings of the Parallel Problem Solving From NatureConference. Brussels, Belgium. 1992. New York: Elsevier Publishing, 1992. 509～520
[69] Dorigo M, Maniezzo V, Colorni A. The ant system: Optimization by a colony of cooperatingagents. IEEE Transactions on Systems, Man, and Cybernetics-Part B, 1996, 26(1):29～41
[70] Colorni A, Dorigo M, Maniezzo V. Distributed optimization by ant colonies. in: Fullmer B,Miikkulainen R, editors. Proceedings of European Conference on Artificial Life. Paris, France.1991. New York: Elsevier Publishing, 1991. 134～142
[71] Mladenovic′N, Hansen P. Variable neighborhood search. Computers and Operations Research,1997, 24(11):1097～1100
[72] Voss S, Martello S, Osman I H, et al. Metaheuristics: advances and trends in local search proce-dures for optimization, 1st ed. Dordrecht, Boston: Kluwer, 1999
[73] Barr R S, Helgason R V, Kennington J L. Interfaces in computer science and operations research:Advances in metaheuristics, optimization, and stochastic modeling technologies, 1st ed. Dor-drecht, Boston: Kluwer, 1996
[74] Boettcher S, Percus A G. Optimization with extremal dynamics. Physical Review Letters, 2001,86(23):5211
[75] Boettcher S, Percus A G. Extremal optimization for graph partitioning. Physical Review E, 2001,64(2):026114
[76] Ferna′ndez A, Go′mez S. Portfolio selection using neural networks. Computers and OperationsResearch, 2007, 34(6):1177～1191
[77] Blum C, Roli A. Metaheuristics in combinatorial optimization: overview and conceptual compar-ison. ACM Computing Surveys, 2003, 35(3):268～308
[78] Ribeiro C, Martins S L, Rosseti I. Metaheuristics for optimization problems in computer commu-nications. Computer Communications, 2006, doi:10.1016/j.comcom.2006.08.027
[79]黄文奇,许如初,陈卫东等.解packing及CNF-SAT问题的拟物拟人方法.华中理工大学学报,1998, 26(9):5～7
[80]李未,黄文奇.一种求解合取范式可满足性问题的数学物理方法.中国科学A辑, 1994,24(11):1208～1217
[81] Huang W, Li W. A hopeful CNF～SAT algorithm–Its high efficiency, industrial application andlimitation. Journal of Computer Science and Technology, 1998, 13(1):9～12
[82]黄文奇,金人超.求解SAT问题的拟物拟人算法–Solar.中国科学(E辑), 1998, 27(2):179～186
[83] Huang W, Jin R. Quasiphysical and quasisociological algorithm Solar for solving SAT problem.Science In China(Series E), 1999, 42(5):485～493
[84]黄文奇.求解Covering问题的拟物方法–NP难度问题的一个处理途径.计算机学报, 1989,12(8):610～616
[85]黄文奇,詹叔浩.一类几何布局问题的计算机辅助设计.应用数学学报, 1983, 6(1):34～46
[86]黄文奇,詹叔浩.求解Packing问题的拟物方法.应用数学学报, 1979, 2(2):176～180
[87]黄文奇,李庆华,余向东.求解空间Packing问题的拟物方法.应用数学学报, 1986,9(4):443～453
[88]康雁,黄文奇.求解圆形packing问题的一个快速拟物算法.计算机工程与应用, 2003,39(35):30～32
[89]康雁,黄文奇.求解圆形Packing问题的一个启发式算法.计算机研究与发展, 2003,39(4):410～414
[90] Huang W, Kang Y. A heuristic quasi-physical strategy for solving disks packing problem. Simu-lation Modeling Practice and Theory, 2002, 10(4):195～207
[91] Wang H, Huang W, Zhang Q, et al. An improved algorithm for the packing of unequalcircles within a larger containing circle. European Journal of Operational Research, 2002,141(2):440～453
[92]黄文奇,陈亮.求解有关空间利用的调度问题的拟物方法.中国科学(A辑), 1991,29(4):325～331
[93]黄文奇,许如初.支持求解圆形Packing问题的两个拟人策略.中国科学(A辑), 1999,29(4):347～353
[94]黄文奇,朱虹.求解方格PACKING问题的启发式算法.计算机学报, 1993, 16(11):829～836
[95]黄文奇,何大华.求解单位等边三角形PACKING问题的最小损伤法.武钢大学学报, 2000,12(1):1～3
[96]王磊,黄文奇.求解置换Flow shop调度问题的一种启发式算法.计算机工程与应用, 2004,40(19):31～32
[97] Huang W, Wang L. A novel local search method for the traveling salesman problem.西南交通大学学报英文版, 2005, 13(1):1～4
[98]王磊,黄文奇.求解工件车间调度问题的一种新的邻域搜索算法.计算机学报, 2005,28(5):809～816
[99] Guttman A J, Ninham B W, Tompson C J. Determination of critical behavior in lattice statisticsfrom series expansions. Physical Review, 1968, 172(2):554～558
[100] Grassberger P. Recursive sampling of random walks: Self-avoiding walks in disordered media.Journal of Physics A, 1993, 26(5):1023～1036
[101] Hegger R, Grassberger P. Chain polymers near absorbing surface. Journal of Physics A, 1994,27(12):4069～4081
[102] Rosenbluth M N, Rosenbluth A W. Monte Carlo calculation of the average extension of molecularchains. Journal of Chemical Physics, 1955, 23(2):356～359
[103] Wall F T, Erpenbeck J J. New method for the statistical computation of polymer dimensions.Journal of Chemical Physics, 1959, 30(1):634～637
[104] Grassberger P. Sequential Monte Carlo methods for protein folding. in: Wolf D, Munster G,Kremer M, editors. Proceedings of NIC Symposium. Ju¨lich, Germany. 2004. John von NeumannInstitute for Computing, Ju¨lich: NIC Series, 2004. 1～10
[105] Hochbaum D S, Maass W. Approximation schemes for covering and packing problems in imageprocessing and VLSI. Journal of the Association for Computing Machinery, 1985, 1(32):130～136
[106] Zhang D, Deng A. An effective hybrid algorithm for the problem of packing circles into a largercontaining circle. Computers and Operations Research, 2005, 32(8):1941～1951
[107] Huang W, Kang Y. A short note on a simple search heuristic for the disk packing problem. Annalsof Operations Research, 2004, 131(1-4):101～108
[108]许如初,黄文奇.解不等圆packing问题拟物拟人算法初态选取.华中理工大学学报, 1998,26(4):1～3
[109]黄文奇,陈端兵.一种求解矩形块布局问题的拟物拟人算法.计算机科学, 2005,32(11):182～186
[110]陈端兵,黄文奇.一种求解矩形块装填问题的拟人算法.计算机科学, 2006, 33(5):234～237
[111]陈端兵,黄文奇.求解矩形和圆形装填问题的最大穴度算法.计算机工程与应用, 2007,43(4):1～3
[112]陈端兵,黄文奇.求解矩形packing问题的贪心算法.计算机工程, 2007, 33(4):160～162
[113] Boyd S, Vandenberghe L. Convex optimization. 1st ed. Cambridge, UK: Cambridge UniversityPress, 2004
[114] Yue K, Fiebig K M, Thomas P D, et al. A test of lattice protein folding algorithms. Proceedingsof the National Academy of Sciences USA, 1995, 92(1):325～329
[115] Dill K A, Fiebig K, Chan H S. Cooperativity in protein-folding kinetics. Proceedings of theNational Academy of Sciences USA, 1993, 90(5):1942～1946
[116] Lattman E E, Fiebig K M, Dill K A. Modeling compact denatured states of proteins. Biochemistry,1994, 33(20):6158～6166
[117] Toma L, Toma S. Contact interactions method: A new algorithm for protein folding simulations.Protein Science, 1996, 5(1):147～153